3.2 Graph Connectivity and Graph Traversal

This section aims at answering the question of if there is a path from a node s to another node t, where s and t are node in a graph G=(V,E). The problem is called “determining s-t connectivity”. Although it can be pretty easy to answer this problem for small graphs, it become more painful for reasonably sized graph. That's why we need a more elegant and efficient way to solve the problem in case we have a fairly big graph. Breadth-First Search and Depth-First algorithms are the most efficient algorithms commonly used to solve this problem.

Using this method, we explore outward from the the (root) node s in all possible directions, going one layer at a time.

• L₀ is the set consisting of just the node s
• L₁ consists of all nodes neighbors of s
• Assuming L₁,…,L_j are defined, L_j+1 consists of all nodes that do not belong to an earlier layer and have an edge to an earlier layer L_j
• For each j≥ 1, layer L_j produced by BFS consists of all nodes at distance exactly j from s. There is a path from s to t if and only if t appears in some layer.
• BFS produces a tree T rooted at s on the set of nodes reachable from s.
• For a BFS tree T, if x and y are nodes in T belonging to layers L_i and L_j respectively, and if (x,y) is an edge of G, then i and j differ by at most 1
• The set of nodes discovered by the BFS algorithm is exactly those reachable from the starting node s: this set R is called the set of connected component of G containing s.

Brief sketch:

R* = set of connected components (a set of sets) while there is a node that does not belong to R* select s not in R* R = {s} while there is an edge (u,v) where u􀋥R and v∉R add v to R end while Add R to R* end while