Problem implementing BFS for my graph data struct

Here is design of my graph data structure which i've developed from scratch. Now to implement BFS i am thinking to use some part of STL to levitate more burden.

I am using algorithm from Cormen's book .For some portion of algorithms like color[u] , distance[u] etc , i am thinking to use map. but i am unable to decided whether i should use map like >> std::map<node<T>*, Node_struct_data_like_color_etc> or std::map<data_type_which_node_contains, Node_struct_data_like_color_etc>

Also, Above map will have t开发者_开发知识库o fit with other part of algo like for(all_adjacent_vertex_v_of_u) etc

I am sorry that my question might would look vague but couldn't explain more better than this.

I have this simple bfs written if it helps

//simple bfs assuming graph is of the form vecotr<int> g
int q[20000];
int vis[20000];

void bfs( int v_ )
{
    int top = 0;
    memset(vis, 0, sizeof(vis));
    vis[v_] = 1;
    q[top++]=v_;
    while( top )
    {
        int v = q[--top];
        for( vector<int>::iterator it = g[v].begin(); it!= g[v].end(); ++it )
        {
            int u = *it;
            if( !vis[u] )
            {
                q[top++]=u;
                vis[u] = 1;
            }
        }
    }
}    

Once i was trying to do something similar. The mistake i did was i didn't define the function object to sort the elements of the map when i stored the pointer to the node as index type. So you should consider this when you design your BFS when keeping the color/other properties as value_type in the map with node pointers as the index type.

so the map that you are planning to implement should look something like this

std::map<Node_t*,NodeProperty_t*,SortNode>

struct SortNode{
operator()(Node_t*,Node_t*){
//...
}
}

You might want to take a look at the Boost Graph Library for inspiration, or even just use it.

Note that it supports both property maps (like the first map you suggested) and custom node classes (what @Grigory Javadyan and I suggest).