[darealmzm]

Hello I'm new to program breadth first search and for my assignment we have to implement a breadth first search graph and output the order of the traversal. The problem is when I run my program I do not get any output from my traversal. All I get is "Breadth First Search Traversal starts at Vertex 2 and the order is: " Could someone please show me where I went wrong?

Here is my Queue class

//Declaration of node

struct node{
    int info;
    node *next;
};


//Defining Queue class

class Queue{
public:
    Queue();
    ~Queue();
    bool isEmpty();
    void add(int);
    int get();
private:
    node *first, *last;
};

//Method implementation of Queue
//Constructor

Queue::Queue(){
    
    first = new node;
    first->next = NULL;
    last = first;
}

//Destructor
Queue::~Queue(){
    delete first;
}

//Check if a queue is empty

bool Queue::isEmpty(){
    return(first->next==NULL);
}

//Add a new value x to the queue
void Queue::add(int x){
    node *tmp = new node;
    tmp->info= x;
    tmp->next= NULL;
    last->next=tmp;
    last = tmp;

}

//Get and  remove the first value in the queue
int Queue::get(){
    node *tmp = first->next;
    int value = tmp->info;
    first->next = tmp->next;
    if(last ==tmp)last = first;
    delete tmp;
    return value;
}
 

Here's my graph class

// Define Graph Class

class Graph{
public:
    Graph(int size =2);
    ~Graph();
    bool isConnected(int,int);
    void addEdge(int x,int y);
    void BFS(int x);
private:
    int n; //number of vertices
    int **A; //adjacency matrix
};

//Method implementation of Graph
//Constructor, to create a graph with a specific number of ("size") vertices
Graph::Graph(int size){
    int i,j;
    if(size <2) n=2;
    else n = size;
    A = new int*[n];
    for(i=0;i<n;++i)
      A[i] = new int[n];
    for(i=0;i<n;++i)
      for(j=0; j<n;++j)
	A[i][j]=0;
    
}

//Destructor
Graph::~Graph(){
    for(int i=0; i <n; ++i)
        delete [] A[i];
    delete [] A;
    
}

bool Graph::isConnected(int x, int y){
    return (A[x-1][y-1]==1);
}

//add (x,y) pair to the edge set

void Graph::addEdge(int x, int y){
    A[x-1][y-1] = A[y-1][x-1] =1;
}

//Performs Breadth first search starting with vertex x

void Graph::BFS(int x){
    
    Queue Q;
    
    //Keeps track of visited vertices
    bool *visited = new bool[n+1];
    
    //Initializes all vertices as unvisted
    for (int i =1; i<=n; ++i)
        visited[i] = false;
    
    //Pushes initial vertex onto queue
    Q.add(x);
    
    visited[x] = true; //marks x as visited
    
    //Checks if queue is empty
    while(!Q.isEmpty()){
        //Pops queue from vertex
        int y = Q.get();
	 cout << y<< " ";
    
    
        //Explores all connected vertices
        for (int z=1;z<=n; ++z)
            if(isConnected(y,z) && !visited[z]){
                Q.add(z);//adds vertex z to queue
                visited[z] = true; //marks q as visited
        }
    }
    //  cout <<endl;
    // delete [] visited;
}

Here's my main function.

int main(int argc, const char * argv[])
{

    Graph g(5);
    
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 5);
    g.addEdge(4, 5);
    
    cout << "Breadth First Search Traversal starts at Vertex 2, and the order is: \n";
    g.BFS(2);
    return 0;
}

[Skydiver]

Have you traced into Queue::isEmpty() and Queue::get() to make sure that it is correctly detecting that the queue is not empty and that you can get the value at the front of the queue?

As an aside, if you are doing this assignment for a graph theory class, why are you rolling your own queue class when the standard library already has one pre-made for you? If this is for a data structures class, then I can possibly see a reason why you have to roll your own queue, but if that is the case why not make the assignment simply about queues?

[darealmzm]

Thank you I figured out what the problem turns out I needed a cout in my BFS method. I don't know why my professor told us to do it this way, but that's what she told us to do.

This post has been edited by Skydiver: 26 March 2014 - 09:04 PM
Reason for edit:: Removed unnecessary quote. No need to quote the message above yours.

[Skydiver]

... but you already had a cout << y on line 70 of your graph class in the code you posted above. That's why I was wondering if you verified that the code was making it that far and if you were getting reasonable values.

[darealmzm]

After I went through and checked to see if my values where actually looping and moved my cout statement from line 70 where it's empty to where x is visited, everything works and I got the necessary output for my test case.