数据结构 英文版 PPT

§2 Topological Sort〖Example〗 Courses needed for a computer science degree at a hypothetical universityCourse number C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 C151/17

Course name Programming I Discrete Mathematics Data Structure Calculus I we convert this How shall Calculus II into a graph? Linear Algebra Analysis of Algorithms Assembly Language Operating Systems Programming Languages Compiler Design Artificial Intelligence Computational Theory Parallel Algorithms Numerical Analysis

Prerequisites None None C1, C2 None list C4 C5 C3, C6 C3 C7, C8 C7 C10 C7 C7 C13 C6

数据结构 英文版 PPT

§2 Topological Sort

AOV Network ::= digraph G in which V( G ) represents activities( e.g. the courses ) and E( G ) represents precedence relations ( e.g.C1 C3 means that C1 is a prerequisite course of C3 ).

i is a predecessor of j ::= there is a path from i to j i is an immediate predecessor of j ::= < i, j > E( G )Then j is called a successor ( immediate successor ) of i

Partial order ::= a precedence relation which is both transitive( i k, k j i j ) and irreflexive ( i i is impossible ).Note: If the precedence relation is reflexive, then there must be an i such that i is a predecessor of i. That is, i must be done before i is started. Therefore if a project is feasible, it must be irreflexive.

Feasible AOV network must be a DAG (directed acyclic graph).2/17

数据结构 英文版 PPT

§2 Topological Sort

【Definition】A topological order is a linear ordering of the vertices ofa graph such that, for any two vertices, i, j, if i is a predecessor of j in the network then i precedes j in the linear ordering.

〖Example〗 One possible suggestion on course schedule for acomputer science degree could be:Course number C1 C2 C4 C3 C5 C6 C7 C15 C8 C10 C9 C12 C13 C11 C14 Course name Programming I Discrete Mathematics Calculus I Data Structure Calculus II Linear Algebra Analysis of Algorithms Numerical Analysis Assembly Language Programming Languages Operating Systems Artificial Intelligence Computational Theory Compiler Design Parallel Algorithms Prerequisites None None None C1, C2 C4 C5 C3, C6 C6 C3 C7 C7, C8 C7 C7 C10 C13

3/17

数据结构 英文版 PPT

§2 Topological Sort

Note: The topological orders may not be unique for a network. For example, there are several ways (topological orders) to meet the degree requirements in computer science. Test an AOV for feasibility, and generate a topological order if possible.

Goal

void Topsort( Graph G ) { int Counter; p.337 9.1 Vertex V, W; Find a topological ordering for ( Counter = 0; Counter < NumVertex; Counter ++ ) { V = FindNewVertexOfDegreeZero( ); /* O( |V| ) */ if ( V == NotAVertex ) { Error ( “Graph has a cycle” ); break; } TopNum[V] = Counter; /*or output V */ for ( each W adjacent to V ) Indegree[ W ] – – ; } T = O( |V|2 ) }

Exercise:

4/17

数据结构 英文版 PPT

§2 Topological Sort

Improvement: Keep all the unassigned vertices of degree 0 in a specialbox (queue or stack).void Topsort( Graph G ) T = O( |V| + |E| )

{ Queue Q; int Counter = 0; Vertex V, W; Q = CreateQueue( NumVertex ); MakeEmpty( Q ); for ( each vertex V ) if ( Indegree[ V ] == 0 ) Enqueue( p.337 9.2 V, Q ); while ( !IsEmpty( Q ) ) { What V = Dequeue( Q );if a stack is used TopNum[ V ]instead = ++ Counter; assign next */ of a/*queue? for ( each W adjacent to V ) if ( – – Indegree[ W ] == 0 ) Enqueue( W, Q ); } /* end-while */ if ( Counter != NumVertex ) Error( “Graph has a cycle” ); DisposeQueue( Q ); /* free memory */ } Mistakes in Fig 9.4 on p.287v1 v3 v4 v2 v5

v6Indegree v1 v2 v3 v4 v5 v6 v7

v7v6

Home work:

0 1 0 2 1 0 3 1 2 0 1 0 3 2 1 0 2 1 0

v7v3 v4 v5 v2 v1

5/17

数据结构 英文版 PPT

§3 Shortest Path AlgorithmsGiven a digraph G = ( V, E ), and a cost function c( e ) for e E( G ). The length of a path P from source to destination is c(ei ) (also called weighted path length).ei P

1. Single-Source Shortest-Path Problem Given as input a weighted graph, G = ( V, E ), and a distinguished vertex, s, find the shortest weighted path from s to every other vertex in G.4

v12 5 8

2 1 3

v22 4

10

4

v12 5 8

2 1 3

v22 4

–10

Negative-cost cycle Note: If there is no

v3

v41

v56

v3

v41

v56

v6

v7

v6

v7

negative-cost cycle, the shortest path from s to s is defined to be zero.

6/17

数据结构 英文版 PPT

§3 Shortest Path Algorithms

Unweighted Shortest Paths Sketch of the idea1 v 1 0 v3 1 v6

v2 2 v42

0: v3v53

1: v1 and v62: v2 and v4 3: v5 and v7

Breadth-first search

v7 3

ImplementationTable[ i ].Dist ::= distance from s to vi /* initialized to be except for s */ Table[ i ].Known ::= 1 if vi is checked; or 0 if not Table[ i ].Path ::= for tracking the path /* initialized to be 0 */

7/17

数据结构 英文版 PPT

§3 Shortest Path Algorithms void Unweighted( Table T ) { int CurrDist; Vertex V, W; for ( CurrDist = 0; CurrDist < NumVertex; CurrDist ++ ) { for ( each vertex V ) if ( !T[ V ].Known && T[ V ].Dist == CurrDist ) { T[ V ].Known = true; for ( each W adjacent to V ) If V is unknown if ( T[ W ].Dist == Infinity ) { yet has Dist < T[ W ].Dist = CurrDist + 1; Infinity, then Dist T[ W ].Path = V; is either CurrDist } /* end-if Dist == Infinity */ } /* end-if !Known && Dist == CurrDist */ or CurrDist+1. } /* end-for CurrDist */ } 2

T = O( |V|v6 v5

)

The worst case:

v9

v8

v7

v4

v3

v2

v1

8/17