《《数据结构》英文课件：chapter11 Graph Applications》由会员分享，可在线阅读，更多相关《《数据结构》英文课件：chapter11 Graph Applications（59页珍藏版）》请在金锄头文库上搜索。
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 graphSparse graphDense graph*4Paths and CyclesPath: A sequence of vert
3、ices v1, v2, , vn of length 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.*5Subgraph A su
4、bgraph S is formed from graph G by selecting a subset Vs of Gs vertices and a subset Es of Gs edges such that for every E in Es, both of whose vertices are in Vs.*6DAGA graph without cycles is called acyclic. A directed graph without cycles is called a directed acyclic graph of DAG.*7Connected Compo
5、nentsAn undirected graph 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.strongly connectedweakly connectedfor directed graph *8Directed RepresentationAdjacency matrixAdjacency listOutdgree
6、 Indgree adjacentneighborInverse Adjacency list*9Undirected RepresentationAdjacency matrixAdjacency list*10Representation CostsAdjacency Matrix: (|V|2) spaceAdjacency List: (|V| + |E|) space*11Graph ADTclass Graph / Graph abstract classpublic: virtual int n() =0; / # of vertices virtual int e() =0;
7、/ # 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 two vertices virtual void delEdge(int, int) =0; / Weight of edge connecting two vertices virtual int weight(
8、int, int) =0; virtual int getMark(int) =0; virtual void setMark(int, int) =0;Implementation for the adjacency matrix #define UNVISITED 0#define VISITED 1#include graph.hclass Graphm : public Graph / Implement adjacency matrixprivate: int numVertex, numEdge; / Store number of vertices, edges int *mat
9、rix; / Pointer to adjacency matrix int *mark; / Pointer to mark array*12public: Graphm(int numVert) / Make graph w/ numVert vertices int i, j; numVertex = numVert; numEdge = 0; mark = new intnumVert; / Initialize mark array for (i=0; inumVertex; i+) marki = UNVISITED; matrix = (int*) new int*numVert
10、ex; / Make matrix for (i=0; inumVertex; i+) matrixi = new intnumVertex; for (i=0; i numVertex; i+) / Edges start w/ 0 weight for (int j=0; jnumVertex; j+) matrixij = 0; *13 Graphm() / Destructor delete mark; / Return dynamically allocated memory for (int i=0; inumVertex; i+) delete matrixi; delete m
11、atrix; int n() return numVertex; / Number of vertices int e() return numEdge; / Number of edges*14int first(int v) / Return vs first neighbor int i; for (i=0; inumVertex; i+) if (matrixvi != 0) return i; return i; / Return n if none int next(int v1, int v2) / Get v1s neighbor after v2 int i; for(i=v
12、2+1; i0, Illegal weight value); if (matrixv1v2 = 0) numEdge+; matrixv1v2 = wgt; void delEdge(int v1, int v2) / Delete edge (v1, v2) if (matrixv1v2 != 0) numEdge-; matrixv1v2 = 0; int weight(int v1, int v2) return matrixv1v2; int getMark(int v) return markv; void setMark(int v, int val) markv = val;
13、;*16Implementation for adjacency listclass Edge public: int vertex, weight; Edge() vertex = -1; weight = -1; Edge(int v, int w) vertex = v; weight = w; ;/ Overload for the Edge operatorostream& operator (ostream& s, Edge e) return(s ( e.vertex , e.weight ); *17class Graphl : public Graph / Implement
14、 adjacency listprivate: int numVertex, numEdge; / Number of vertices, edges List* vertex; / List headers int *mark; / Pointer to mark arraypublic: Graphl(int numVert) / Make graph with numVert vertices int i, j; numVertex = numVert; numEdge = 0; mark = new intnumVert; / Initialize mark array for (i=
15、0; inumVertex; i+) marki = UNVISITED; / Create and initialize adjacency lists vertex = (List*) new List*numVertex; for (i=0; inumVertex; i+) vertexi = new LList(); *18 Graphl() / Destructor delete mark; / Return dynamically allocated memory for (int i=0; isetStart(); if (vertexv-getValue(it) return
16、it.vertex; else return numVertex; / Return n if none *19int next(int v1, int v2) / Gete v1s neighbor after v2 Edge it; vertexv1-getValue(it); if (it.vertex = v2) vertexv1-next(); else / Start from beginning of list vertexv1-setStart(); while (vertexv1-getValue(it) & (it.vertex next(); if (vertexv1-g
17、etValue(it) return it.vertex; else return numVertex; / Return n if none *20 / Set edge (v1, v2) to wgt void setEdge(int v1, int v2, int wgt) Assert(wgt0, Illegal weight value); Edge it(v2, wgt); Edge curr; vertexv1-getValue(curr); if (curr.vertex != v2) / If not already there, search for (vertexv1-s
18、etStart(); vertexv1-getValue(curr); vertexv1-next() if (curr.vertex = v2) break; if (curr.vertex = v2) / Clear out the current one vertexv1-remove(curr); else numEdge+; vertexv1-insert(it); *21void delEdge(int v1, int v2) / Delete edge (v1, v2) Edge curr; vertexv1-getValue(curr); if (curr.vertex !=
19、v2) / If not already there, search for (vertexv1-setStart(); vertexv1-getValue(curr); vertexv1-next() if (curr.vertex = v2) break; if (curr.vertex = v2) / If not, then there is none vertexv1-remove(curr); numEdge-; *22int weight(int v1, int v2) / Return weight of (v1, v2) Edge curr; vertexv1-getValu
20、e(curr); if (curr.vertex != v2) / If not already there, search for (vertexv1-setStart(); vertexv1-getValue(curr); vertexv1-next() if (curr.vertex = v2) break; if (curr.vertex = v2) return curr.weight; else return 0; / No such edge int getMark(int v) return markv; void setMark(int v, int val) markv =
21、 val; ;*23*24Graph Traversals (1)Some applications require visiting every vertex in the graph exactly once.The application may require that vertices be visited in some special order based on graph topology.Examples:Artificial Intelligence SearchShortest paths problems*25Graph Traversals (2)To insure
22、 visiting all vertices:void graphTraverse(const Graph* G) for (v=0; vn(); v+) G-setMark(v, UNVISITED); / Initialize for (v=0; vn(); v+) if (G-getMark(v) = UNVISITED) doTraverse(G, v);*26Depth First Search (1)/ Depth first searchvoid DFS(Graph* G, int v) PreVisit(G, v); / Take action G-setMark(v, VIS
23、ITED); 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*27Depth First Search (2)Order that nodes are processed: ACBFDE*28Breadth First Search (1)void BFS(Graph* G, int start,Queue*Q) int v, w; Q-enqueue(start); / Initialize Q G-setM
24、ark(start, VISITED); while (Q-length() != 0) / Process Q Q-dequeue(v); PreVisit(G, v); / Take action for(w=G-first(v);wn();w=G-next(v,w) if (G-getMark(w) = UNVISITED) G-setMark(w, VISITED); Q-enqueue(w); *29Breadth First Search (2)Order that nodes are processed: ACEBDF*30Topological Sort (1)Problem:
25、 Given a set of jobs, courses, etc., with prerequisite constraints, output the jobs in an order that does not violate any of the prerequisites.*31Topological 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 ve
26、rtices if (G-getMark(i) = UNVISITED) tophelp(G, i); / Call helpervoid tophelp(Graph* G, int v) / Process v G-setMark(v, VISITED); 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*32Topological Sort (3)Prints in reverse or
27、der: J7,J5,J4,J6,J2,J3,J1*33Queue-Based Topsortvoid topsort(Graph* G, Queue* Q) int CountG-n(); int v, w; for (v=0; vn(); v+) 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 p
28、rerequisites Q-enqueue(v); while (Q-length() != 0) Q-dequeue(v); printout(v); / PreVisit for V for (w=G-first(v); wn(); w = G-next(v,w) Countw-; / One less prereq if (Countw = 0) / Now free Q-enqueue(w); *34Shortest Paths ProblemsInput: A graph with weights or costs associated with each edge.Output:
29、 The list of edges forming the shortest path.Sample problems:Find shortest path between two specified verticesFind shortest path from S to all other verticesFind shortest path between all pairs of verticesOur algorithms will actually calculate only distances.*35Shortest Paths Definitionsd(A, B) is t
30、he 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(A, B) = .*36w(A, D) = 20; d(A, D) = 10 (through ACBD).Shortest Paths Example*37Single-Source Shortest PathsGiven start vertex s, find the shortest path from s to all other ver
31、tices.Try 1: Visit vertices in some order, compute shortest paths for all vertices seen so far, then add shortest path to next 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) *38Single-S
32、ource Shortest PathsProblem: Shortest path to a vertex already processed might go through x.Example: d(v0,vi)=d(v0,vj)+w(vj,vi) jiSolution: Process vertices in order of distance from s.*39Dijkstras Algorithm Example ABCDEInitial0Process A010320Process C0532018Process B0531018Process D0531018Process
33、E0531018*40Dijkstras Implementation/ Compute shortest path distances from s,/ return them in Dvoid Dijkstra(Graph* G, int* D, 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 (
34、Dv + G-weight(v, w) Dw = Dv + G-weight(v, w); *41Implementing minVertexIssue: How to determine the next-closest vertex? (I.e., 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 impl
35、ement a priority queue ordered by D value. Must update priority queue for each edge.Total Cost: (|V| + |E|)log|E|)*42Approach 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 sma
36、llest D value for (i+; in(); i+) if (G-getMark(i) = UNVISITED) & (Di e(); / Heap array temp.distance = 0; temp.vertex = s; E0 = 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
37、-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 + G-weight(v, w); temp.distance = Dw; temp.vertex = w; H.insert(temp); / Insert in heap *44All-Pairs Shortest PathsFor every vertex u, v V, calculate d(u, v).Could run Dijkstras
38、 Algorithm |V| times.Better is Floyds Algorithm.Define a k-path from u to v to be any path whose intermediate vertices all have indices less than k.*45All-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.*46Floyds Algorithm/Floy
39、ds all-pairs shortest paths algorithmvoid Floyd(Graph* G) int DG-n()G-n(); / Store distances for (int i=0; in(); i+) / Initialize 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
40、+ Dkj;*47Floyds Algorithm Example(1)1234561010 20 2210035330 15 4205011 105 15 110362 10301-path:2-path:1234561010 20 2210035 12330 15 4205011 105 15 11036212 1030*48Floyds Algorithm Example(2)1234561010 13 15 2210035 1231330815 1541558011 105 15 110362 15 10303-path:4-path:1234561010 13 15 22100351
41、8 1231330815 1541558011 105 18 15 110362 15 1030*49Floyds Algorithm Example(3)5-path:6-path:1234561010 13 15 31221003516 1231330815 1541558011 10531 16 15 110362 15 10301234561010 13 15 31221003516 1231330815 1541558011 10531 16 15 110362 15 1030*50Floyds Algorithm Example(4)7-path:1234561010 13 126
42、221003516 1231330815 1541258011 105616 15 110362 15 1030*51Minimal Cost Spanning TreesMinimal Cost Spanning Tree (MST) Problem:Input: An undirected, connected graph G.Output: 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 th
43、e vertices connected.*52Prim*53Prims 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(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(
44、v,w) if (Dw G-weight(v,w) Dw = G-weight(v,w);/ Update dist Vw = v; / Update who it came from *54Alternate ImplementationAs with Dijkstras algorithm, the key issue is determining which vertex is next closest.As with Dijkstras algorithm, the alternative is to use a priority queue.Running times for the
45、 two implementations are identical to the corresponding Dijkstras algorithm implementations.*55Kruskals MST Algorithm (1)Initially, each vertex is in its own MST.Merge two MSTs that have the shortest edge between them.Use a priority queue to order the unprocessed edges. Grab next one at each step.Ho
46、w to tell if an edge connects two vertices already in the same MST?Use the UNION/FIND algorithm with parent-pointer representation.*56Kruskals MST Algorithm (2)*57Class KruskElem public: int from, to, distance; KruskElem( ) from=-1; to=-1; distance=-1; KruskElem(int f, int t, int d) from=f; to=t; di
47、stance=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 Algorithm (3)*58Kruskals MST Algorithm (4)for (int i=0; in( ); i+) / Put edges on array for (int w = G-first(i); wn( ); w = G
48、-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; i+) / Combine equiv classes KruskElem temp; H.removemin(temp); / Get next cheap edge int v = temp.from; int u = temp.to; if
49、(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*59Kruskals 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|).
