# Graph Traversal

### Simulating Graph Algorithms

7.1. For the following graphs ${\displaystyle G_{1}}$ (left) and ${\displaystyle G_{2}}$ (right):
(see book for figures)
(a)Report the order of the vertices encountered on a breadth-first search starting from vertex ${\displaystyle A}$. Break all ties by picking the vertices in alphabetical order (i.e., ${\displaystyle A}$ before ${\displaystyle Z}$).
(b)Report the order of the vertices encountered on a depth-first search starting from vertex ${\displaystyle A}$. Break all ties by picking the vertices in alphabetical order (i.e., ${\displaystyle A}$ before ${\displaystyle Z}$).

7.2. Do a topological sort of the following graph ${\displaystyle G}$:
(see book for figure)

7.3

7.4

7.5

7.6

7.7

7.8

7.9

7.10

7.11

7.12

7.13

7.14

7.15

7.16

7.17

7.18

7.19

7.20

7.21]

7.22

7.23

7.24

7.25

7.26

7.27

7.28

7.29

7.30

7.31

7.32

7.33

7.34

7.35

7.36

7.37

7.38

7.39

7.40

7.41

### Interview Problems

7.42

7.43

Back to Chapter List