Difference between revisions of "Chapter 8"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
Line 8: Line 8:
 
:(c) Find the shortest-path spanning tree rooted in <math>A</math>.
 
:(c) Find the shortest-path spanning tree rooted in <math>A</math>.
 
:(d) Compute the maximum flow from <math>A</math> to <math>H</math>.
 
:(d) Compute the maximum flow from <math>A</math> to <math>H</math>.
 +
[[8.1|Solution]]
  
 
===Minimum Spanning Tree===
 
===Minimum Spanning Tree===

Revision as of 22:31, 13 September 2020

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