# Difference between revisions of "Chapter 8"

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

## Contents

# 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 .
- (d) Compute the maximum flow from to .

### Minimum Spanning Tree

- 8.2

- 8.4

- 8.6

- 8.8

- 8.10

- 8.12

### Union Find

- 8.14

### Shortest Paths

- 8.16

- 8.18

- 8.20

- 8.22

- 8.24

- 8.26

### Network Flow and Matching

- 8.28

Back to Chapter List