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

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice