Ques.Write a program to implement Depth first traversal of graphs represented using adjacency matrix and list.
Answer :
Depth-first search(DFS) : DFS is traversing or searching tree or graph data structures algorithm. The algorithm starts at the root node and explores as far as possible or we find the goal node or the node which has no children. It then backtracks from the dead end towards the most recent node that is yet to be completely unexplored. DFS uses Depth wise searching . DFS data structure uses stack . In DFS, the edges that leads to an unvisited node are called discovery edges while the edges that leads to an already visited node are called block edges.
Steps for searching :
- Push the root node in the Stack.
- Loop until stack is empty.
- Peek the node of the stack.
- If the node has unvisited child nodes, get the unvisited child node, mark it as traversed and push it on stack.
- If the node does not have any unvisited child nodes, pop the node from the stack.
Adjacency Matrix : It is a two dimensional array with Boolean flags. As an example, we can represent the edges for the above graph using the following adjacency matrix.
- n by n matrix, where n is number of vertices
- A[m,n] = 1 iff (m,n) is an edge, or 0 otherwise
- For weighted graph: A[m,n] = w (weight of edge), or positive infinity otherwise
Advantages of Adjacency Matrix
- Adjacency matrix representation of graph is very simple to implement.
- Adding or removing time of an edge can be done in O(1) time. Same time is required to check, if there is an edge between two vertices.
- It is very convenient and simple to program.
Disadvantages of Adjacency Matrix
- It consumes huge amount of memory for storing big graphs.
- It requires huge efforts for adding or removing a vertex. If you are constructing a graph in dynamic structure, adjacency matrix is quite slow for big graphs.
Example :
from the above graph the path is 0----->1----->2----->3----->4
Program :
|
def dfs_recursive(graph, vertex, path=[]):
path += [vertex]
for neighbor in graph[vertex]:
if neighbor not in path:
path = dfs_recursive(graph, neighbor, path)
return path
adjacency_matrix = {1: [2, 3], 2: [4, 5],
3: [5], 4: [6], 5: [6],
6: [7], 7: []}
print(dfs_recursive(adjacency_matrix, 1))
|
Output : [1, 2, 4, 6, 7, 5, 3]
For more Rajasthan Technical University CSE-III Sem DSA Lab Experiments CLICK HERE
| 
| 
