DSA Graphs Traversal
Graphs Traversal
A graph can be traversed by beginning at one vertex, visiting additional vertices by following the edges, and continuing until all vertices, or as many as possible, have been visited.
==== EXAM MUKAVU ====
Comprehending the traversal mechanism of a graph is crucial to comprehending the operation of algorithms operating on graphs.
There are two primary methods for traversing a graph:
- Depth First Search (DFS)
- Breadth First Search (BFS)
While BFS is typically done using a Queue, DFS is typically implemented using a Stack or by employing recursion, which makes use of the call stack.
Functions are kept operating in the proper order via the Call Stack.
FunctionB is positioned at the top of the call stack and begins to operate, for instance, if FunctionA calls FunctionB. FunctionB is eliminated from the stack after it is completed, and FunctionA then gets back to work.
Depth First Search Traversal
Because it visits a vertex, its neighboring vertices, that vertex’s neighbor vertex, and so on, Depth First Search is considered to go “deep” because each recursive repetition increases the distance from the beginning vertex.
How it works:
1.Start DFS traversal on a vertex.
2.Do a recursive DFS traversal on each of the adjacent vertices as long as they are not already visited.
Try the following animation to show how the Depth First Search (DFS) traversal works on a particular graph, beginning at vertex D (this animation is identical to the previous one).
==== EXAM MUKAVU ====
Vertex D is where the DFS traversal begins, and it identifies vertex D as visited. The traversal procedure is then called recursively on all neighboring vertices that have not yet been visited for each new vertex that is visited. Vertex C or E, depending on the implementation, is the next vertex where the traversal continues after vertex A is reached in the animation above.
Example
Python:
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
def dfs_util(self, v, visited):
visited[v] = True
print(self.vertex_data[v], end=' ')
for i in range(self.size):
if self.adj_matrix[v][i] == 1 and not visited[i]:
self.dfs_util(i, visited)
def dfs(self, start_vertex_data):
visited = [False] * self.size
start_vertex = self.vertex_data.index(start_vertex_data)
self.dfs_util(start_vertex, visited)
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0) # D - A
g.add_edge(0, 2) # A - C
g.add_edge(0, 3) # A - D
g.add_edge(0, 4) # A - E
g.add_edge(4, 2) # E - C
g.add_edge(2, 5) # C - F
g.add_edge(2, 1) # C - B
g.add_edge(2, 6) # C - G
g.add_edge(1, 5) # B - F
g.print_graph()
print("\nDepth First Search starting from vertex D:")
g.dfs('D')
Line 60: Calling the dfs() function initiates the DFS traversal.
Line 33: Since no vertices have yet been visited, the visited array is initially set to false for every vertex.
Line 35: The dfs_util() method receives the visited array as an input. The visited array is not the actual array containing the data when it is supplied as an input to the dfs_util() function; rather, it is merely a reference to the visited array. Thus, in our program, there is only ever one visited array, and as nodes are visited, the dfs_util() method can modify it (line 25).
Lines 28–30: If the neighboring nodes are not already visited, all of them are called recursively for the current vertex, v.
Breadth First Search Traversal
Before moving on to surrounding vertices, the Breadth First Search examines all of a vertex’s neighboring vertices. In other words, vertices that are equally far from the initial vertex are visited before vertices that are farther away are visited.
How it works:
1.Add the initial vertices to the queue
2.Visit each vertex that is removed from the queue, and then add all of the neighboring vertices that have not yet been visited to the queue.
3.As long as there are vertices in the queue, keep going.
See how the Breadth First Search (BFS) traversal functions on a particular graph, starting at vertex D, by watching the animation below.
==== EXAM MUKAVU ====
The video above illustrates how BFS traversal visits vertices that are the same distance from the initial vertex before moving on to vertices that are farther away. Because vertex E and C are farther away, they are visited before vertices B, F, and G, for instance, after vertex A.
In order to traverse a breadth first, all nearby vertices are first placed in a queue (if they haven’t been visited), and then the next vertex in the queue is visited using the queue.
With the exception of the bfs() method, this code sample for the Breadth First Search traversal is identical to the Depth First Search code example above:
Example
Python:
def bfs(self, start_vertex_data):
queue = [self.vertex_data.index(start_vertex_data)]
visited = [False] * self.size
visited[queue[0]] = True
while queue:
current_vertex = queue.pop(0)
print(self.vertex_data[current_vertex], end=' ')
for i in range(self.size):
if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
Line 2-4: To begin, the bfs() method creates a queue containing the start vertex, sets the start vertex as visited, and creates a visited array.
Lines 6–13: In order for the BFS traversal to function, a vertex must be taken from the queue, printed, and any neighboring vertices that have not yet been visited must be added to the queue. The process then proceeds to take vertices from the queue in this manner. When there are no more unexplored nearby vertices for the final piece in the queue, the traversal is complete.
DFS and BFS Traversal of a Directed Graph
With only few modifications, depth first and breadth first traversals can be made to operate on directed graphs rather than undirected ones.
See how to use DFS or BFS to traverse a directed graph by running the animation below.
==== EXAM MUKAVU ====
We only need to delete the final line of the add_edge() method in order to switch from traversing an undirected graph to a directed graph:
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1The fact that the edges are now directed means we need to be careful when creating our graph.
The directed graph from the animation above is traversed using both BFS and DFS in the code example below:
Example
Python:
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
#self.adj_matrix[v][u] = 1
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
def dfs_util(self, v, visited):
visited[v] = True
print(self.vertex_data[v], end=' ')
for i in range(self.size):
if self.adj_matrix[v][i] == 1 and not visited[i]:
self.dfs_util(i, visited)
def dfs(self, start_vertex_data):
visited = [False] * self.size
start_vertex = self.vertex_data.index(start_vertex_data)
self.dfs_util(start_vertex, visited)
def bfs(self, start_vertex_data):
queue = [self.vertex_data.index(start_vertex_data)]
visited = [False] * self.size
visited[queue[0]] = True
while queue:
current_vertex = queue.pop(0)
print(self.vertex_data[current_vertex], end=' ')
for i in range(self.size):
if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0) # D -> A
g.add_edge(3, 4) # D -> E
g.add_edge(4, 0) # E -> A
g.add_edge(0, 2) # A -> C
g.add_edge(2, 5) # C -> F
g.add_edge(2, 6) # C -> G
g.add_edge(5, 1) # F -> B
g.add_edge(1, 2) # B -> C
g.print_graph()
print("\nDepth First Search starting from vertex D:")
g.dfs('D')
print("\n\nBreadth First Search starting from vertex D:")
g.bfs('D')
After examining two fundamental algorithms for navigating graphs, we will use the next pages to examine the capabilities of the Graph data structure for executing other algorithms.
