# Difference between revisions of "Chapter 7"

Jump to navigation
Jump to search

Line 4: | Line 4: | ||

:[[7.1]]. For the following graphs <math>G_1</math> (left) and <math>G_2</math> (right): | :[[7.1]]. For the following graphs <math>G_1</math> (left) and <math>G_2</math> (right): | ||

− | + | :(see book for figures) | |

− | + | ||

:(a)Report the order of the vertices encountered on a breadth-first search starting from vertex <math>A</math>. Break all ties by picking the vertices in alphabetical order (i.e., <math>A</math> before <math>Z</math>). | :(a)Report the order of the vertices encountered on a breadth-first search starting from vertex <math>A</math>. Break all ties by picking the vertices in alphabetical order (i.e., <math>A</math> before <math>Z</math>). | ||

− | (b)Report the order of the vertices encountered on a depth-first search starting from vertex <math>A</math>. Break all ties by picking the vertices in alphabetical order (i.e., <math>A</math> before <math>Z</math>). | + | :(b)Report the order of the vertices encountered on a depth-first search starting from vertex <math>A</math>. Break all ties by picking the vertices in alphabetical order (i.e., <math>A</math> before <math>Z</math>). |

[[7.1|Solution]] | [[7.1|Solution]] | ||

:7.2. Do a topological sort of the following graph <math>G</math>: | :7.2. Do a topological sort of the following graph <math>G</math>: | ||

− | + | :(see book for figure) | |

===Traversal=== | ===Traversal=== |

## Revision as of 16:13, 14 September 2020

## Contents

# Graph Traversal

### Simulating Graph Algorithms

- 7.1. For the following graphs (left) and (right):
- (see book for figures)

- (a)Report the order of the vertices encountered on a breadth-first search starting from vertex . Break all ties by picking the vertices in alphabetical order (i.e., before ).
- (b)Report the order of the vertices encountered on a depth-first search starting from vertex . Break all ties by picking the vertices in alphabetical order (i.e., before ).

- 7.2. Do a topological sort of the following graph :
- (see book for figure)

### Traversal

- 7.4

- 7.6

- 7.8

- 7.10

- 7.12

### Applications

- 7.14

### Algorithm Design

- 7.16

- 7.18

- 7.20

- 7.21]

- 7.22

- 7.24

- 7.26

### Directed Graphs

- 7.28

- 7.30

- 7.32

- 7.34

- 7.36

### Articulation Vertices

- 7.38

- 7.40

### Interview Problems

- 7.42

Back to Chapter List