Analysis of Algorithms : An Active Learning Approach

GRAPH ALGORITHMS 143 edges. Sometimes our graphs are directed (like one-way streets) or weighted with a travel cost associated w ...

144 GRAPH ALGORITHMS to get information through. The last section of this chapter looks at a bicon- nected components algorithm. ...

6.1 GRAPH BACKGROUND AND TERMINOLOGY 145 After this section, we will specify graphs by drawing them instead of giving these sets ...

146 GRAPH ALGORITHMS A weighted graph or digraph is one where each edge has a value, called the weight, associated with it. In g ...

6.2 DATA STRUCTURE METHODS FOR GRAPHS 147 Give the set description for the following digraph: List all of the paths between nod ...

148 GRAPH ALGORITHMS because it would not be very large, so even a sparse graph would not waste many entries. In situations wher ...

6.2 DATA STRUCTURE METHODS FOR GRAPHS 149 ■ 6.2.2 The Adjacency List An adjacency list, AdjList, for a graph G = (V,E), with |V| ...

150 GRAPH ALGORITHMS 6.3 Depth-First and Breadth-First Traversal Algorithms When we work with graphs, there may be times that we ...

6.3 DEPTH-FIRST AND BREADTH-FIRST TRAVERSAL ALGORITHMS 151 Consider the graph in Fig. 6.4. If we begin the depth-first traversal ...

152 GRAPH ALGORITHMS the graph, it is possible for a node to be on two paths of different lengths from the starting node. Becaus ...

6.3 DEPTH-FIRST AND BREADTH-FIRST TRAVERSAL ALGORITHMS 153 considered again until all of the nodes one edge away have been taken ...

154 GRAPH ALGORITHMS 6.3.4 For the following graphs, give the order that the nodes will be first visited when doing a breadth-f ...

6.4 MINIMUM SPANNING TREE ALGORITHM 155 6.4 Minimum Spanning Tree Algorithm The minimum spanning tree (MST) of a weighted connec ...

156 GRAPH ALGORITHMS category. We loop through the process of picking the smallest weighted edge connecting a tree node with a f ...

6.4 MINIMUM SPANNING TREE ALGORITHM 157 edge with the smallest weight connects nodes A and B, so B is added to the MST along wit ...

158 GRAPH ALGORITHMS The addition of node C and edge AC to the spanning tree (Fig. 6.5(e)) did not cause any edges to be updated ...

6.4 MINIMUM SPANNING TREE ALGORITHM 159 ■ 6.4.2 The Kruskal Algorithm Where the Dijkstra-Prim algorithm began at a particular no ...

160 GRAPH ALGORITHMS A B F G C D E 1 (^2) A B F G C D E 1 2 3 ■FIGURE 6.6C Second edge added ■FIGURE 6.6D Third edge added A B F ...

6.4 MINIMUM SPANNING TREE ALGORITHM 161 The general algorithm that will accomplish this is (where E represents the number of edg ...

162 GRAPH ALGORITHMS 6.4.3 Find the minimum spanning tree using the Dijkstra-Prim algorithm for the following graphs starting a ...