Graph Traversal Algorithms

# CHAPTER 20

Graph Traversal Algorithms #

1. Introduction #

2. Learning Objectives #

• Identify the catastrophic infinite loop danger of Graph Cycles.

• Implement a global Visited Cache to secure traversal execution.

• Adapt Tree BFS and DFS algorithms to operate within Graph matrices.

• Understand how to handle Disconnected Graph Components.

3. The Visited Array (The Cycle Breaker) #

• Every time the algorithm physically extracts a Node, it flags that Node's ID in the Visited array as True.

• Before the algorithm is allowed to process a neighboring connection, it MUST check the Visited cache. If the neighbor is already flagged as True, the algorithm immediately aborts that path.

4. Graph DFS (Depth-First Search) #

Algorithm Flow:

1. 1. Pick a starting Node. Mark it as Visited.

1. 2. Print/Process the Node.

1. 3. Loop through all its connected neighbors.

1. 4. If a neighbor is NOT in the Visited cache, recursively plunge DFS into that neighbor.

Execution Trace: Graph: A - B - C (where A also connects to C forming a triangle).

1. 1. Start A. Mark Visited=[A]. Print A.

1. 2. A's neighbors are B, C. Go to B.

1. 3. Mark Visited=[A, B]. Print B.

1. 4. B's neighbor is C. Go to C.

1. 5. Mark Visited=[A, B, C]. Print C.

1. 6. C's neighbors are A, B.

1. 7. Check cache: A is visited! Skip! B is visited! Skip!

1. 8. C dead-ends. Recursion unwinds safely!

5. Graph BFS (Breadth-First Search) #

Algorithm Flow:

1. 1. Pick a starting Node. Mark it as Visited immediately, and push it to the Queue.

1. 2. Loop while Queue is not empty.

1. 3. Dequeue the front Node. Process/Print it.

1. 4. Loop through all connected neighbors.

1. 5. If a neighbor is NOT Visited, mark it Visited and push it to the Queue!

6. The "Disconnected Component" Trap #

# The Master Guardian Loop
for node in all_nodes:
    if not visited[node]:
        execute_DFS(node) # Only launches if the node hasn't been touched yet!

*This guarantees that if the graph is fractured into 5 disconnected islands, the engine will restart 5 separate times, successfully scanning the entire database.*

7. Complexity Analysis #

• Time Complexity: $O(V + E)$. The engine evaluates every discrete Vertex exactly once (due to the Visited array) and sweeps every connected Edge loop exactly once.

• Space Complexity: $O(V)$. You must allocate the Visited tracking Array to match the total number of Vertices, plus the recursion Stack or BFS Queue sizing.

8. Python Code Execution (Graph DFS) #

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited = set() # O(1) Lookup Cache

def dfs(node):
    if node not in visited:
        print(node, end=" ") # Process
        visited.add(node)    # Mark as Visited
        
        # Aggressively plunge into all neighbors
        for neighbor in graph[node]:
            dfs(neighbor)

# Initiate Search
dfs('A')

9. Exercises #

1. 1. If Graph BFS utilizes a FIFO Queue and Graph DFS utilizes a LIFO Stack, theoretically explain which algorithm is better suited for tracing a complex maze to find the absolute shortest exit path.

1. 2. Trace the exact Visited array state at every recursion step if the provided Python code executes a DFS search on the graph starting at Node C.

10. MCQs with Answers #

11. Interview Preparation #

• *Algorithmic Edge Testing:* "You wrote a DFS algorithm that finds a path from City A to City B. An interviewer points out that if City A is completely isolated with no edges, your code crashes. How do you fix it?" *(Answer: The classic Disconnected Component error! Before executing the recursive DFS call, I must wrap it in a global iteration loop validating the Visited cache state across the entire vertex master list!)*

12. Summary #

13. Next Chapter Recommendation #