**Note: **The terminology applied to graphs and to digraphs is distinct in the mathematical literature. The sequence of terms (chain, simple chain, closed chain, circuit) applied to graphs corresponds directly to terms (path, simple path, closed path, cycle) applied to directed graphs. The distinction lies in whether or not edges are directional. In a program, links are directional. If all links in a structure are double links, it models a graph rather than a digraph. However, the algorithms that search for simple chains in a graph, for example, actually locate simple paths. Such algorithms take a simpler form when working within a graph than they do if starting with a digraph. Nevertheless, the terminology (path, simple path, closed path, and cycle) are firmly entrenched in the literature in descriptions of graph algorithms. The standard terminology will be followed here without further apology.

A *graph* is a collection of *V* vertices and *E* (directed or undirected) edges that join the vertices into pairs (see section 6.3). This abstraction reflects a very common pattern; the number of systems and relationships that can be modeled by a graph is huge. An example of a graph that will be called G_{1} in this chapter is shown in Figure 10.1.

G_{1} has two *components:* subgraphs G_{11} with vertices {S-P-R-E-A-D-I-N-G} and G_{12} with vertices {O-U-T}. A component is a maximal subgraph having a sequence of edges connecting any two vertices in it.

A sequence of edges connecting two vertices is a *path,* but the sequence of vertices encountered as endpoints of the edges defines the same path. A *simple path* is one that repeats no vertex. For example, (S,A,P) specifies a simple path from S to P but (S,A,I,G,D,R,A,P) is not simple.

A *cycle* is a path that is simple except that the first and last vertices are the same. For example, (R,D,G,R) is a cycle.

A graph with no cycles is a *tree.* A collection of trees is a *forest*. Every connected component of a graph contains *spanning trees*, trees that contain every vertex in the graph. One spanning forest of G_{1} is shown in Figure 10.2.

*Exercise **E10.1 is appropriate at this point.*

If two vertices are joined by an edge, they are *adjacent*. Graphs in which every pair of vertices is adjacent are *complete*. Graphs that approach completeness are *dense*. Those with few edges are *sparse*. As a working definition, graphs for which *E* is much closer to *V* than to *V*^{2} are *sparse.*

A subgraph of a graph is *biconnected* if the removal of any one vertex leaves it connected.

*Exercise **E10.2 is appropriate at this point.*

Given a representation of a graph, some of the processes that are of common interest are:

Traverse it in one of a variety of ways, visiting every node.

Determine its components.

Determine whether there is a path between vertex v_{1} and vertex v_{2}.

Find a spanning tree in it.

Find out if the graph contains a cycle.

Determine its biconnected components.

Also of interest for weighted graphs:

Find a minimal spanning tree in it.

Find the shortest path between two vertices.

The efficiency of these operations depends on the data structure used to represent a graph as well as the algorithm used to traverse it.

10.2 The Priority - Queue Traverse of a Graph

10.3 Applications of Priority-Queue Traverses

10.4 Traverses of Weighted Graphs

A graph can be represented by itself in the sense that every vertex can be represented as a node linked to all adjacent vertices. For an arbitrary graph of *N* vertices, *N* -- 1 link-fields would be needed in the nodes. The vertices of a graph may have a limited *degree* (number of edges to adjacent vertices). A graph of degree 2 or 3 or 4 could reasonably be represented as itself and a general visitation algorithm such as those of section 7.7 or Part II, section M, applied to traverse its components. Determination of some of its attributes would be difficult, however.

As usual with data structures, a graph representation may be either endogenous or exogenous. Processing is simplified if it is assumed that the structure is exogenous, and access to the information that would appear in a vertex is reduced to an index, 1 . . . *N*. The index can be used as the argument of a function that maps it to the corresponding information, including a node identifier. In this chapter, *Tag*(*k*) is taken to be the identifier of vertex *k*. In the other direction, if *id* is the identifier of a vertex, *Index*(*id*) is the corresponding index. Hence *Index*(*Tag*(*k*))* = k and Tag*(*Index*(*id*))* = id.*

We assume here that the raw data concerning vertices and the edges connecting them are available from a file, perhaps the system input file, and that the maps *Index *and* Tag* can be created as the data is read. We assume that the number of vertices *V* and the number of edges *E* are also known. In practice, sentinel values or End-of-File flags may be used during input, and the entries counted. The function *Index* in practice may be a search for an index field in a node, just the application of a Pascal *ORD* function, a search through a sorted table of identifiers, or several other possibilities.

The timing estimates applied to the algorithms of this chapter assume that *Index* and *Tag* are *O*(1).

The efficiency of the representation of a graph depends on whether it is sparse or dense and which algorithms are applied to that representation.

One common representation (introduced in section 6.3) is the *adjacency matrix.* In simple form, it is a Boolean matrix with *TRUE* entries in row *i* and column *j* iff vertices *i* and *j* are adjacent. (Variations are a binary matrix using 1's and 0's or a *REAL* matrix with values representing weights.) For some applications, it is convenient to set the main diagonal entries (at (1,1),(2,2), . . . ) to *TRUE*, and that is assumed in this chapter for unweighted graphs. The results for G_{1} are shown in Table 10.1, where *T* is used for *TRUE* and *FALSE* entries are blank.

Given *V*, *E*, and *Index*, the *Create* procedure for an adjacency-matrix representation is:

procedureCreateAM{O(V^{2}+E)

fori=1toVdo

forj=1toVdo

a[i,j] FALSE

nextj

nexti

fori=1toVdoa[i,i] TRUEnexti

fore=1toEdo

Read(id1, id2)

iIndex(id1)

jIndex(id2)

a[i,j] TRUE

a[j,i] TRUE

nexte

end{CreateAM

For sparse graphs, a common representation of a graph is the *adjacency-list,* not to be confused with the circular-list structure applied to sparse matrices in section 6.3. In its abstract form, the adjacency listing for G_{1} is:

S : A

P : A G

R : A D G

E : N

A : S P R I

D : R N G

I : A G

N : E D G

G : P R D I N

O : U T

U : O T

T : U O

*Exercise E10.3 is appropriate at this point.*

The adjacency-list structure used here is an array of pointers to linear lists, one pointer per vertex. The list associated with a vertex pointer contains nodes that represent edges. The nodes of such a list contain the index of the vertex that the edge connects to its header vertex. For example, the (partial) list

S : A

P : A G

.

.

.

A : S P R I

.

.

.

is actually represented by Figure 10.3 if S,P,R, . . .,T are nodes 1,2, . . .,12.

Creation of the adjacency list with the simple structure illustrated above is done by:

procedureCreateAL{O(V+E)

fork = 1toVdo

L[k] NIL

nextk

fore=1toEdo

Read(id1, id2)

iIndex(id1)

jIndex(id2)

NEW(p)

p.Valuej

p.LinkL[i]

L[i]p

NEW(p)

p.Valuei

p.LinkL[j]

L[j]p

nexte

end{CreateAL

One way to traverse a graph is:

**3.** Choose a vertex from the holding structure as the new *k.*

**until** *all vertices are in the stale DONE.*

A *priority queue*, section 8.6.2, is the natural holding structure for such a traverse. In some algorithms derived from *PQT,* the priority-queue acts as a stack or as a queue, and should be replaced by the simpler and more efficient structure. In some applications of *PQT,* an unordered list may be an efficient representation of the holding structure, but it is used as a priority queue.

DONE HELD UNSEEN

1. S - PREADINGOUT

2. S A PRE DINGOUT

1. SA PRE DINGOUT

2. SA PRI E D NGOUT

1. SAI PR E D NGOUT

2. SAI PRG E D N OUT

1. SAIG PR E D N OUT

2. SAIG PRDN E OUT

1. SAIGN PRD E OUT

2. SAIGN PRDE OUT

1. SAIGNE PRD OUT

2. SAIGNE PRD OUT

1. SAIGNED PR OUT

2. SAIGNED PR OUT

1. SAIGNEDR P OUT

2. SAIGNEDR P OUT

1. SAIGNEDRP OUT

2. SAIGNEDRP OUT

DONE HELD UNSEEN

1. SAIGNEDRPO UT

2. SAIGNEDRPO UT

1. SAIGNEDRPOT U

2. SAIGNEDRPOT U

1. SAIGNEDRPOTU

2. SAIGNEDRPOTU

When vertices are held in a queue, step 3 of *PQT* chooses the longest-held vertex. The result is a *breadth-first-search* (bfs). Starting at S for G_{1:}

DONE HELD UNSEEN

1. S - PREADINGOUT

2. S A PRE DINGOUT

1. SA PRE DINGOUT

2. SA PRI E D NGOUT

1. SAP RI E D NGOUT

2. SAP RIG E D N OUT

1. SAPR IG E D N OUT

2. SAPR IGD E N OUT

1. SAPRI IGD E N OUT

2. 2SAPRI GD E N OUT

1. SAPRIG D E N OUT

2. SAPRIG DN E OUT

1. SAPRIGD N E OUT

2. SAPRIGD N E OUT

1. SAPRIGDN E OUT

2. SAPRIGDN E OUT

1. SAPRIGDNE OUT

2. SAPRIGDNE OUT

DONE HELD UNSEEN

1. SAPRIGDNEO UT

2. SAPRIGDNEO UT

1. SAPRIGDNEOU T

2. SAPRIGDNEOU T

1. SAPRIGDNEOUT

2. SAPRIGDNEOUT

A quite different trse results when the graph edges are weighted, and the weights are used for priorities. A weighting of the edges of G_{1} is shown in Figure 10.4.

DONE HELD UNSEEN

1. S - PREADINGOUT

2. S A PRE DINGOUT

1. SA PRE DINGOUT

2. SA RI E D NGOUT

1. SAI PR E D NGOUT

2. SAI PRG E D N OUT

1. SAIP RG E D N OUT

2. SAIP RG E D N OUT

1. SAIPG R E D N OUT

2. SAIPG RDN E OUT

1. SAIPGD RN E OUT

2. SAIPGD RN E OUT

1. SAIPGDR N E OUT

2. SAIPGDR N E OUT

1. SAIPGDRN E OUT

2. SAIPGDRN E OUT

1. SAIPGDRNE OUT

2. SAIPGDRNE OUT

DONE HELD UNSEEN

1. SAIPGDRNEO UT

2. SAIPGDRNEO UT

1. SAIPGDRNEOT U

2. SAIPGDRNEOT U

1. SAIPGDRNEOTU

2. SAIPGDRNEOTU

*OnPQ*[1 . . *V*] is a Boolean list for which *OnPQ*[*k*] is *TRUE* if the *k*th vertex is still in *PQ*.

*L*[1. . *V*] is the list of adjacency-list headers.

*Remove* returns and deletes the front value of *PQ*.

With these tools an adjacency-list traverse is:

procedureSparsePQT

T0

fork=1toVdo{initialization

State[k]Unseen

OnPQ[k] TRUE

PROCESS0(k)

nextk

CreatePQ{queue all vertices

repeat{retrieve them one by one

kRemove

OnPQ[k] FALSE

PROCESS1(k)

ifState[k] =Unseen{a new component starts

thenState[k]Root

TT+1

PROCESS2(k)

endif

pL[k] {check the adjacency-list

whilepNILdo

mp.Value

ifOnPQ[m]

then ifState[m] =Unseen

thenTT+1

PROCESS3(k)

endif

ifState[m] >Priority

thenState[m]Priority

PROCESS4(k)

endif

endif

pp.Link

endwhile

untilEmpty(PQ)

end{SparsePQT

form=1toVdo{check the adjacency-list

ifa[k,m]

then ifOnPQ[m]

thenTT+1

PROCESS3(k)

endif

ifState[m] >Priority

thenState[m]Priority

PROCESS4(k)

endif

endif

nextm

10.3.2 Path-Connections and Components

The list of vertices in the sequence in which they are processed (in *PROCESS*1) is the *process sequence.* The entry for the root of a component in the process sequence is negated to make component detection easier. The list is kept in *Done*[l . . *V*] and generated by the inclusions:

:c0

PROCESS1: cc + 1

Done[c]k

PROCESS2: Done[c]- Done[c]

The list that specifies at what position in the sequence a vertex is processed is the *process map.* In effect, it is an inverse of (the absolute value of) *Done *and kept in *WhenDone*[1 . . *V*]. *WhenDone*[*k*] *= c* iff |*Done*[*c*]| = *k. WhenDone* is generated simply by changing the *PROCESS1* generation of *Done* to:

PROCESS1:cc + 1

Done[c]k

WhenDone[k]c

A vertex *k* that determines the final priority of a vertex *m* is its *Parent,* kept in *Parent*[1 . . *V*]. Parenting data is gathered by:

PROCESS0 :Parent[k]0

PROCESS4 :Parent[m]k

A vertex that pulls the vertex *m* into the HELD state from the UNSEEN state is the earliest-processed vertex adjacent to *m* and is called its *ancestor.* The list *Ancestor*[1. . *V*] can be generated with:

PROCESS0 :Ancestor[k]Unseen

PROCESS2 :Ancestor[k]O

PROCESS3 :Ancestor[m]k

The data-collection lists *Done, WhenDone, Parent,* and *Ancestor* are all generated for essentially no execution-time cost with *O*(1) operations. However, they do not directly answer the questions about graphs mentioned at the beginning of this chapter and certainly they do not represent the most convenient form for working with components, paths, and spanning trees. Mining the ore they represent is the subject of the subsections that follow.

**Note: **Almost any application of the preceding data-acquisition lists can be done more succinctly and often more efficiently by incorporating their ultimate use into the traverse itself. The advantage of using them as a standard data-collection format is just that--a system one can come to know and understand and apply quickly.

A trace of the generation of the data-lists by a dfs on G_{1}, starting at S is:

S = State A = Ancestor D = Done

Pa = Parent P = Priority W = WhenDone

Tag k m T P S W D A Pa

----------------------------------------

S 1 1 -1 0 0

5 2 10 10 1 1

A 5 2 5 1 1

2 3 9 9 5 5

3 4 8 8 5 5

7 5 7 7 5 5

I 7 3 7 5 5

9 6 6 6

G 9 4 9 7 7

2 6 6 6 5 9

3 6 6 6 5 9

6 7 5 5 9 9

8 8 4 4 9 9

N 8 5 8 9 9

6 8 4 4 9 8

4 9 3 3 8 8

E 4 6 4 8 8

D 6 7 6 9 8

3 9 3 3 5 6

R 3 8 3 5 6

P 2 9 2 5 6

0 10 10 -10 0 0

11 11 1 1 10 10

12 12 0 0 10 10

T 12 11 12 10 10

11 12 0 0 10 12

U 11 12 11 10 12

The resulting values are summarized in Table 10.2.

Tag[k] k Ancestor[k] Parent[k] WhenDone[k] Done[k]

-------------------------------------------------------

S 1 0 0 1 -1

P 2 5 8 9 5

R 3 5 6 8 7

E 4 8 8 6 9

A 5 1 1 2 8

D 6 9 8 7 4

I 7 5 5 3 6

N 8 9 9 5 3

G 9 7 7 4 2

O 10 0 0 0 -10

U 11 10 12 12 12

T 12 10 10 11 11

*Program **PG10.1 is appropriate at this point.*

The progress of a traverse may be printed (or listed on a file) with:

PROCESS1: Write(Tag[k])

A linear scan of *Done* yields sets of vertices in the same component, separated by root vertices with negative entries. In a computing system that supports set variables and manages them efficiently, the component data may be shifted into sets during a linear scan for further processing.

The union-find operations of section 9.7 can be applied to *Parent* to build set structures within which the search for a common root node efficiently answers the question of whether two vertices are in the same component.

An approach more efficient than union-find structures uses *Done* as a guide to construct fully collapsed component sets. The procedure *MakeSet* that follows points all of the vertices to the root node of their component, which has an index that is the current value of *SetLink.*

procedureMakeSet{O(V)

forc=1toVdo

ifDone[c] >0

thenSet[c]SetLink

elseSetLink-Done[c]

Set[c]SetLink

endif

nextc

end{MakeSet

The Boolean expression for path connection is then:

Set[k1] =Set[k2]

**Note**: *MakeSet* works for *T* and *V* -- *T* priorities because with their use, root nodes are processed before other nodes in any component. It will not suffice otherwise.

The root nodes in *Set* are self-referencing, as an alternative to root indices of value 0.

The logic of *MakeSet* can be incorporated into *SparsePRT* (or *DensePQT*) by:

: c0

PROCESS1:cc+1

Done[c]k

PROCESS2:SetLinkDone[c]

Set[c]SetLink

Done[c] --Done[c]

elseSet[c]SetLink

If *Done* is not needed for any other purpose, it may be dispensed with:

:c0

PROCESS1 :cc+1

PROCESS2: SetLinkk

Set[c]SetLink

elseSet[c]SetLink

*Exercise E10.4 is appropriate at this point.*

The data in *Parent* determines a spanning forest, but the links point from child to parent, in the wrong direction for most tree processing. A treeform that can be traversed from root to leaf is an adjacency-list that omits links extraneous to the forest. Figure 10.5 shows the dfs traverse of G_{1} beginning at S.

Such a forest can be formed from a linear scan of *Parent*:

procedureMakeForest{O(V)

fork=1toVdo

Forest[k] NIL

nextk

fork=1toVdo

pParent[k]

ifp0

thenNEW(q)

q.Valuek

q.LinkForest[p] .Link

Forest[p] .Linkq

endif

nextk

end{MakeForest

This process can be included in *SparsePQT* (or *DensePQT*) by:

PROCESS0:Parent[k]0

Forest[k] NIL

PROCESS2:elsepParent[k]

NEW(q)

q.Valuek

q.LinkForest[p] .Link

Forest[p].Linkq

PROCESS4:Parent[m]k

*Exercise **E10.5, problem P10.1, and program PG10.2 are appropriate at this point.*

A connected graph G has a cycle iff a spanning tree does not contain all of the edges of G. An extra edge (*v*_{1},*v*_{2}) provides a path (not in the tree) between *v*_{1} and *v*_{2}; and, together with the connecting path through the tree, it forms a cycle. A graph has no edges that connect trees in its spanning forest, and so any edge not in the forest forms a cycle within a component.

PROCESS0:CycleFALSE

PROCESS3:elseCycleTRUE

An *articulation point* of a graph is a vertex with the property that, if it is removed, the remaining subgraph has more components than the original. All connecting paths between some parts of the graph and others must pass through it. The articulation points in the graph G_{2} of Figure 10.6 are A, B, and C.

Biconnected components (maximal biconnected subgraphs) are *not* disjoint, in contrast to (connected) components. For example, G_{4} in Figure 10.7 has two biconnected components joined by the articulation point K, which lies in both of them.

The information needed to detect articulation points is implicit in a search tree generated by dfs when used in conjunction with the edges not in the tree--*ghost links*.

The dfs search forest for G_{1} by dfs starting at S has four ghost links, dashed in Figure 10.8. The dfs search tree for G_{2} starting at C has one ghost link, as it must, since there are seven vertices and hence precisely six edges in the spanning tree itself. The seventh edge must be a ghost, as shown in Figure 10.9.

As one consequence of this note:

A ghost link, such as (C,F) in T_{3} (Figure 10.9), forms a *cycle*. All of the vertices from the ancestor down through the search tree to the parent to the ghost link vertex and back through the ghost link to the ancestor lie in the cycle and hence form a biconnected subgraph. The possible articulation points in this cycle are vertices with children not on the cycle and the ancestor. (The ancestor may be the only bridge between the cycle to that part of the graph higher in the tree.)

If a vertex *k* has a child that roots a subtree with no ghost links to vertices higher in the tree than *k*, then removal of *k* disconnects this subtree from the parent of *k* (and higher nodes). In general:

A nonroot vertex *k* is an articulation point iff it has a child that roots a subtree that has no ghost links to vertices higher in the tree than *k*. (Vertices higher in the tree are necessarily processed earlier.)

procedureArticulation{O(V)

Children[O]0{component counter

fork=1toVdo

Children[k]0

pParent[k]

ifp=0thenpkendif

UrMin[k]WhenDone[p]

Urmax[k]0

nextk

forc=Vdownto1do

k|Done[c]|

pParent[k]

Children[p]Children[p] +1

ifp0

thenaAncestor[k]

tWhenDone[a]

ifUrMin[k] >t

thenMint

elseMinUrMin[k]

endif

ifMin<UrMin[p]

thenUrMin[p]Min

endif

ifMin>UrMax[p]

thenUrMax[p]Min

endif

endif

nextc

end{Articulation

Note that *UrMax*[*k*] remains 0 for a leaf vertex *k*. A partial trace of the variables in *Articulation* from the data-acquisition lists of section 10.3 generated by the dfs search of G_{1} is shown in Table 10.3.

c k p a t Min

12 11 12 10 10 10

11 12 10 10 10 10

10 10 0 - - -

9 2 8 5 2 2

8 3 6 5 2 2

7 6 8 9 4 2

6 4 8 5 5 5

. . . . . .

. . . . . .

. . . . . .

UrMax[8] = 5

and hence vertex 8 is an articulation point.

*Exercise **E10.6, problem P10.2, and program PG10.3 are appropriate at this point.*

The weighted graph W_{1} of section 10.2 is reproduced as Figure 10.10 for convenience.

When vertex *m* is processed in the adjacency loop of vertex *k* in *SparsePQT*, the value of the variable *Priority *is *p * *.w*. (This is the weight of the edge connecting *k *and *m*.) It has already been traced for W_{1} in section 10.2, and construction of the tree itself is covered in section 10.3.3.

When the greedy method is implemented with *DensePQT*, it follows the scheme known as "Prim's Algorithm." An alternate scheme, known as "Kruskal's Algorithm" is to choose edges one at a time, lowest-weight first, rejecting those that would close a cycle if added to the forest. When complete--all vertices are included--there is one spanning tree for each component.

When an edge *e *is used to attach vertex *m *to a vertex *k *already in the forest, the process of attachment involves lists already familiar from section 10.3:

procedureAttach(m,k)

cc+1

WhenDone[m]c

Donem

State[m]e.w

Parent[m]k

Set[m]Set[k]

end{Attach

The resulting lists can be applied as they were in section 10.3, with minor variations. *Parent *entries of component roots need to be changed from self-reference to zero for complete conformity. *WhenDone*[*k*] is the time at which *k* is added to the forest, but not necessarily when it is joined into its final component tree.

Figure 10.11 shows some snapshots of the process applied to W_{1}.

At this point, all of the vertices have been chosen; but, as Figure 10.12 shows, the trees of the forest do not represent components of the graph.

*Problem **P10.3 is appropriate at this point.*

The test for cycle generation is a test to see if the two vertices of an edge lie in the same tree. *Set* will not work as it did in section 10.3.3 because component roots are not identifiable until the process is complete and roots are not necessarily added before their children. Some variation of the *Find *operation of section 9.7, acting on *Set*, is needed to test for a common component.

The version of Kruskal's Algorithm presented here examines the vertices of the (greedily) chosen edge. Neither, one, or both are already in the forest: vertex *m* is in the forest if *WhenDone*[*m*] 0. If precisely one vertex is in the forest, the other is attached to it. If neither is in the forest, one is attached to the other. If both are in the forest in distinct trees, one is attached to the other; but if they are in the same tree, the edge is rejected:

procedureKruskal

fork=1toVdo

Parent[k]0

Set[k]k

WhenDone[k]0

nextk

c0

ec0

whileec<Edo

ecec+1

eEdges[ec]

ifWhenDone[e.a] =0{e .ais not in the forest

then ifWhenDone[e.b] =0{and neither ise .b

thenAttach(e.b,e.b)

endif

Attach(e.a,e.b)

else ifWhenDone[e.b] =0{onlye .ais in the forest

thenAttach(e.b,e.a)

else ifFind(e.a)Find(e.b) {both are in the forest

thenParent[e.b]e.a{and in distinct trees

Set[e.b]Set[e.a]

State[e.b]e.w

endif

endif

endif

endwhile

end{Kruskal

*Program PG10.4 is appropriate at this point.*

10.4.1 The Shortest Path Problem

The *shortest path *problem is to find the path in a weighted graph between two given vertices that has the minimal weight sum of all such paths.

Priority=State[k] +p.w

The use of *a*[*k,m*] for *Priority *values yields Prim's Algorithm for the minimal spanning forest, and the use of *State*[*k*] + *a*[*k,m*] for *Priority *values yields Dijkstra's Algorithm for the shortest path problem.

*Program **PG10.5 is appropriate at this point.*

Problems of interest in a wide variety of applications include the mathematical model, *graph*. Graph models have been used for a long time and have accumulated a great deal of nomenclature concerning their paths and cycles. Graphs can be modeled in a program in a number of ways. The two most common structures for representing a graph are the *adjacency matrix*, most suitable for dense graphs, and the *adjaceny list *for sparse graphs.

A basic requirement of most algorithms that deal with a graph is a *traverse* of it, generally to make a search for something. The approach taken here is to describe a very general traversal that can be specialized and perhaps made more efficient for particular uses. It is a *priority-queue traverse, PQT. PQT *is shown to be general enough to include dfs (depth-first search) and bfs (breadth-first search).

PQT is used to generate data-acquisition lists *Parent, Ancestor, Done, *and *WhenDone*. These in turn are used to answer questions about a graph--its cycles, components, paths, spanning forest, and biconnection properties.

The use of edge-weights for priorities in *PQT *allows it to be used to find minimal spanning trees and shortest paths.

This chapter is formed around a central algorithm. *PQT *can be specialized, tuned, and expanded as needed. An advantage to this approach is that customizing can be done on familiar grounds, using the programmer's time efficiently.

The reader seeking background material on graphs for this chapter can try any number of finite mathematics texts. They usually include a chapter on graphs and indicate some of the areas of application. A survey of applications at a higher level is [ROBERTS, 1978], which has been supplemented by [ROBERTS, 1984]. Both contain extensive bibliographies.

Numerous books on graph theory are available for the undergraduate level, and the list is growing. The choice is yours. The same is true of books titled *Discrete Mathematics.*

Graph algorithms are being researched extensively. Several books about graph algorithms exist, and again the list is growing. One such is [EVEN, 1979].

A nice treatment of priority-queue traverses, including recursive versions, is given in [SEDGEWICK, 1983].

A number of graph-algorithm topics not covered in this chapter are relatively accessible. They include those for directed graphs, networks, and matching problems. Both [SEDGEWICK, 1983] and [TARJAN, 1983] have good treatments of these topics.

Exercises immediate applications of the text material

**E10.1** Find the smallest graph with more than one minimal spanning tree (mint) and a mint-(shortest-path) pair that have no edges in common.

**E10.2** In G_{1} of section 10.1, determine:

**(b)** a spanning forest different from the one illustrated

**(c)** the largest biconnected subgraph

**E10.3** Form the adjacency listing and adjacency matrix for G_{1} if the nodes are in alphabetical order.

**E10.4** Trace the operation of *MakeSet *on the summary data for G_{1} given in section 10.3.

**E10.5** Draw the spanning tree for G_{1} that would be produced by *MakeForest *altered to use *Ancestor *rather than *Parent*.

**E10.6** Complete the trace of *Articulation *variables started in section 10.3.5 and determine *UrMin *and *UrMax*.

Problems not immediate, but requiring no major extensions of the text material

**P10.1** Incorporate the effect of *MakeForest *(section 10.3.3), using *Ancestor *rather than *Parent*, directly into *SparsePQT *(section 10.2).

**P10.2** Design a procedure that uses *UrMax *and *Children *to determine and list of articulation points.

**P10.3** Change all of the weights *w *in W_{1} (section 10.4) to 10 - w and trace the behavior of Kruskal's Algorithm with snapshots.

Programs for trying it yourself

**PG10.1** Write a program that will read a file of vertices and edges and display a summary of data-acquisition lists like the one for G_{1} at the end of section 10.3.

**PG10.2** Write a program that determines and displays the spanning forest of a graph. A variation is to use PG10.1 to write files used as input by this program.

**PG10.3** Write a program that inputs vertex, edge, and identifier data for graphs and displays components and articulation points. A variation uses the program of PG10.1 to create files used as input for this program.

**PG10.4** Write a program that sorts an edge list of a graph and applies *Kruskal *to it and displays the data-acquisition lists that result from it.

**PG10.5** Write a program that uses *SparsePQT *to determine the shortest paths from a given vertex to all the vertices reachable from it.