Depth-first search
Aim : Program to traverse a graph using DFS
Algorithm:
Step 1: consider that the DFS is beginning from the starting vertex A. Process the vertex A and mark it as visited.
Step 2: Using the adjacency matrix of the graph find the vertex along the path which begins vertex A, that has not been visited yet. Process the vertex and consider this as the new vertex and mark the vertex as visited.
Step 3: Repeat Step 2 using the new search vertex. If no vertices back track to the previous node and continue the search from there.
Step 4: When backtracking to the previous search node in step 3 is impossible, the search from the originally chosen search node is complete.
Step 5: If the graph still contains unvisited nodes, choose any vertex that has not been visited and repeat step 1 to 4.
No comments:
Post a Comment