Coder Life
Published in

Coder Life

Breadth First Traversal and Depth First Traversal for Graph

Data Structures and Algorithms Note

The breadth first traversal will go through all vertices level by level. From [level 0] vertex 1 -> [level 1] vertex2, vertex3 -> [level 2] vertex 4, vertex 5 and finally [level 3] vertex6

We could use a queue to implement breadth first traversal, start from vertex1, then we append vertex1’s connected vertices into the queue, then pop the first vertex as well as append its connected vertex into the queue, keep the action till all the vertices are visited.

Time Complexity: O(V+E)
where V is the number of vertices and E is the number of edges in the graph.

result

according to the step of add_edge above, we could get the g will look like:

1->2->3
2->4->5
3->5
4->5->6
5->6

for the breadth first traversal that starts from vertex1, we take the g[1], append the rest of linked vertices to queue, which is vertex2 and vertex3, then pop current queue that we will get vetex2, take the g[2], append the rest of linked vertex4 and vertex5 into the queue, and so on. So that we get the result as 1 2 3 4 5 6.

The depth first traversal will go forward to the depth until there is no further vertex to go, then trackback to the previous vertex check if there any other vertex still not be visited. Keep doing the same action until all the vertices are visited. From vertex 1 -> vertex2 -> vertex4 -> vertex5 -> vertex6, and there is no further vertex, so go back to the previous vertex, stop at vertex1 and go to the last vertex, vertex3.

Time complexity: O(V + E)
where V is the number of vertices and E is the number of edges in the graph.

Space Complexity: O(V)
since an extra visited array of size V is required.

result

according to the step of add_edge above, we could get the g will look like:

1->2->3
2->4->5
3->5
4->5->6
5->6

for the depth first traversal that starts from vertex1, we take the g[1], go to its linked vertex, vertex2, take g[2], go to its linked vertex, vertex4, for the g[4], go to the vertex5, for [g5] go to the vertex6, and it is the end, the deepest vertex of the graph, trace back to the previous vertex and find is there any vertex not been visited, we will find all the vertices are visited except the g[1] vertex3, so we print 3 as the last one we visited. That is why we get the result as 1 2 4 5 6 3.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store