Scribd
Upload
27 views3 pages

DFS Algorithm for Graph Traversal

The document outlines a Depth-First Search (DFS) algorithm using a stack to traverse a graph, starting from node 1. It provides a step-by-step trace of the algorithm applied to a specific graph, detailing the stack's state, visited nodes, and printed nodes at each step. The final DFS traversal order is 1 → 3 → 4 → 5 → 2.

Uploaded by

hasinipragnyamargani
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
27 views3 pages

DFS Algorithm for Graph Traversal

The document outlines a Depth-First Search (DFS) algorithm using a stack to traverse a graph, starting from node 1. It provides a step-by-step trace of the algorithm applied to a specific graph, detailing the stack's state, visited nodes, and printed nodes at each step. The final DFS traversal order is 1 → 3 → 4 → 5 → 2.

Uploaded by

hasinipragnyamargani
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Write a DFS algorithm to traverse a graph. Apply the same algorithm for the graph given in Fig.

1 by
considering node 1 as the starting node.

1
/\
2 3
\/
4
|
5

DFS Algorithm
Algorithm DFS_Stack(Graph G, Node start)

1. let stack ← empty stack // Initialize an empty stack to manage nodes

2. let visited ← empty set // Initialize an empty set to keep track of visited nodes

3. push start onto stack // Start the DFS from the 'start' node

4. while stack is not empty do // Continue until there are no more nodes to visit

5. node ← pop from stack // Take the top node from the stack

6. if node ∉ visited then // If this node has not been visited yet

7. print node // Process the node (e.g., print or record it)

8. visited ← visited ∪ {node} // Mark the node as visited to avoid revisiting

9. for each neighbor u of node in Adjacent[node] do // Explore all neighbors of node

10. if u ∉ visited then // If the neighbor hasn't been visited

11. push u onto stack // Push it onto the stack for future exploration

12. end if

13. end for


14. end if

15. end while // When stack is empty, all reachable nodes have been visited

Step-by-step trace for the example graph, starting from node


1:
Graph adjacency:

 1 → [2, 3]
 2 → [1, 4]
 3 → [1, 4]
 4 → [2, 3, 5]
 5 → [4]

Iteration Table with Comments


Stack (top on Pop Visited After Printed
Step Explanation/Comments
right) Node Step Node

Start by popping 1 from stack, mark as


1 [1] 1 {1} 1
visited, print it

Push neighbors 2 and 3 onto stack

2 [2, 3] 3 {1, 3} 3 Pop 3, mark visited, print

Push neighbors 1 and 4; 1 already visited,


skip; push 4

3 [2, 4] 4 {1, 3, 4} 4 Pop 4, mark visited, print

Push neighbors 2, 3, 5; 2 and 3 already


visited, push 5

4 [2, 5] 5 {1, 3, 4, 5} 5 Pop 5, mark visited, print

Push neighbor 4; already visited, skip

5 [2] 2 {1, 2, 3, 4, 5} 2 Pop 2, mark visited, print

Push neighbors 1 and 4; both visited, skip

6 [] — {1, 2, 3, 4, 5} — Stack empty → traversal complete


Stack (top on Pop Visited After Printed
Step Explanation/Comments
right) Node Step Node

Final DFS traversal order with stack:


1 → 3 → 4 → 5 → 2

Summary of the iterative DFS:

 The stack manages which nodes to visit next, always taking the last inserted (LIFO).
 Visited nodes are tracked to avoid revisiting and infinite loops.
 Each node is printed when first popped from the stack and marked visited.
 Neighbors are pushed onto the stack in order, which influences the traversal path.

You might also like