Analysis of Algorithms : An Active Learning Approach

154 GRAPH ALGORITHMS

6.3.4

1. For the following graphs, give the order that the nodes will be first visited
   when doing a breadth-first traversal starting at the node labeled with a 1.


2. For the graphs in question 1, give the order that the nodes will be first vis-
   ited when doing a depth-first traversal starting at the node labeled with a 1.


3. Write a detailed algorithm for depth-first traversal using an adjacency
   matrix that just prints the node label as the visit operation. You should trace
   it using the graphs in this section to make sure you get the same answer.


4. Write a detailed algorithm for breadth-first traversal using an adjacency
   matrix that just prints the node label as the visit operation. You should trace
   it using the graphs in this section to make sure you get the same answer.


5. Write a detailed algorithm for depth-first traversal using an adjacency list
   that just prints the node label as the visit operation. You should trace it using
   the graphs in this section to make sure you get the same answer.


6. Write a detailed algorithm for breadth-first traversal using an adjacency list
   that just prints the node label as the visit operation. You should trace it using
   the graphs in this section to make sure you get the same answer.


7. Prove that each edge in a connected graph will be part of the depth-first tra-
   versal tree or will be an edge pointing to a predecessor in the tree.


8. Prove that each edge in a connected graph will be part of the breadth-first
   traversal tree or will be an edge pointing to a node in the tree that is neither
   a predecessor or descendent.

■6.3.4 EXERCISES

1 2

6 7

3 4 5

1 2

6 7

5 4 3

a.

c.

1 2

6 7

5 4 3

1 2

6 7

5 4 3

b.

d.