Analysis of Algorithms : An Active Learning Approach

142 GRAPH ALGORITHMS

STUDY SUGGESTIONS

As you are working through the chapter, you should rework the examples to

make sure you understand them. You should do a breadth-first and depth-first

traversal starting at node A for the following graph:

You should trace the Dijkstra-Prim minimum spanning tree algorithm start-

ing at node A, Kruskal’s minimum spanning tree algorithm, and Dijkstra’s

shortest-path algorithm starting at node A for the following graph:

You should also try to answer any questions before reading on. A hint or the

answer is in the sentences following the question.

raphs are a formal description for a wide range of familiar situations.

The most common example is a road map, which shows the location

of intersections and the roads that run between them. In graph termi-

nology, the intersections are the nodes of the graph, and the roads are the

ABC D

IJK L

EFG H

C

G

K

D

H

L

B

F

J

A

E

I

9

5

3

3

2

36

6

6

94

4

4

8

8

(^178)
7
(^55)
(^79122)
G