Graph Traversals
Like trees traversal algorithms (Inorder, Preorder, Postorder and Level-Order traversals), graph search algorithms can be thought of as starting at some source vertex in a graph and “searching” the graph by going through the edges and marking the vertices. Now, we will discuss two such algorithms for traversing the graphs.
Graph traversal means visiting every vertex and edge exactly once in a well-defined order. While using certain graph algorithms, you must ensure that each vertex of the graph is visited exactly once.
The order in which the vertices are visited are important and may depend upon the algorithm or question that you are solving.
During a traversal, it is important that you track which vertices have been visited. The most common way of tracking vertices is to mark them.
Breadth First Search BFS
There are many other ways to travel the graph but most common and easy way to travel in graph is BFS . In this algorithm you start travelling from a selected node or called as source and then move to its neighbor .
As we traveled a node in graph we use to mark them by color or boolean values so that we can avoid travelling the same vertex again and again .
To make this process easy, use a queue to store the node and mark it as ‘visited’ until all its neighbors (vertices that are directly connected to it) are marked. The queue follows the First In First Out (FIFO) queuing method, and therefore, the neighbors of the node will be visited in the order in which they were inserted in the node i.e. the node that was inserted first will be visited first, and so on.
Code Implementation of BFS
class BFS:
def __init__(self, n):
self.dist = [0]*n
self.pred = [-1]*n
self.colors = ['white']*n
self.graph = {0:[1], 1:[0, 2], 2: [1, 3],
3: [2, 4, 5], 4: [3, 5, 7], 5: [3, 4, 6, 7], 6: [5, 7], 7:[4, 5, 6]}
#this is a graph using dic
def bfs(self, source):
queue = []
queue.append(source)
self.dist[source] = 0
self.colors[source] = 'Gray'
while queue:
current = queue.pop(0)
print("Vertex {}".format(current))
for i in range(len(self.graph[current])):
if self.colors[self.graph[current][i]] == "white":
self.colors[self.graph[current][i]] = 'Gray'
self.dist[self.graph[current][i]] = self.dist[current] + 1
self.pred[self.graph[current][i]] = current
queue.append(self.graph[current][i])
self.colors[current] = 'Black'instance = BFS(8)
instance.bfs(2)
Application of BFS
- Finding all connected components in a graph
- Finding all nodes within one connected component
- Finding the shortest path between two nodes
- Testing a graph for bipartiteness
Depth First Traversal DFS
It is a recursive algorithm that uses the idea of backtracking . or by backtracking . Since it is using recursion means they use stack implicitly and can be done illiterately using stack explicitly .
We can mark visited vertices by boolean or colored .
Code Implementation of DFS
from collections import defaultdict
class DFS:
def __init__(self, n):
self.V = n
self.colors = ['white']*n
self.start_time = [0]*n
self.end_time = [0]*n
self.graph = defaultdict(list)
#created a graph using dic
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs_visit(self, u):
self.time += 1
self.start_time[u] = self.time
self.colors[u] = 'Gray'
print(u)
for i in self.graph[u]:
if self.colors[i] == 'white':
self.dfs_visit(i)
self.time += 1
self.end_time[u] = self.time
self.colors[u] = 'Black'
def dfs(self):
for i in range(self.V):
self.time = 0
if self.colors[i] == 'white':
self.dfs_visit(i)
print(self.start_time)
print(self.end_time)
d = DFS(6)
d.add_edge(0, 1)
d.add_edge(0, 2)
d.add_edge(1, 2)
d.add_edge(2, 3)
d.add_edge(3, 1)
d.add_edge(4, 3)
d.add_edge(4, 5)
d.add_edge(5, 5)
d.dfs()Applications of DFS
- Topological sorting
- Finding connected components
- Finding articulation points (cut vertices) of the graph
- Finding strongly connected components
- Solving puzzles such as mazes
There are some edges found in DFS :
- Tree edge: It is an edge which is present in the tree obtained after applying DFS on the graph. All the Green edges are tree edges.
- Back edge: It is an edge (u, v) such that v is ancestor of edge u but not part of DFS tree. Edge from 6 to 2 is a back edge.
- Forward edge: It is an edge (u, v) such that v is descendant but not part of the DFS tree. Edge from 1 to 8 is a forward edge.
- Cross edge: It is a edge which connects two node such that they do not have any ancestor and a descendant relationship between them. Edge from node 5 to 4 is cross edge.
Sources
My LinkedIn :- linkedin.com/in/my-pro-file
Topics You may Interested IN :
- Connectivity in Graph :- https://medium.com/@mdcode2021/connectivity-in-graph-e3bf2f5ce09f
- Representation of Graph and Intro to it : https://medium.com/@mdcode2021/representation-and-introduction-of-graph-dfb232a1ae2e
- BST , Tree : https://medium.com/dev-genius/trees-binary-search-trees-and-traversal-ab63e192f3a7
