Pastable version of Breadth First Search (Textbook Example)

<pre class='prettyprint' language='c++'>#include &lt;iostream&gt;
#include &lt;limits&gt;
#include &lt;map&gt;
#include &lt;list&gt;
#include &lt;queue&gt;

using namespace std;

const int INFINITY = INT_MAX;

enum Color { WHITE, GRAY, BLACK };

class Vertex
{
public:
    Vertex();
    Vertex(char id);
    ~Vertex();
    char Vertex::getId();
    void Vertex::setId(char arg);

bool operator &lt;(const Vertex&amp; rhs) const
    {
        return id &lt; rhs.id;
    }

private:
    char id;
};

Vertex::Vertex(): id('0')
{}

Vertex::Vertex(char id): id(id)
{}

Vertex::~Vertex()
{
}

char Vertex::getId()
{
    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&lt; Vertex , Color&gt; 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&lt; Vertex , int&gt; 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&lt; Vertex , Vertex*&gt; parent;
    parent[r] = NULL;
    parent[s] = NULL;
    parent[t] = NULL;
    parent[u] = NULL;
    parent[v] = NULL;
    parent[w] = NULL;
    parent[x] = NULL;
    parent[y] = NULL;

//create the adj lists
    list&lt;Vertex&gt; adj_r;
    list&lt;Vertex&gt; adj_s;
    list&lt;Vertex&gt; adj_t;
    list&lt;Vertex&gt; adj_u;
    list&lt;Vertex&gt; adj_v;
    list&lt;Vertex&gt; adj_w;
    list&lt;Vertex&gt; adj_x;
    list&lt;Vertex&gt; 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&lt; Vertex , list&lt;Vertex&gt; &gt; 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&lt;Vertex&gt; 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&lt;Vertex&gt;::iterator it;
        for(it = adj[currentVertex].begin(); it != adj[currentVertex].end(); it++)
        {
            currentDecescendant.setId( it-&gt;getId() );

if( color[currentDecescendant]==WHITE )
            {
                color[currentDecescendant] = GRAY;
                distance[currentDecescendant] = distance[currentVertex] + 1;
                parent[currentDecescendant] = &amp;currentVertex;

q.push(currentDecescendant);
            }
        }

color[currentVertex] = BLACK;
    }

cout &lt;&lt; &quot;distance[r]: &quot; &lt;&lt; distance[r] &lt;&lt;endl;
    cout &lt;&lt; &quot;distance[s]: &quot; &lt;&lt; distance[s] &lt;&lt;endl;
    cout &lt;&lt; &quot;distance[t]: &quot; &lt;&lt; distance[t] &lt;&lt;endl;
    cout &lt;&lt; &quot;distance[u]: &quot; &lt;&lt; distance[u] &lt;&lt;endl;
    cout &lt;&lt; &quot;distance[v]: &quot; &lt;&lt; distance[v] &lt;&lt;endl;
    cout &lt;&lt; &quot;distance[w]: &quot; &lt;&lt; distance[w] &lt;&lt;endl;
    cout &lt;&lt; &quot;distance[x]: &quot; &lt;&lt; distance[x] &lt;&lt;endl;
    cout &lt;&lt; &quot;distance[y]: &quot; &lt;&lt; distance[y] &lt;&lt;endl;

return 0;
}</pre>
<a href="http://www.refactormycode.com/codes/957-breadth-first-search-textbook-example" style="color:#fff" title="As seen on RefactorMyCode.com"><img alt="Small_logo" src="http://www.refactormycode.com/images/small_logo.gif" style="border:0" /></a>

Refactor :my => 'code'

Recent

Popular

Pastable version of Breadth First Search (Textbook Example)