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(pseudo-code):

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

The R produced at the end of the algorithm is the connected component of G containing s. The BFS algorithms is usually used when we need to order nodes we visit in successive layers based on their distance from s. Great application: Finding the shortest path.

This algorithms consists in going through a graph as far as possible, and only retreating(or backtracking)when necessary. With this implementation, we keep track of the nodes we have already explored so that we may be able to backtrack when necessary.

• Similarities with BFS: They both build the connected component containing s, and achieve qualitatively similar levels of efficiency. In both implementations, nontree edges can only connect ancestors to descendants.
• Differences with BFS: DFS visits the nodes in a different order:it probes its way down long paths, potentially getting very far from s, before backtracking to explore nearer nodes.
• Also, the trees they both produce have different structures: DFS trees tend to be narrow and deep while BFS trees are as short as possible.

DFS(u):
Mark u as “Explored” and add u to R
For each edge (u,v) incident to u:

if v is not marked “Explored” then

Recursively invoke DFS(u)

Endif

Endfor

In brief, when trying to efficiently solve problems that involve graph traversal, BFS and DFS are the best options available to the algorithm designer. Both BFS and DFS allows easy and efficient traversals of a graph, which in turn helps solve some problems that involve huge graphs.

This section was also interesting and easy to read,so why not give it a 9/10?Yeah, I give it a 9/10.