0
1.6kviews
Graph Traversal Technique
0
16views
1. Graphs can be traverse in two ways

b. DFS(Depth First Search)

2. BFS

1.Breadth-first search starts at a given vertex āSā, which is at level 0.

2.In the first stage, we visit all the vertices that are at the distance of one edge away.

3.When we visit there, we mark them as "visited," the vertices adjacent to the start vertex s - these vertices are placed into level 1.

4.In the second stage, we visit all the new vertices we can reach at the distance of two edges away from the source vertex āSā. These new vertices, which are adjacent to level 1 vertices and not previously assigned to a level, are placed into level 2, and so on.

5.The BFS traversal terminates when every vertex has been visited.

3. DFS

1.Depth First Search is like pre-order traversal of tree.

2.DFS can be started from any vertex and it continuous recursively until all nodes are visited.

3.After visiting a node it is marked as visited so as to avoid re-visiting the same node and avoid cycles.

4.Marking of nodes can be done by using a global array visited[] which is initialed to 0.

5.Similarly all the remaining vertices are traversed.

4. Consider the example

BFS will visit the nodes in the following order: A, B, C, E, D, F, G.
DFS will visit the nodes in the following order: A, B, D, F, E, C, G.