Difference between pages "Chapter 8" and "Chapter 7"
(Difference between pages)
Jump to navigation
Jump to search
Line 1: | Line 1: | ||
− | = | + | =Graph Traversal= |
===Simulating Graph Algorithms=== | ===Simulating Graph Algorithms=== | ||
− | :[[ | + | :[[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>). | |
+ | :(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.2. Do a topological sort of the following graph <math>G</math>: | ||
+ | :(see book for figure) | ||
− | + | ===Traversal=== | |
+ | :[[7.3]] | ||
− | |||
+ | :7.4 | ||
− | |||
+ | :[[7.5]] | ||
− | |||
+ | :7.6 | ||
− | |||
+ | :[[7.7]] | ||
− | |||
+ | :7.8 | ||
− | |||
+ | :[[7.9]] | ||
− | |||
+ | :7.10 | ||
− | |||
+ | :[[7.11]] | ||
− | |||
+ | :7.12 | ||
− | |||
− | + | ===Applications=== | |
+ | :[[7.13]] | ||
− | |||
+ | :7.14 | ||
− | |||
− | :[[ | + | :[[7.15]] |
+ | ===Algorithm Design=== | ||
− | : | + | :7.16 |
− | :[[ | + | :[[7.17]] |
− | : | + | :7.18 |
− | :[[ | + | :[[7.19]] |
− | : | + | :7.20 |
− | :[[ | + | :[[7.21]]] |
− | : | + | :7.22 |
− | :[[ | + | :[[7.23]] |
− | : | + | :7.24 |
− | :[[ | + | :[[7.25]] |
− | : | + | :7.26 |
− | + | ===Directed Graphs=== | |
+ | :[[7.27]] | ||
− | |||
− | : | + | :7.28 |
− | :[[ | + | :[[7.29]] |
+ | |||
+ | |||
+ | :7.30 | ||
+ | |||
+ | |||
+ | :[[7.31]] | ||
+ | |||
+ | |||
+ | :7.32 | ||
+ | |||
+ | |||
+ | :[[7.33]] | ||
+ | |||
+ | |||
+ | :7.34 | ||
+ | |||
+ | |||
+ | :[[7.35]] | ||
+ | |||
+ | |||
+ | :7.36 | ||
+ | |||
+ | |||
+ | :[[7.37]] | ||
+ | |||
+ | |||
+ | ===Articulation Vertices=== | ||
+ | |||
+ | :7.38 | ||
+ | |||
+ | |||
+ | :[[7.39]] | ||
+ | |||
+ | |||
+ | :7.40 | ||
+ | |||
+ | |||
+ | :[[7.41]] | ||
+ | |||
+ | |||
+ | ===Interview Problems=== | ||
+ | |||
+ | :7.42 | ||
+ | |||
+ | |||
+ | :[[7.43]] | ||
Back to [[Chapter List]] | Back to [[Chapter List]] |
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