Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Breath-First Search algorithm C++ (http://www.go4expert.com/forums/breath-search-algorithm-cpp-t23796/)

 ihatec 8Nov2010 16:14

Breath-First Search algorithm C++

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; }```

 All times are GMT +5.5. The time now is 18:14.