606
Graph Algorithms
For Exercises 25–28, write the nodes in a breadth-first search of the graph for Exercises 21–24, beginning with
the node specified.
25. a
26. g
27. f
28. e
29. In the computer network in the accompanying figure, the same message is to be broadcast from node C
to nodes A, E, F, and G. One way to do this is to find the shortest path from C to each of these nodes and
send out multiple copies of the same message. A more efficient approach is to send one copy out from C
along a spanning tree for the subgraph containing the nodes involved. Use the depth-first search algorithm
to find a spanning tree for the subgraph.
A
C
B
E
D
F
G
30. Using the graph for Exercise 29, use the breadth-first search algorithm to find a spanning tree for the subgraph.
31. Use the depth-first search algorithm to do a topological sort on the following graph. Indicate the counting
numbers on the graph. Also state the starting node or nodes for the search.
32. Use the depth-first search algorithm to do a topological sort on the following graph. Indicate the counting
numbers on the graph. Also state the starting node or nodes for the search.
33. The data structure used to implement a breadth-first search is a queue. What is the appropriate data structure
to implement a depth-first search?
34. Find a way to traverse a tree in level order, that is, so that all nodes at the same depth are listed from left
to right for increasing depth. (Hint: We already have a way to do this.)
35. Describe how the depth-first search algorithm can be used in a connected (undirected) graph to detect
the presence of cycles in the graph. (While it is simple to look at Figure 7.13 and see that a–b–c–e–a, for
example, is a cycle, in a huge graph with thousands of node and arcs, a cycle may be less easy to spot, in
addition to which you might not even have a visual representation.)
Graph Algorithms
For Exercises 25–28, write the nodes in a breadth-first search of the graph for Exercises 21–24, beginning with
the node specified.
25. a
26. g
27. f
28. e
29. In the computer network in the accompanying figure, the same message is to be broadcast from node C
to nodes A, E, F, and G. One way to do this is to find the shortest path from C to each of these nodes and
send out multiple copies of the same message. A more efficient approach is to send one copy out from C
along a spanning tree for the subgraph containing the nodes involved. Use the depth-first search algorithm
to find a spanning tree for the subgraph.
A
C
B
E
D
F
G
30. Using the graph for Exercise 29, use the breadth-first search algorithm to find a spanning tree for the subgraph.
31. Use the depth-first search algorithm to do a topological sort on the following graph. Indicate the counting
numbers on the graph. Also state the starting node or nodes for the search.
32. Use the depth-first search algorithm to do a topological sort on the following graph. Indicate the counting
numbers on the graph. Also state the starting node or nodes for the search.
33. The data structure used to implement a breadth-first search is a queue. What is the appropriate data structure
to implement a depth-first search?
34. Find a way to traverse a tree in level order, that is, so that all nodes at the same depth are listed from left
to right for increasing depth. (Hint: We already have a way to do this.)
35. Describe how the depth-first search algorithm can be used in a connected (undirected) graph to detect
the presence of cycles in the graph. (While it is simple to look at Figure 7.13 and see that a–b–c–e–a, for
example, is a cycle, in a huge graph with thousands of node and arcs, a cycle may be less easy to spot, in
addition to which you might not even have a visual representation.)