# Posted By

medikgt on 07/19/09

# Statistics

Viewed 224 times
Favorited by 0 user(s)

# Related snippets

/ Published in: C++
`#include <iostream>#include <limits>#include <map>#include <list>#include <queue> using namespace std; const int INFINITY = INT_MAX; enum Color { WHITE, GRAY, BLACK }; class Vertex{public:    Vertex();    Vertex(char id);    ~Vertex();    char Vertex::getId() const;    void Vertex::setId(char arg);     bool operator <(const Vertex& rhs) const    {        return id < rhs.id;    } private:    char id;}; Vertex::Vertex(): id('0'){} Vertex::Vertex(char id): id(id){} Vertex::~Vertex(){} char Vertex::getId() const{    return id;} void Vertex::setId(char arg){    id = arg;} int main(){    //created the vertices    Vertex r('r');    Vertex s('s');    Vertex t('t');    Vertex u('u');    Vertex v('v');    Vertex w('w');    Vertex x('x');    Vertex y('y');     //use maps for keeping track of color, distance and parents    map< Vertex , Color> color;    color[r] = WHITE;    color[s] = WHITE;    color[t] = WHITE;    color[u] = WHITE;    color[v] = WHITE;    color[w] = WHITE;    color[x] = WHITE;    color[y] = WHITE;     map< Vertex , int> distance;    distance[r] = INFINITY;    distance[s] = INFINITY;    distance[t] = INFINITY;    distance[u] = INFINITY;    distance[v] = INFINITY;    distance[w] = INFINITY;    distance[x] = INFINITY;    distance[y] = INFINITY;     map< Vertex , char> parent;    parent[r] = '0';    parent[s] = '0';    parent[t] = '0';    parent[u] = '0';    parent[v] = '0';    parent[w] = '0';    parent[x] = '0';    parent[y] = '0';     //create the adj lists    list<Vertex> adj_r;    list<Vertex> adj_s;    list<Vertex> adj_t;    list<Vertex> adj_u;    list<Vertex> adj_v;    list<Vertex> adj_w;    list<Vertex> adj_x;    list<Vertex> adj_y;     adj_r.push_back(s);    adj_r.push_back(v);     adj_s.push_back(r);    adj_s.push_back(w);     adj_t.push_back(w);    adj_t.push_back(x);    adj_t.push_back(u);     adj_u.push_back(t);    adj_u.push_back(x);    adj_u.push_back(y);     adj_v.push_back(r);     adj_w.push_back(s);    adj_w.push_back(t);    adj_w.push_back(x);     adj_x.push_back(w);    adj_x.push_back(t);    adj_x.push_back(y);    adj_x.push_back(u);     adj_y.push_back(x);    adj_y.push_back(u);     //map vertices to corresponding lists    map< Vertex , list<Vertex> > adj;    adj[r] = adj_r;    adj[s] = adj_s;    adj[t] = adj_t;    adj[u] = adj_u;    adj[v] = adj_v;    adj[w] = adj_w;    adj[x] = adj_x;    adj[y] = adj_y;     //other objects    queue<Vertex> q;    Vertex currentVertex;    Vertex currentDecescendant;     //start algorithm    color[s] = GRAY;    distance[s] = 0;    parent[s] = NULL;     q.push(s);     //in while loop    while( !q.empty() )    {        //dequeue        currentVertex = q.front();        q.pop();         //for each currentDecescendant in adj[currentVertex]        list<Vertex>::iterator it;        for(it = adj[currentVertex].begin(); it != adj[currentVertex].end(); it++)        {            currentDecescendant.setId( it->getId() );             if( color[currentDecescendant]==WHITE )            {                color[currentDecescendant] = GRAY;                distance[currentDecescendant] = distance[currentVertex] + 1;                parent[currentDecescendant] = currentVertex.getId();                 q.push(currentDecescendant);            }        }         color[currentVertex] = BLACK;    }     cout << "distance[r]: " << distance[r] <<endl;    cout << "distance[s]: " << distance[s] <<endl;    cout << "distance[t]: " << distance[t] <<endl;    cout << "distance[u]: " << distance[u] <<endl;    cout << "distance[v]: " << distance[v] <<endl;    cout << "distance[w]: " << distance[w] <<endl;    cout << "distance[x]: " << distance[x] <<endl;    cout << "distance[y]: " << distance[y] <<endl;     cout << endl;     cout << "parent[r]: " << parent[r] <<endl;    cout << "parent[s]: " << parent[s] <<endl;    cout << "parent[t]: " << parent[t] <<endl;    cout << "parent[u]: " << parent[u] <<endl;    cout << "parent[v]: " << parent[v] <<endl;    cout << "parent[w]: " << parent[w] <<endl;    cout << "parent[x]: " << parent[x] <<endl;    cout << "parent[y]: " << parent[y] <<endl;     cout << endl;     char travaller = 'u';    char source = 's';     while(travaller!=source)    {        cout << parent[travaller];        travaller = parent[travaller];    }     return 0;}`