Chapter 7

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