Breadth First Traversal and Depth First Traversal for Graph
Data Structures and Algorithms Note
Breadth First Traversal
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.
from collections import defaultdict
# This Graph class using adjacency list representation
class Graph:
def __init__(self):
# default dictionary to store graph
self.graph = defaultdict(list)
# function to add an edge to graph
def add_edge(self,u,v):
self.graph[u].append(v)
# Function to print a BFS of graph
def BFS(self, v):
# Mark all the vertices as not visited
visited = set()
# Create a queue for BFS
queue = []
# Mark the start node as
# visited and enqueue it
queue.append(v)
visited.add(v)
while queue:
# Dequeue a vertex from
# queue and print it
v= queue.pop(0)
print(v)
# Get all adjacent vertices of the dequeued vertex v.
# If a adjacent has not been visited,
# then mark it visited and enqueue it
for i in self.graph[v]:
if i not in visited:
queue.append(i)
visited.add(i)Time Complexity: O(V+E)
where V is the number of vertices and E is the number of edges in the graph.
result
# Create a graph given in the above diagram
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 5)
g.add_edge(4, 5)
g.add_edge(4, 6)
g.add_edge(5, 6)
print ("Following is Breadth First Traversal starting from vertex1:")
g.BFS(1)
-----------------------------------------
Following is Breadth First Traversal starting from vertex1:
1
2
3
4
5
6another way to think
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.
Depth First Traversal
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.
from collections import defaultdict
# This Graph class using adjacency list representation
class Graph:
def __init__(self):
# default dictionary to store graph
self.graph = defaultdict(list)
# function to add an edge to graph
def add_edge(self,u,v):
self.graph[u].append(v)
def DFSUtil(self, v, visited):
# Mark the current node as visited and print it
visited.add(v)
print(v)
# recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
if i not in visited:
self.DFSUtil(i, visited)
def DFS(self, v):
# create a set to store all visited vertices
visited = set()
# call the recursive helper function to print DFS traversal
self.DFSUtil(v, visited)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
# Create a graph given in the above diagram
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 5)
g.add_edge(4, 5)
g.add_edge(4, 6)
g.add_edge(5, 6)
print ("Following is Breadth First Traversal starting from vertex1:")
g.DFS(1)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Following is Breadth First Traversal starting from vertex1:
1
2
4
5
6
3another way to think
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.
