Bold TextAfter understanding basic notion of graphs, we look forward to solving basic algorithm questions.Is there a path from s to t in a given graph, G? (s-t connectivity problem). This problem could also be called the Maze-solving problem. If we think of nodes as rooms, how can you get from one room to another if you start from room s? How efficient an algorithm can we design for this task?

We shall describe two natural algorithms for this problem at a high level: Breadth-first search and depth-first search.

Breadth-first search

We explore outward from s in all possible directions, adding nodes one “layer” at a time. Start at s, include all nodes that are joined by an edge to s (first layer of serach). Then, include all additional nodes that are joined by an edge to any node in the first layer (this is the second layer). We continue this way until no new nodes are encountered. An example on Page 79-80.

Recalling our definition of the distance between two nodes as the minimum nujmber of edges on a path joining them, we see that the layer L1 is the set of all nodes at a distance of 1 from s. Generally, layer Lj is the set of all nodes at distance j from s. A node fails to appear in any layer iff there is no path to it from s. BFS is both computing the shortest distance from s to all nodes and the paths to them. An edge can belong to a graph, G but not the breadth first search tree, T associated with it. We can observe that the dotted lines(which represent edges that belong to the graph and not to the tree.) are connecting nodes on the same layer or in adjacent layers only.

Exploring a connected component.

The set R is the set of all reachable nodes from s. This set is referred to as the connected component of G containing s. We start with R={s} and then add node v, not a member of R, if it has an edge to u, a member of R. The algorithm of finding the connected component is on Page 82. For any node t in the set R, it is easy to retrieve its source, thus its actual path from s. We retrieve the path of t from s by backtracking. We notice that the general algorithm we have defined to grow R is underspecified, because we do not know which edge to consider next. We, therefore, use the BFS algorithm as a way of of ordering the nodes we visit, in layers based on their distances from s.

Depth-First Serach

Another natural method to find the nodes reachable from s is the approach you might take if the graph G were truly a maze of interconnected rooms and you were walking around in it. You would have to start from s and try the first edge leading out of it, to node v. You would then follw the first edge leading out of v, and continue in this way until you reach a “dead end”- a node for which you had already explored all its neighbors. You would then backtrack until you get to anode whose neighbors have not all been explored, and explore it till you reach a dead end. We call this algorithm depth-first search becaus it explores G by going as deeply as possible and only retreating when necessary. DFS is m,ost easily described in recursive form. Algorithm of DFS on page84.

DFS vs BFS.

DFS visits nodes and makes way down long paths,potentially getting very far from s, before backtracking up to try nearer unexplored nodes. DFS gives us a spindly, thin,long tree while BFS explores nodes in form of layers, thus giving us a bushy, fatty-fat tree. They both visit the same set of nodes. They both build the connected component containing s, and they achieve similar levels of efficiency as we shall see later.

The scale of readability of this section is 8/10.