Chapter 8

Weighted Graph Algorithms

Simulating Graph Algorithms

8.1. For the graphs in Problem 7-1:

(a) Draw the spanning forest after every iteration of the main loop in Kruskal’s algorithm.

(b) Draw the spanning forest after every iteration of the main loop in Prim’s algorithm.

(c) Find the shortest-path spanning tree rooted in [math]\displaystyle{ A }[/math].

(d) Compute the maximum flow from [math]\displaystyle{ A }[/math] to [math]\displaystyle{ H }[/math].

Minimum Spanning Tree

8.2

8.3

8.4

8.5

8.6

8.7

8.8

8.9

8.10

8.11

8.12

Union Find

8.13

8.14

Shortest Paths

8:15

8.16

8.17

8.18

8.19

8.20

8.21

8.22

8.23

8.24

8.25

8.26

8.27

Network Flow and Matching

8.28

8.29

Back to Chapter List