Graph Traversal: BFS and DFS Algorithms

A Refresher on Graph Traversal: BFS vs. DFS

Before we dive into applications, let's quickly recap the two primary ways to explore a graph. Given your background in Information Technology, you've likely implemented these before, so we'll focus on their core characteristics relevant to problem-solving.

• Breadth-First Search (BFS): This traversal explores the graph layer by layer. Starting from a source vertex, it visits all its immediate neighbors first, then the neighbors of those neighbors, and so on. It uses a Queue data structure to manage the order of vertices to visit. A key property of BFS is that in an unweighted graph, it finds the shortest path (in terms of the number of edges) from the source vertex to all other reachable vertices.

• Depth-First Search (DFS): This traversal goes as deep as possible along each branch before backtracking. Starting from a source, it explores an edge, then from the new vertex, it explores another edge, continuing until it hits a dead end (a vertex with no unvisited neighbors). It then backtracks to the previous vertex to explore other paths. DFS is naturally implemented using a Stack, either explicitly or implicitly through recursion (the call stack).

Think of it like exploring a maze:

• BFS is like a team of people starting at the entrance, with each person taking one step down a path, then all of them taking a second step simultaneously. They explore the maze in concentric circles.
• DFS is like one person walking down a path, taking turns at every junction, until they hit a dead end, then walking back to the last junction to try a different path.

Application 1: Finding Connected Components

In an undirected graph, a connected component is a subgraph where there is a path between any two vertices within the component, and which is disconnected from the rest of the graph. A disconnected graph consists of two or more such components.

Finding and counting these components is a classic application of graph traversal. The algorithm is straightforward and works with either BFS or DFS.

1. Initialize a counter for components to zero and an array visited[V] to false for all vertices V.
2. Iterate through each vertex u from 0 to V-1.
3. If visited[u] is false, it means we have found a new, unvisited component.
   • Increment the component counter.
   • Start a traversal (either DFS or BFS) from vertex u. The traversal will visit every vertex in this component and mark them as true in the visited array.
4. After the loop finishes, the counter will hold the total number of connected components.

This process systematically "paints" each component. Every time we need to pick a new starting color (i.e., start a new traversal), we've found a new component.

Application 2: Topological Sorting

Many real-world problems involve dependencies. For example, to take an "Advanced Algorithms" course, you must first complete "Data Structures". This "must be done before" relationship can be modeled using a Directed Acyclic Graph (DAG). A topological sort of a DAG is a linear ordering of its vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering.

A topological sort provides a valid sequence to perform the tasks. For a DAG, multiple valid topological sorts can exist.

The most common way to generate a topological sort is using DFS. The logic is subtle but powerful:

1. Perform a DFS traversal on the graph.
2. For each vertex, once its DFS recursive call is finished (meaning all its descendants have been fully explored), add that vertex to the front of a list or push it onto a stack.
3. After the traversal is complete, the list or the popped elements from the stack will represent a valid topological order.

Why does this work? A vertex u's DFS call only finishes after all its descendants' DFS calls have finished. This means any vertex v that u points to will be placed on the stack/list before u is. When the final list is read, u will naturally appear before v.

The following video provides an excellent visualization of this process.

Application 3: Cycle Detection

Detecting cycles is a critical task in many graph algorithms. The method for detecting a cycle depends on whether the graph is directed or undirected.

Cycle in an Undirected Graph

In an undirected graph, a simple DFS can detect a cycle. During the traversal, for each visited vertex u, we examine its neighbors. If we find a neighbor v that is already visited but is not the parent of u in the DFS tree, we have found a back edge. A back edge in an undirected graph implies a cycle.

The "parent" check is crucial because in an undirected graph, the edge (u, v) means there is also an edge (v, u). When exploring from u, we will find its parent p (from which we arrived at u) is already visited. This is not a cycle; it's just the two-way nature of the edge. Any other visited neighbor indicates a true cycle.

Cycle in a Directed Graph

The parent-check trick doesn't work for directed graphs. We need a more robust method. There are two main approaches:

1. DFS with Three States (Colors)

We can augment our visited array to track three states for each node:

• WHITE: The node has not been visited yet.
• GRAY: The node is currently being visited (it's in the current recursion stack).
• BLACK: The node and all its descendants have been fully visited.

A cycle is detected when the DFS traversal from a node u encounters a neighbor v that is GRAY. A gray node is one we are currently visiting. Finding a path to a node that is already in our current recursion path means we have found a back edge, and thus a cycle.

2. Using Topological Sort (Kahn's Algorithm)

This is a very elegant method often tested in GATE. The logic is based on a fundamental property: A topological sort is only possible for a Directed Acyclic Graph (DAG).

Therefore, if we attempt to perform a topological sort on a graph and fail to include all vertices in the final sorted list, the graph must contain a cycle.

The most common algorithm for this is Kahn's Algorithm, which is BFS-based:

1. Compute the in-degree (number of incoming edges) for every vertex.
2. Initialize a queue with all vertices that have an in-degree of 0.
3. Initialize a counter for visited nodes to 0.
4. While the queue is not empty:
   a. Dequeue a vertex u. Add it to your (conceptual) topological sort list and increment the visited node counter.
   b. For each neighbor v of u:
   i. Decrement the in-degree of v.
   ii. If the in-degree of v becomes 0, enqueue v.
5. After the loop, if the visited_node_counter is less than the total number of vertices in the graph, then the graph has a cycle. The vertices with non-zero in-degrees that were never added to the queue are part of the cycle(s).

This video explains this exact process for cycle detection.

Conclusion

Today we've seen how the fundamental traversal algorithms, BFS and DFS, are not just for visiting nodes, but are powerful tools for solving a variety of graph problems. Understanding how and why they work in these contexts is crucial for your GATE preparation.

Key Takeaways:

• BFS (queue-based, level-order) and DFS (stack-based, depth-first) are the workhorses of graph algorithms.
• Connected components in undirected graphs can be found by repeatedly running BFS or DFS on unvisited nodes.
• Topological Sorting provides a linear ordering for tasks in a DAG and is typically implemented with DFS by adding nodes to a list after their recursive calls complete.
• Cycle detection in an undirected graph can be done with DFS by looking for a visited neighbor that isn't the parent.
• Cycle detection in a directed graph can be done with a 3-color DFS approach or, more elegantly, by checking for a failed topological sort (e.g., via Kahn's algorithm).

In our next lesson, we will build directly on these concepts to tackle some of the most important optimization problems in graph theory: finding Minimum Spanning Trees with Kruskal's and Prim's algorithms, and finding Single-Source Shortest Paths with Dijkstra's algorithm.