Difference between pages "Chapter 8" and "Chapter 7"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
 
 
Line 1: Line 1:
=Weighted Graph Algorithms=
+
=Graph Traversal=
  
 
===Simulating Graph Algorithms===
 
===Simulating Graph Algorithms===
  
:[[8.1]]
+
:[[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]]
  
===Minimum Spanning Tree===
 
  
:8.2
+
:7.2. Do a topological sort of the following graph <math>G</math>:
 +
:(see book for figure)
  
 +
===Traversal===
  
:[[8.3]]
+
:[[7.3]]
  
  
:8.4
+
:7.4
  
  
:[[8.5]]
+
:[[7.5]]
  
  
:8.6
+
:7.6
  
  
:[[8.7]]
+
:[[7.7]]
  
  
:8.8
+
:7.8
  
  
:[[8.9]]
+
:[[7.9]]
  
  
:8.10
+
:7.10
  
  
:[[8.11]]
+
:[[7.11]]
  
  
:8.12
+
:7.12
  
  
===Union Find===
+
===Applications===
  
:[[8.13]]
+
:[[7.13]]
  
  
:8.14
+
:7.14
  
  
===Shortest Paths===
+
:[[7.15]]
  
:[[8:15]]
+
===Algorithm Design===
  
 +
:7.16
  
:8.16
 
  
 +
:[[7.17]]
  
:[[8.17]]
 
  
 +
:7.18
  
:8.18
 
  
 +
:[[7.19]]
  
:[[8.19]]
 
  
 +
:7.20
  
:8.20
 
  
 +
:[[7.21]]]
  
:[[8.21]]
 
  
 +
:7.22
  
:8.22
 
  
 +
:[[7.23]]
  
:[[8.23]]
 
  
 +
:7.24
  
:8.24
 
  
 +
:[[7.25]]
  
:[[8.25]]
 
  
 +
:7.26
  
:8.26
 
  
 +
===Directed Graphs===
  
:[[8.27]]
+
:[[7.27]]
  
  
===Network Flow and Matching===
+
:7.28
  
:8.28
 
  
 +
:[[7.29]]
  
:[[8.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

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

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