1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

Breath-First Search algorithm C++

Discussion in 'C' started by ihatec, Nov 8, 2010.

  1. ihatec

    ihatec New Member

    I have to implement BFS algorithm for connected and disconnected graphs that returns the order of visited vertices. For connected graph everytihing is ok, but for disconnected one I have to do it in such a way that every vertex is visited also those in other connected components. In each component it should be done in according to BFS. First component start from the vertex start. I tried few things but it didn't work. If somebody could give me some hints, I would be grateful. I have also methods given below.

    int areConnected(int,int)
    Returns:
    1 if given vertices are connected by an egde
    0 if the vertices are not connected
    -1 if the vertices do not exist

    int getVerticesCount()
    Returns number of vertices

    int EdgesCount()
    Returns number of edges

    int getDegree(int)
    Returns:
    degree of the given vertex
    -1 if no such vertex exists.

    list<int>* getNeighbors(int)
    Returns:
    a pointer to the list of neighbors of a given vertex (for isolated vertex list is empty)
    null if no such vertex exists

    Code:
    list<int>  BFS(int start)
    {
            list<int> order; // order of vertices
            bool *visited=new bool[getVerticesCount()];
            queue<int> kolejka;
            for(int i=0;i<getVerticesCount();++i)
            visited[i]=false;
            visited[start]=true;
            kolejka.push(start);
            while(!kolejka.empty())
            {            
                int vertex=kolejka.front();
                kolejka.pop();
                order.push_back(vertex);
                for(int i=0;i<getVerticesCount();++i)
                {    
                    if(i==vertex)
                        continue;
                    if(areConnected(i,vertex)==1)
                    {
                        if(visited[i]==false)
                        {
                            visited[i]=true;
                            kolejka.push(i);
                        }
                    }
                    else 
                        continue;
                }
            }
            delete [] visited;
            visited=NULL;
            return order;
    }
    
     

Share This Page