Chapter 8

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

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].

Solution

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