DFS (Depth First Search The process of Depth First Search A 2~ 3 2 B AB 3E 7(D C5(G4 C)5(G)4 6(F 6(F①(D 8 9 8 9 forward Tree of Depth First Search backward
DFS ( Depth First Search ) ◼ The process of Depth First Search 6 7 A D C E G B F H I A D C E G B F H I 1 2 3 5 4 8 9 1 2 3 5 4 6 7 8 9 forward backward Tree of Depth First Search
After visiting certain initial vertex v in the graph, DFS viSits one of its neighbor vertexes Wi, then start from Wi,it visits one of the neighbor vertexes of w, that has not been visited yet; then again start from W2,-.. keep visiting with the same rule until it arrives at the vertex u, all of whose neighbors have been visited. Then go back to the vertex that has just been visited and see if there are any other connected vertexes that have not been visited. If there is, visit it, then start form this vertex, keep visiting as before. If there isnt, go back another step to search. Repeat the process until all vertexes in the connected graph have been visited
◼ After visiting certain initial vertex v in the graph, DFS visits one of its neighbor vertexes w1 , then start from w1 ,it visits one of the neighbor vertexes of w1 that has not been visited yet; then again start from w2 ,……keep visiting with the same rule until it arrives at the vertex u, all of whose neighbors have been visited. Then go back to the vertex that has just been visited and see if there are any other connected vertexes that have not been visited. If there is, visit it, then start form this vertex, keep visiting as before. If there isn’t, go back another step to search. Repeat the process until all vertexes in the connected graph have been visited
arithmetic of Depth First Search void Graph Traverse(AdjGraph g) int visited -new int Num Vertices; for( int i=0; i< Gn; i++) visited i=0; //The original status of visited [ for(int i=0;i<Gn; i++) if ( visited)DFS (G, i, visited ) //start from vertex i delete l visited; //delete visited
arithmetic of Depth First Search void Graph_Traverse (AdjGraph G) { int * visited = new int [NumVertices]; for ( int i = 0; i < G.n; i++ ) visited [i] = 0; // The original status of visited [ ] for ( int i = 0; i < G.n; i++ ) if ( ! visited[i] ) DFS (G, i, visited ); //start from vertex i delete [ ] visited; //delete visited }
void DFS (AdjGraph G, int v, int visited [l)i cout < GetValueG, v)<<i//visit vertex v visited[v]= 1; //sign the vertex int w= GetFirstNeighbor(G, v) //get v's first adjacent vertex named w while(w! =-1t //if w exist if(!visited[w])DS (G, w, visited )B //if w haven't be visited, visit it w=GetNextNeighbor (G, v,w ); //get w
void DFS (AdjGraph G, int v, int visited [ ] ) { cout << GetValue (G, v) << ‘ ’; //visit vertex v visited[v] = 1; //sign the vertex int w = GetFirstNeighbor (G, v); //get v’s first adjacent vertex named w while ( w != -1 ) { //if w exist if ( !visited[w] ) DFS (G, w, visited ); //if w haven’t be visited, visit it w = GetNextNeighbor (G, v, w ); //get w } }
BFS( Breadth First Search The process of Breadth First Search 5 2 5 A B E B E 4①D)C3G7 4(D C3G7 6(F 6(F 8 9 8 9 tree of breadth first search
BFS ( Breadth First Search ) ◼ The process of Breadth First Search A D C E G B F H I A D C E G B F H 1 2 4 3 5 6 7 8 9 1 2 4 3 5 6 7 8 9 tree of Breadth First Search I