breadth-first search and graph (adjacency lists)

[ferenczi]

Hello,

(this is not a homework).
So, I've created a graph as adjacency lists:

class Edge;

class Vertex
{
      public:
             Vertex* vNext;
             Edge* adjList;
             char FirstElement;
             bool marked;
             
             Vertex(char a) : FirstElement(a), vNext(NULL), adjList(NULL), marked(false) {  }   
};

class Edge
{
      public:
             Edge* eNext;
             int weight;
             char SecondElement;
             bool marked;
             
             Edge(char a, int b) : SecondElement(a), weight(b), eNext(NULL), marked(false) {  }
};

class Graph
{
      private:
              Vertex *gFirst;
              
      public:
             Graph() : gFirst(NULL) {  }
             
             Vertex* findElement(char n)
             {
                   Vertex* pTemp = gFirst;
                   Vertex* location = NULL;
                   
                   while (pTemp != NULL)
                   {
                        if (n == pTemp->FirstElement)
                        {
                              location = pTemp;
                              return location;
                        }
                        else
                            pTemp = pTemp->vNext;
                   }
                   
                   return location;
             }
             
             void insertVertex(char a)
             {
                 Vertex* nuovoVertex = new Vertex(a);
                 
                 if (gFirst == NULL)
                 {
                       gFirst = nuovoVertex;
                       return;     
                 }
                 
                 Vertex* pTemp = gFirst;
                 while (pTemp->vNext != NULL)
                       pTemp = pTemp->vNext;
                       
                 pTemp->vNext = nuovoVertex;
             }
             
             void insertEdge(char a, char b, int c) // Because the graph is not directed
             {
                  insertEdge_(a, b, c);
                  insertEdge_(b, a, c);
             }
             
             void insertEdge_(char a, char b, int c)
             {
                  Vertex* loc_01;
                  Vertex* loc_02;
                  
                  loc_01 = findElement(a);
                  loc_02 = findElement(b);
                  
                  if (loc_01 == NULL)
                  {
                           cout << "First element not found.";
                           return;
                  }
                  
                  if (loc_02 == NULL)
                  {
                            cout << "Second element not found.";
                            return;
                  }
                  
                  Edge* nuovoEdge = new Edge(b, c);
                  
                  if (loc_01->adjList == NULL)
                  {
                            loc_01->adjList = nuovoEdge;
                            return;                 
                  }
                  
                  Edge* pTemp = loc_01->adjList;                  
                  while (pTemp->eNext != NULL)
                        pTemp = pTemp->eNext;
                        
                  pTemp->eNext = nuovoEdge;
             }
             
             void printGraph()
             {
                  Vertex* pTemp = gFirst;
                  Edge* Temp;
                  
                  while (pTemp != NULL)
                  {
                        cout << pTemp->FirstElement;
                        Temp = pTemp->adjList;
                        
                        while (Temp != NULL)
                        {
                           cout << " -> " << Temp->SecondElement << " (weight " << Temp->weight << ")";
                              Temp = Temp->eNext;
                        }
                        
                        cout << endl;
                        pTemp = pTemp->vNext;
                  }
             }
             
             void markAll(char a)
             {
                  mark(gFirst, a);
             }
             
             void mark(Vertex* Root, char a)
             {
                  
                  Edge* Temp;
                  
                  while (Root != NULL)
                  {
                        if (Root->FirstElement == a)
                           Root->marked = true;                           
                        Temp = Root->adjList;                           
                        while (Temp != NULL)
                        {
                              if (Temp->SecondElement == a)
                                 Temp->marked = true;                                 
                              Temp = Temp->eNext; 
                        }                        
                        Root = Root->vNext;
                  }
             }
};


int main(int argc, char *argv[])
{
    Graph example;    
    example.insertVertex('a');
    example.insertVertex('b');
    example.insertVertex('c');
    example.insertVertex('d');
    example.insertVertex('e');
    example.insertVertex('f');
    example.insertVertex('g');    
    example.insertEdge('a', 'b', 0);
    example.insertEdge('a', 'c', 0);
    example.insertEdge('a', 'd', 0);
    example.insertEdge('b', 'c', 0);
    example.insertEdge('c', 'd', 0);
    example.insertEdge('c', 'e', 0);
    example.insertEdge('e', 'f', 0);
    example.insertEdge('e', 'g', 0);
    example.insertEdge('f', 'g', 0);    
    example.printGraph();    
    return EXIT_SUCCESS;
}

I would like to understand how to create a Breadth-First Search.
Can anyone help me with that?

Thank you in advice

[daviddoria]

Here is the algorithm - it is actually quite short and straight forward:

http://en.wikipedia.org/wiki/Breadth-first_search#Algorithm_.28informal.29