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 [math]\displaystyle{ G_1 }[/math] (left) and [math]\displaystyle{ 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]\displaystyle{ A }[/math]. Break all ties by picking the vertices in alphabetical order (i.e., [math]\displaystyle{ A }[/math] before [math]\displaystyle{ Z }[/math]).
- (b)Report the order of the vertices encountered on a depth-first search starting from vertex [math]\displaystyle{ A }[/math]. Break all ties by picking the vertices in alphabetical order (i.e., [math]\displaystyle{ A }[/math] before [math]\displaystyle{ Z }[/math]).
- 7.2. Do a topological sort of the following graph [math]\displaystyle{ G }[/math]:
- (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
