《【精品数据结构】Graph Applications.ppt》由会员分享，可在线阅读，更多相关《【精品数据结构】Graph Applications.ppt（37页珍藏版）》请在三一文库上搜索。
1、Graph Applications,Modeling connectivity in computer networks Representing maps Modeling flow capacities in networks Finding paths from start to goal (AI) Modeling transitions in algorithms Ordering tasks Modeling relationships (families, organizations),Graphs,A graph G = (V, E) consists of a set of
2、 vertices 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|.,Graphs (2),Paths and Cycles,Path: A sequence of vertices v1, v2, , vn of length n-1 with an edge from vi to vi+1 fo
3、r 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.,Connected Components,An undirected graph is connected if there is at least
4、 one path from any vertex to any other. The maximum connected subgraphs of an undirected graph are called connected components.,Directed Representation,Undirected Representation,Representation Costs,Adjacency Matrix: Adjacency List:,Graph ADT,class Graph / Graph abstract class public: virtual int n(
5、) =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 two vertices virtual void delEdge(int, int) =0; / Weight of edge c
6、onnecting two vertices virtual int weight(int, int) =0; virtual int getMark(int) =0; virtual void setMark(int, int) =0; ;,Graph Traversals,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 gr
7、aph topology. Examples: Artificial Intelligence Search Shortest paths problems,Graph 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; vn(); v+) if (G-getMark(v) = UNVISITED) doTraverse(G, v); ,Depth
8、 First Search (1),/ Depth first search void 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 ,Depth First Search (2),Cost: (|V| + |E|).,Breadth First Search (
9、1),Like DFS, but replace stack with a queue. Visit vertexs neighbors before continuing deeper in the tree.,Breadth First Search (2),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
10、, 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); ,Breadth First Search (3),Topological Sort (1),Problem: Given a set of jobs, courses, etc., with prerequisite constraints, output the jobs in an order that does not violate any
11、of the prerequisites.,Topological 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 helper void tophelp(Graph* G, int v) / Process v G-setMark(v, VI
12、SITED); 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 ,Topological Sort (3),Queue-Based Topsort,void topsort(Graph* G, Queue* Q) int CountG-n(); int v, w; for (v=0; vn(); v+) Countv = 0; for (v=0; vn(); v+) / Process e
13、dges 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 prereqs 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 =
14、 0) / Now free Q-enqueue(w); ,Shortest Paths Problems,Input: 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 named vertices Find shortest path from S to all other vertices Find shortest path
15、 between all pairs of vertices Will actually calculate only distances.,Shortest Paths Definitions,d(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(A, B) = .,Single-Source Shortest Paths,Given start vertex s, fi
16、nd 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 next vertex x. Problem: Shortest path to a vertex already processed might go through x. Solution: Process vertices in order of distan
17、ce from s.,Dijkstras Algorithm Example,Dijkstras Implementation,/ Compute shortest path distances from s, / return them in D void 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);
18、 wn(); w = G-next(v,w) if (Dw (Dv + G-weight(v, w) Dw = Dv + G-weight(v, w); ,Implementing minVertex,Issue: How to determine the next-closest vertex? (I.e., implement minVertex) Approach 1: Scan through the table of current distances. Cost: Q(|V|2 + |E|) = Q(|V|2). Approach 2: Store unprocessed vert
19、ices using a min-heap to implement a priority queue ordered by D value. Must update priority queue for each edge. Cost: Q(|V| + |E|)log|V|),Approach 1,/ Find min cost vertex int 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 =
20、 i; break; / Now find smallest D value for (i+; in(); i+) if (G-getMark(i) = UNVISITED) ,Approach 2,void Dijkstra(Graph* G, int* D, int s) int i, v, w; / v is current vertex DijkElem temp; DijkElem EG-e(); / Heap array temp.distance = 0; temp.vertex = s; E0 = temp; / Initialize heap array minheap H(
21、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 + G-weight(v, w); temp.distance = Dw; temp.ve
22、rtex = w; H.insert(temp); / Insert in heap ,All-Pairs Shortest Paths,For 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 have indices less than k.,Floyds Algorithm,
23、/Floyds all-pairs shortest paths algorithm void 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
24、= Dik + Dkj; ,Minimal Cost Spanning Trees,Minimal 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, and 2) keeps the vertices connected.,MST Example,Pri
25、ms MST Algorithm,void 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(v,w) if (Dw G-weight(v,w) Dw = G-
26、weight(v,w);/ Update dist Vw = v; / Update who it came from ,Alternate Implementation,As 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 two implementations are identic
27、al to the corresponding Dijkstras algorithm implementations.,Kruskals 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. How to tell if an edge connects
28、two vertices already in the same MST? Use the UNION/FIND algorithm with parent-pointer representation.,Kruskals MST Algorithm (2),Kruskals 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 MST Total cost: Q(|V| + |E| log |E|).,