After BFS has visited initial vertex v, it visits every neighbor vertex W1, W2,..., W then again it visits all neighbor vertexes of Wi, W2,..., wo which has not been visited yet And starting from these vertexes, it visits their neighbors that havent been visited.. Keep doing this until all the vertexes in the graph have been visited. BFS is an layered search process, in which you can visit a batch of vertexes in each step. Different from DFS, there isnt backward steps So BFS is not a recursive process
◼ After BFS has visited initial vertex v, it visits every neighbor vertex w1 , w2 , …, wt , then again it visits all neighbor vertexes of w1 , w2 , …, wt , which has not been visited yet. And starting from these vertexes, it visits their neighbors that haven’t been visited…. Keep doing this until all the vertexes in the graph have been visited. BFS is an layered search process, in which you can visit a batch of vertexes in each step. Different from DFS, there isn’t backward steps. So BFS is not a recursive process
In order to implement layered visit, the algorithm uses a queue to record vertexes in the current layer being visited and also in the following layer which is convenient for the following visit. To avoid repeat visits, we need an accessorial array visited I, which marks vertexes that have been visited. Breath First Search algorithm of graph void Graph Traverse(AdjGraph G)i for( int i=0; i< G n; i++) if(! visited[i]) BFS (G, i, visited ) ●●。●●●●●
◼ In order to implement layered visit, the algorithm uses a queue to record vertexes in the current layer being visited and also in the following layer which is convenient for the following visit. ◼ To avoid repeat visits, we need an accessorial array visited [ ], which marks vertexes that have been visited. Breath First Search algorithm of graph void Graph_Traverse (AdjGraph G) { ‥‥‥‥‥ for ( int i = 0; i < G.n; i++ ) if ( ! visited[i] ) BFS (G, i, visited ); ‥‥‥‥‥ }
void BFS (AdjGraph G, int v, int visited[1)i cout < GetValue(v)<< visited[v]=1; Queue<int> g: InitQueue &a; EnQueue&q,V)/进队列 while(! QueueEmpty(&q)){/队空搜索结束 DeQueue(&q, v); int w= Get FirstNeighbor(G, v); while(W!=-1){/若邻接顶点w存在 if(! visited[w]){/未访问过 cout < GetValue(w)<<
void BFS (AdjGraph G, int v, int visited[ ] ) { cout << GetValue (v) << ' '; visited[v] = 1; Queue<int> q; InitQueue(&q); EnQueue (&q, v); //进队列 while ( ! QueueEmpty (&q) ) { //队空搜索结束 DeQueue (&q, v); int w = GetFirstNeighbor (G, v); while ( w != -1 ) { //若邻接顶点 w 存在 if ( !visited[w] ) { //未访问过 cout << GetValue (w) << ‘ ’;
visited[w]= 1; EnQueue( &q, w); W=GetNextNeighbor(G, v, w)i }/重复检测v的所有邻接顶点 }/外层循环,判队列空否 delete [l visited;
visited[w] = 1; EnQueue (&q, w); } w = GetNextNeighbor (G, v, w); } //重复检测 v 的所有邻接顶点 } //外层循环，判队列空否 delete [ ] visited; }
Connectivity problem of graph Connected component When an undirected graph is an unconnected one, if we start from a certain vertex and use des or bes it is not possible to visit all the vertexes. We can only visit all the vertexes in the biggest connected sub-graph(connected component) If we start from a vertex of each connected component, we can get all the connected component in undirected graph
Connected component ◼ When an undirected graph is an unconnected one, if we start from a certain vertex and use DFS or BFS, it is not possible to visit all the vertexes. We can only visit all the vertexes in the biggest connected sub-graph (connected component) 。 ◼ If we start from a vertex of each connected component, we can get all the connected component in undirected graph. Connectivity problem of graph