22.6. Applications of BFS and DFS

We have seen how to use Breadth First and Depth First search to explore whether there is a path from a source to a target vertex. But one can do a lot more with these two procedures.

So, recall that a graph is a set of vertices and a set of edges which have connections between the vertices, and these may be directed or undirected.

BFS (Breadth First Search) and DFS (Depth First Search) are two fundamental algorithms used to explore graphs. While they can determine if a path exists between two vertices, their applications extend further. A graph consists of nodes (vertices) and edges connecting them. These connections can be either directed (one-way) or undirected (two-way). Both BFS and DFS are commonly used to analyze these graph structures.

Think of a graph like a city map, where each intersection is a vertex and each road is an edge. BFS would represent exploring the city block by block, while DFS would mean going down one street as far as you can before switching to a different street.

One fundamental property of undirected graph is whether or not disconnected, can we go from every vertex to every other vertex. So, you can see in these two pictures that the graph on the left is connected...

In an undirected graph, we are often concerned with its connectivity. A graph is connected if there is a path between every pair of vertices. If some vertices cannot be reached from others, the graph is classified as disconnected. By using BFS or DFS, we can identify all the connected components within a disconnected graph, allowing us to determine how many separate groups of vertices exist.

Imagine an island with various villages (vertices). If there's a road (edge) connecting each village, you can travel from one to another. However, if some villages are isolated, you cannot reach them from others unless there’s a bridge (path) connecting them. Using BFS or DFS is like sending a team to explore which villages can be reached from one starting village.

So, at first target is to use BFS or DFS to identify connected components. This is quite easy to do which start with the node label 1 or any other node...

To find connected components in a graph, you can initiate a BFS or DFS from a starting node and mark all reachable nodes as visited. Once you finish exploring from that node, you choose the next unvisited node and repeat the process. Each time you start a new BFS or DFS, you are identifying a new connected component.

Think of exploring a forest where some trees are grouped closely together (connected components). You decide to mark all the trees in one area as visited. After finishing in that area, you move to a new spot where you discover another cluster of trees. Each exploration represents finding a new connected component in the forest.

Another interesting structural property of a graph is whether or not it has cycles. An acyclic graph is a graph such as one on the left, in which you cannot started at any node and follow up sequence of edges and come back to the node...

A cycle in a graph occurs when you can start at a vertex, traverse edges, and return to the same vertex without retracing any edge. A graph without cycles is called acyclic. To find cycles, you can utilize BFS or DFS to track the edges used during exploration. If you encounter an edge to a previously visited vertex, that indicates a cycle exists within the graph.

Imagine winding paths in a park. If you walk along a path and eventually find yourself back at the starting point, you have created a cycle. If there’s a path that leads you around in a circle, like riding a bike around a track, that’s a cycle too. BFS and DFS help you explore these paths systematically.

If we have a graph with n vertices and it is connected and it does not have cycles, then it will have exactly n minus 1 edges, this kind of a graph is called a tree...

A tree is a special type of graph that is both connected and acyclic. In a tree with 'n' vertices, there will always be exactly 'n-1' edges. When performing BFS or DFS in a tree, all edges utilized form what is known as a spanning tree. Any additional edges (non-tree edges) could potentially create cycles.

Consider a family tree. Each person (node) is connected by relationships (edges) with their parents or children. If there’s a relationship where each person can only connect directly to one parent (no cycles), it maintains the structure of a tree. If you tried to introduce a cousin relationship that creates a loop, you’d have a cycle, which isn't allowed in the structure of a basic family tree.

So, this situation with directed graphs is little more complex... in a directed graph we need to follow the edge arrows...

Directed graphs have edges that have a specific direction, represented by arrows, indicating where a connection leads. To explore such graphs while looking for cycles, you must follow the direction of the edges. It’s important to identify different types of edges such as tree edges, back edges, forward edges, and cross edges, which can help denote cycles within the graph.

Think of a one-way street system where traffic can only flow in one direction. If you drive along these one-way streets, you can sometimes find yourself going around in circles (creating cycles). The direction of the streets (edges) dictates where you can and cannot go.

In directed graphs, we say that two nodes are strongly connected, if I can go from i to j by a path and I can come back from j to i...

Strongly connected components (SCC) in directed graphs ensure that each node can reach every other node within that component. By effectively analyzing a directed graph, it can be decomposed into its strongly connected components, allowing us to explore its structure more deeply and efficiently.

Imagine a group of friends who can all visit each other’s houses. If you can go from your house to a friend’s and back again, you are strongly connected. If some friends can’t visit others, you don’t have that strong connecting relationship in the group.

So, we have seen some concrete examples of what you can compute, there are many other properties that you can compute using BFS and DFS...

BFS and DFS are widely used in various applications, such as identifying articulation points and critical edges that can disconnect components of a graph. Understanding these properties helps in the design of robust systems and networks by pinpointing vulnerabilities.

Consider a network of roads in a city. If a major intersection (articulation point) closes, it might block traffic and disconnect parts of the city. Using BFS or DFS, city planners can identify these intersections to implement strategies for rerouting or improving traffic flow.

--