1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Breath-First Search algorithm C++

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

  1. ihatec

    ihatec New Member

    Joined:
    Sep 1, 2010
    Messages:
    20
    Likes Received:
    3
    Trophy Points:
    0
    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