Difference between revisions of "Chapter 7"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
Line 3: Line 3:
 
===Simulating Graph Algorithms===
 
===Simulating Graph Algorithms===
  
:[[7.1]]
+
:[[7.1]]. For the following graphs <math>G_1</math> (left) and <math>G_2</math> (right):
 +
<br>(see book for figure)
 +
<br>(see book for figure)
 +
:(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
+
:7.2. Do a topological sort of the following graph <math>G</math>:
 
+
<br>(see book for figure)
  
 
===Traversal===
 
===Traversal===

Revision as of 16:13, 14 September 2020

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