Analysis of Algorithms : An Active Learning Approach

168 GRAPH ALGORITHMS

2. Alter the algorithm in this section so that it efficiently determines the short-
   est path from the start node to every node in the graph, instead of just to
   one destination.


3. Do an analysis of the shortest-path algorithm, counting the number of times
   that an edge is checked for nodes added to the fringe, for updating edges to
   the fringe nodes, or to pick the node to move from the fringe to the mini-
   mum spanning tree.


4. Prove that a breadth-first traversal produces a shortest-path tree for a graph
   without weights.


5. Prove whether it is always, never, or sometimes true that the order in which
   the nodes are added to the shortest-path tree is the same as the order in
   which they are encountered in a breadth-first traversal.


6. Prove whether it is always, never, or sometimes true that the order in which
   the nodes are added to the shortest-path tree is the same as the order in
   which they are encountered in a depth-first traversal.

6.6 Biconnected Component Algorithm

A biconnected component of a graph is the set of three or more nodes for

which there are at least two paths between each node. A biconnected compo-

nent can also have just two nodes and one edge connecting them. A bicon-

nected component is a robust part of a graph because if one node and its edges

are removed from the graph, all of the other nodes in the biconnected compo-

nent can still reach any other. The graph in Fig. 6.9 shows a connected graph

that has three biconnected components. The first biconnected component has

the nodes labeled A, B, C, and D, the second has the nodes labeled D, E, F, G,

and H, and the third has the nodes H and I.

A C E

F

G

B D H I

■FIGURE 6.9
A connected graph
with two
biconnected
components