Chapter 7

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

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 figure)
(see book for figure)

(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]). Solution


7.2. Do a topological sort of the following graph [math]\displaystyle{ 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