Depth First Search (BFS) is a recursive graph traversal algorithm that is used to traverse all the vertices of a graph in a depthward motion. In other words, it starts the graph traversal from root node and explores all the branches.
Depth First Traversal is used to traverse all the vertices of a graph. Using this algorithm, traversal is done in a depthward motion.
Below is the example of DFS Traversal with input- output constraint and the solution for the example.
Given the undirected, connected and unweighted graph G, and the task is used to traverse all the vertices of a graph using DFS Traversal starting from 0.
Output:
Depth First Traversal from vertex 0 is 0 1 3 2.
Visited:
0
Nxt_Vertex:
1
3
2
Visited:
0
1
Nxt_Vertex:
3
2
Visited:
0
1
3
Nxt_Vertex:
2
Visited:
0
1
3
2
Nxt_Vertex :
Here’s pseudocode to traverse all the vertices of a graph using DFS Traversal.
Depth_First_Traversal(G, root):
root is visited
for all edges from v to w in G.adjacentEdges(v) do
if w is not visited then
call Depth_First_Traversal(G, w)
def Depth_First_Traversal(Graph, vertex, visited=None):
if visited is None:
visited = set()
visited.add(vertex)
print(str(vertex) + " ", end="")
for next_vertex in Graph[vertex] - visited:
if next_vertex not in visited:
Depth_First_Traversal(Graph, next_vertex, visited)
return visited
if __name__ == '__main__':
Graph = {0: set([1, 3]), 1: set([3]), 2: set([1]), 3: set([1, 2])}
print("Depth First Traversal: ")
Depth_First_Traversal(Graph, 0)