《数据结构教学课件：chapter11》由会员分享，可在线阅读，更多相关《数据结构教学课件：chapter11（41页珍藏版）》请在金锄头文库上搜索。
1、*1Graph ApplicationsModeling connectivity in computer networksRepresenting mapsModeling flow capacities in networksFinding paths from start to goalModeling transitions in algorithmsOrdering tasksModeling relationships (families, organizations)*2Graphs (1)A graph G = (V, E) consists of a set of verti
2、ces V, and a set of edges E, such that each edge in E is a connection between a pair of vertices in V.The number of vertices is written |V|, and the number edges is written |E|.*3Graphs (2) undirected graph directed graph labeled graph*4Paths and CyclesPath: A sequence of vertices v1, v2, , vn of le
3、ngth n-1 with an edge from vi to vi+1 for 1 = i n.A path is simple if all vertices on the path are distinct.A cycle is a path of length 3 or more that connects vi to itself.A cycle is simple if the path is simple, except the first and last vertices are the same.*5Connected ComponentsAn undirected gr
4、aph is connected if there is at least one path from any vertex to any other.The maximum connected subgraphs of an undirected graph are called connected components.*6Directed Representation*7Undirected Representation*8Representation CostsAdjacency Matrix: (|V|2) spaceAdjacency List: (|V| + |E|) space
5、*9Graph ADTclass Graph / Graph abstract classpublic: virtual int n() =0; / # of vertices virtual int e() =0; / # of edges / Return index of first, next neighbor virtual int first(int) =0; virtual int next(int, int) =0; / Store new edge virtual void setEdge(int, int, int) =0; / Delete edge defined by
6、 two vertices virtual void delEdge(int, int) =0; / Weight of edge connecting two vertices virtual int weight(int, int) =0; virtual int getMark(int) =0; virtual void setMark(int, int) =0;*10Graph Traversals (1)Some applications require visiting every vertex in the graph exactly once.The application m
7、ay require that vertices be visited in some special order based on graph topology.Examples:Artificial Intelligence SearchShortest paths problems*11Graph Traversals (2)To insure visiting all vertices:void graphTraverse(const Graph* G) for (v=0; vn(); v+) G-setMark(v, UNVISITED); / Initialize for (v=0
8、; vn(); v+) if (G-getMark(v) = UNVISITED) doTraverse(G, v);*12Depth First Search (1)/ Depth first searchvoid DFS(Graph* G, int v) PreVisit(G, v); / Take action G-setMark(v, VISITED); for (int w=G-first(v); wn(); w = G-next(v,w) if (G-getMark(w) = UNVISITED) DFS(G, w); PostVisit(G, v); / Take action*
9、13Depth First Search (2)Order that nodes are processed: ACBFDE*14Breadth First Search (1)void BFS(Graph* G, int start,Queue*Q) int v, w; Q-enqueue(start); / Initialize Q G-setMark(start, VISITED); while (Q-length() != 0) / Process Q Q-dequeue(v); PreVisit(G, v); / Take action for(w=G-first(v);wn();w
10、=G-next(v,w) if (G-getMark(w) = UNVISITED) G-setMark(w, VISITED); Q-enqueue(w); *15Breadth First Search (2)Order that nodes are processed: ACEBDF*16Topological Sort (1)Problem: Given a set of jobs, courses, etc., with prerequisite constraints, output the jobs in an order that does not violate any of
11、 the prerequisites.*17Topological Sort (2)void topsort(Graph* G) / Topological sort int i; for (i=0; in(); i+) / Initialize G-setMark(i, UNVISITED); for (i=0; in(); i+) / Do vertices if (G-getMark(i) = UNVISITED) tophelp(G, i); / Call helpervoid tophelp(Graph* G, int v) / Process v G-setMark(v, VISI
12、TED); for (int w=G-first(v); wn(); w = G-next(v,w) if (G-getMark(w) = UNVISITED) tophelp(G, w); printout(v); / PostVisit for Vertex v*18Topological Sort (3)Prints in reverse order: J7,J5,J4,J6,J2,J3,J1*19Queue-Based Topsortvoid topsort(Graph* G, Queue* Q) int CountG-n(); int v, w; for (v=0; vn(); v+
13、) Countv = 0; for (v=0; vn(); v+) / Process edges for (w=G-first(v); wn(); w = G-next(v,w) Countw+; / Add to v2s count for (v=0; vn(); v+) / Initialize Q if (Countv = 0) / No prerequisites Q-enqueue(v); while (Q-length() != 0) Q-dequeue(v); printout(v); / PreVisit for V for (w=G-first(v); wn(); w =
14、G-next(v,w) Countw-; / One less prereq if (Countw = 0) / Now free Q-enqueue(w); *20Shortest Paths ProblemsInput: A graph with weights or costs associated with each edge.Output: The list of edges forming the shortest path.Sample problems:Find shortest path between two specified verticesFind shortest
15、path from S to all other verticesFind shortest path between all pairs of verticesOur algorithms will actually calculate only distances.*21Shortest Paths Definitionsd(A, B) is the shortest distance from vertex A to B.w(A, B) is the weight of the edge connecting A to B.If there is no such edge, then w
16、(A, B) = .*22w(A, D) = 20; d(A, D) = 10 (through ACBD).Shortest Paths Example*23Single-Source Shortest PathsGiven start vertex s, find the shortest path from s to all other vertices.Try 1: Visit vertices in some order, compute shortest paths for all vertices seen so far, then add shortest path to ne
17、xt vertex x.Example: v0,v1,v2,v3,vn-1 d(v0,v2)=min w(v0,v2), w(v0,v1)+w(v1,v2) d(v0,v3)=min w(v0,v3), d(v0,v2)+w(v2,v3) d(v0,vi)=min w(v0,vi), d(v0,vi-1)+w(vi-1,vi) *24Single-Source Shortest PathsProblem: Shortest path to a vertex already processed might go through x.Example: d(v0,vi)=d(v0,vj)+w(vj,
18、vi) jiSolution: Process vertices in order of distance from s.*25Dijkstras Algorithm Example ABCDEInitial0Process A010320Process C0532018Process B0531018Process D0531018Process E0531018*26Dijkstras Implementation/ Compute shortest path distances from s,/ return them in Dvoid Dijkstra(Graph* G, int* D
19、, int s) int i, v, w; for (i=0; in(); i+) / Do vertices v = minVertex(G, D); if (Dv = INFINITY) return; G-setMark(v, VISITED); for (w=G-first(v); wn(); w = G-next(v,w) if (Dw (Dv + G-weight(v, w) Dw = Dv + G-weight(v, w); *27Implementing minVertexIssue: How to determine the next-closest vertex? (I.e
20、., implement minVertex)Approach 1: Scan through the table of current distances.Total Cost: (|V|2 + |E|) = (|V|2).Approach 2: Store unprocessed vertices using a min-heap to implement a priority queue ordered by D value. Must update priority queue for each edge.Total Cost: (|V| + |E|)log|E|)*28Approac
21、h 1/ Find min cost vertexint minVertex(Graph* G, int* D) int i, v; / Set v to an unvisited vertex for (i=0; in(); i+) if (G-getMark(i) = UNVISITED) v = i; break; / Now find smallest D value for (i+; in(); i+) if (G-getMark(i) = UNVISITED) & (Di e(); / Heap array temp.distance = 0; temp.vertex = s; E
22、0 = temp; / Initialize heap array minheap H(E, 1, G-e(); for (i=0; in(); i+) / Get distances do if(!H.removemin(temp) return; v = temp.vertex; while (G-getMark(v) = VISITED); G-setMark(v, VISITED); if (Dv = INFINITY) return; for(w=G-first(v); wn(); w=G-next(v,w) if (Dw (Dv + G-weight(v, w) Dw = Dv +
23、 G-weight(v, w); temp.distance = Dw; temp.vertex = w; H.insert(temp); / Insert in heap *30All-Pairs Shortest PathsFor every vertex u, v V, calculate d(u, v).Could run Dijkstras Algorithm |V| times.Better is Floyds Algorithm.Define a k-path from u to v to be any path whose intermediate vertices all h
24、ave indices less than k.*31All-Pairs Shortest Paths0,3 is a 0-path. 2,0,3 is a 1-path. 0,2,3 is a 3-path, but not a 2 or 1 path. Everything is a 4 path.*32Floyds Algorithm/Floyds all-pairs shortest paths algorithmvoid Floyd(Graph* G) int DG-n()G-n(); / Store distances for (int i=0; in(); i+) / Initi
25、alize for (int j=0; jn(); j+) Dij = G-weight(i, j); / Compute all k paths for (int k=0; kn(); k+) for (int i=0; in(); i+) for (int j=0; jn(); j+) if (Dij (Dik + Dkj) Dij = Dik + Dkj;*33Minimal-Cost Spanning TreesMinimal Cost Spanning Tree (MST) Problem:Input: An undirected, connected graph G.Output:
26、 The subgraph of G that 1) has minimum total cost as measured by summing the values of all the edges in the subset 2) keeps the vertices connected.*34Prim*35Prims MST Algorithmvoid Prim(Graph* G, int* D, int s) int VG-n(); / Whos closest int i, w; for (i=0; in(); i+) / Do vertices int v = minVertex(
27、G, D); G-setMark(v, VISITED); if (v != s) AddEdgetoMST(Vv, v); if (Dv = INFINITY) return; for (w=G-first(v); wn(); w = G-next(v,w) if (Dw G-weight(v,w) Dw = G-weight(v,w);/ Update dist Vw = v; / Update who it came from *36Alternate ImplementationAs with Dijkstras algorithm, the key issue is determin
28、ing which vertex is next closest.As with Dijkstras algorithm, the alternative is to use a priority queue.Running times for the two implementations are identical to the corresponding Dijkstras algorithm implementations.*37Kruskals MST Algorithm (1)Initially, each vertex is in its own MST.Merge two MS
29、Ts that have the shortest edge between them.Use a priority queue to order the unprocessed edges. Grab next one at each step.How to tell if an edge connects two vertices already in the same MST?Use the UNION/FIND algorithm with parent-pointer representation.*38Kruskals MST Algorithm (2)*39Class Krusk
30、Elem public: int from, to, distance; KruskElem( ) from=-1; to=-1; distance=-1; KruskElem(int f, int t, int d) from=f; to=t; distance=d; ;Kruskal(Graph& G) / Kruskals MST algorithm Gentree AG-n( ); / Equivalence class array KruskElem EG-e( ); / Array of edges for min-heap int edgecnt = 0;Kruskals MST
31、 Algorithm (3)*40Kruskals MST Algorithm (4)for (int i=0; in( ); i+) / Put edges on array for (int w = G-first(i); wn( ); w = G-next(i,w) Eedgecnt.distance = G-weight(i,w); Eedgecnt.from = i; Eedgecnt+.to = w;Minheap H(E, edgecnt, edgecnt); int numMST = G-n( ); / Init n equiv classesfor (i=0; numMST1
32、; i+) / Combine equiv classes KruskElem temp; H.removemin(temp); / Get next cheap edge int v = temp.from; int u = temp.to; if (A.differ(v, u) / If different equiv classes A.UNION(v, u); / Combine equiv classes AddEdgetoMST(v,u); / Add to MST numMST-; / One less MST*41Kruskals MST Algorithm (3)Cost is dominated by the time to remove edges from the heap.Can stop processing edges once all vertices are in the same MSTTotal cost: worst case: (|E| log |E|). average case: (|V| log |E|).
