Microsoft PowerPoint - Lecture10.ppt

Transcription

1 Chap 11. Graph 1

2 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)

3 GRAPH THEORY 3

4 Graphs A graph G = (V, E) consists of a set of 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.

5 Graph Theory Example: given the vertices V = {v 1, v 2, v 3, v 4 } and the edges E = {{v 1, v 2 }, {v 1, v 3 }, {v 3, v 4 }} the graph has three edges connecting four vertices Example: given the V = 7 vertices V = {1, 2, 3, 4, 5, 6, 7} and the E = 12 edges E = {{1, 2}, {1, 3}, {1, 4}, {2, 4}, {2, 5}, {3, 4}, {3, 6}, {4, 5}, {4, 6}, {4, 7}, {5, 7}, {6, 7}}

6 Graph Theory Two vertices are said to be adjacent if there exists an edge between the two vertices Note that if the edge is {a, b}, then a is adjacent to b, and b is adjacent to a We will assume that a vertex is not adjacent to itself, that is, each edge is made up of two distinct vertices The degree of a vertex is defined as the number of adjacent vertices In this graph, the degree of each vertex is given in red

7 Paths A path is an ordered sequence of vertices (v 0, v 1, v 2,..., v k ) where {v i 1, v i } is an edge for i = 1,..., k Termed a path from v 0 to v k The length of this path is k Same as a path in a tree Examples of paths: (1, 2, 4, 3, 6, 7, 5) (1, 4, 2, 4, 3, 4, 5, 4, 6, 4, 7) (2, 4, 1, 2, 4, 2, 1) (1)

8 Simple Paths A simple path has no repetitions other than perhaps the first and last vertices A simple path where the first and last vertices are equal is said to be a cycle Note: these definitions are not universal Examples of simple paths: (1, 2, 4, 3, 6, 7, 5) (1, 2, 5, 7, 6, 3) (2, 4, 1, 2) (1)

9 Connectedness Two vertices v i, v j are said to be connected if there exists a path from v i to v j A graph is connected if there exists a path between any two vertices Connected Unconnected

10 Weighted Graphs A weight may be associated with each edge in a graph This could represent distance, energy consumption, cost, etc. Pictorially, we will represent weights by numbers next to the edges

11 Weighted Graphs A graph where each edge has a weight is termed an weighted graph A graph where edges do not have any associated weights is termed an unweighted graph An unweighted graph may be considered to be a weighted graph where all edges have weight 1

12 Weighted Graphs The length of a path within a graph is the sum of all of the edges which make up the path The length of the path (1, 4, 7) in the following graph is = 8.8

13 Weighted Graphs There may be multiple paths between two vertices, each with a different weight Another path from 1 to 7 is (1, 4, 5, 7) with length 6.9

14 Weighted Graphs One problem we will be to find the shortest path between two vertices In this example, the shortest path from 1 to 7 is (1, 3, 6, 4, 5, 7) with length 5.7:

15 Directed Graphs The edges on a graph may be associated with a direction In this case, all edges are ordered pairs (v i, v j ) where this denotes a connection from v i to v j This does not suggest that there is a connection between v j and v i

16 Directed Graphs Such a graph is termed a directed graph and we will use arrows to denote which directions the edges go For example, G = {1, 2, 3, 4} E = {(1, 2), (1, 3), (4, 3)}

17 Directed Graphs A vertex v i is adjacent to v j in a directed graph if (v i, v i ) is in the set of edges For two vertices to be adjacent to each other, both pair must be in the set of edges: E = {(1, 2), (1, 3), (3, 4), (4, 3)}

18 Directed Graphs Another example is: G = {1, 2, 3, 4, 5, 6, 7} E = {(1, 2), (1, 4), (2, 5), (3, 1), (4, 2), (4, 3), (4, 5), (4, 6), (4,7), (5, 4), (7, 6)}

19 Directed Graphs Graphs without directions are termed undirected graphs, though these may be considered to be directed graphs with edges in both directions Most algorithms will focus on directed weighted graphs

20 In and Out Degrees The degree of a vertex must be modified to consider both cases: the out-degree of a vertex is the number of vertices which are adjacent to the given vertex the in-degree of a vertex is the number of vertices which this vertex is adjacent to Visually, think of it as the number of arrows gout out and coming in, respectively

21 In and Out Degrees For example, the in/out degrees of each of the vertices in this graph are listed next to the vertex 2/5

22 Directed Acyclic Graphs A directed acyclic graph is a directed graph which has no cycles Such an object is sufficiently common that they are often referred to as DAGs Two examples are shown here:

23 Directed Acyclic Graphs The following directed graph has a cycle and therefore is not a valid DAG

24 Directed Acyclic Graphs Applications of directed acyclic graphs include: the parse tree constructed by a compiler a reference graph that can be garbage collected using simple reference counting dependency graphs such as those used in instruction scheduling and makefiles dependency graphs between classes formed by inheritance relationships in object-oriented programming languages information categorization systems, such as folders in a computer directed acyclic word graph data structure to memory-efficiently store a set of strings (words) Reference:

25 Connected Components An 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.

26 Directed Representation

27 Undirected Representation

28 Representation Costs Adjacency Matrix: Ɵ( V 2 ) Adjacency List: Ɵ( V + E )

29 Graph ADT class Graph { // Graph abstract class public: 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 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; };

30 GRAPH TRAVERSALS 30

31 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 graph topology. Examples: Artificial Intelligence Search Shortest paths problems

32 Graph Traversals (2) To insure visiting all vertices: void graphtraverse(const Graph* G) { for (v=0; v<g->n(); v++) G->setMark(v, UNVISITED); // Initialize for (v=0; v<g->n(); v++) if (G->getMark(v) == UNVISITED) dotraverse(g, v); }

33 Depth 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); w<g->n(); w = G->next(v,w)) if (G->getMark(w) == UNVISITED) DFS(G, w); PostVisit(G, v); // Take action }

34 Depth First Search (2) Cost: ( V + E ).

35 Breadth First Search (1) Like DFS, but replace stack with a queue. Visit vertex s neighbors before continuing deeper in the tree.

36 Breadth First Search (2) void BFS(Graph* G, int start,queue<int>*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);w<g->n();w=g->next(v,w)) if (G->getMark(w) == UNVISITED) { G->setMark(w, VISITED); Q->enqueue(w); } } }

37 Breadth First Search (3)

38 TOPOLOGICAL SORT 38

39 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 of the prerequisites. Given two vertices v i and v j in a DAG, at most, there can exist only: a path from v i to v j, or a path from v j to v i Thus, it must be possible to list all of the vertices such that in that list, v i precedes v j whenever a path exists from v i to v j If this is not possible, this would imply the existence of a cycle

40 Topological Sort Such an ordering is called a topological sort For example, in this DAG, one topological sort is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

41 Application Given a number of tasks, there are often a number of constraints between the tasks: task A must be completed before task B can start These tasks together with the constraints form a directed acyclic graph A topological sort of the graph gives an order in which the tasks can be scheduled while still satisfying the constraints

42 Application Consider the course instructor getting ready for a dinner out He must wear the following: jacket, shirt, briefs, socks, tie, Blackberry, etc. There are certain constraints: the pants really should go on after the briefs, the Blackberry must be clipped on the belt socks are put on before shoes

43 Application The following is a task graph for getting dressed: One topological sort is: briefs, pants, wallet, keys, belt, Blackberry, socks, shoes, shirt, tie, jacket, ipod, watch A more likely topological sort (why?) is: briefs, socks, pants, shirt, belt, tie, jacket, wallet, keys, Blackberry, ipod, watch, shoes

44 Application Another set of tasks are courses Certain courses have prerequisites The resulting graph is a DAG Interesting twist: co-requisites (courses which must be taken concurrently) treat them as a single node

45 Applications The course sequence DAG for electrical engineering students This image is not official not all cases shown and subject to change Courses such as ECE 103, ECE 251, etc. are outside the core Ref: University of Waterloo Undergraduate Calendar, 2005/2006

46 Application The following is a DAG representing a number of tasks The numbering indicates the topological sort of the tasks The green arrows represent precedence constraints Ref: The Standard Task Graph

47 Application Here we see another topological sort of a task DAG The red critical path is that sequence of tasks which takes the longest time This is from an actual application Ref: The Standard Task Graph

48 Application This application would be used for performing these tasks on m processors In this case, the topological sort takes into case other considerations, specifically, minimizing the total run time of the collection of tasks We will see a simpler task-scheduling algorithm under greedy algorithms

49 Topological Sort To generate a topological sort, we note that we must start with a vertex with an indegree of zero: x 1

50 Topological Sort At this point, we may ignore those edges which connect vertex 1 to other vertices, and thus, we may chose vertex 2: 1, 2

51 Topological Sort We may now ignore all edges which extend from either vertices 1 or 2 We may choose from vertices 4, 5, or 3: 1, 2, 4

52 Topological Sort Adding the edges extending from vertex 4 to those we are ignoring, we find that we may add vertex 8 to our topological sort: 1, 2, 4, 8

53 Topological Sort At this point, we cannot add 11, as it must follow 9 in the topological sort Instead, we must choose from 5 or 3: 1, 2, 4, 8, 5

54 Topological Sort Removing vertex 5 from consideration allows us to consider vertices 3 or 9 We note that 3 must precede 10: 1, 2, 4, 8, 5, 9

55 Topological Sort We are now free to add 11 to our topological sort x x 1, 2, 4, 8, 5, 9, 11

56 Topological Sort The only vertex left which has an indegree of 0 when we ignore all vertices already in the topological sort is 3 1, 2, 4, 8, 5, 9, 11, 3

57 Topological Sort Having added 3, this now allows us to choose from either vertices 6 or 7 1, 2, 4, 8, 5, 9, 11, 3, 6

58 Topological Sort Adding vertex 6 to our sort allows us now to choose from vertices 7 or 10 1, 2, 4, 8, 5, 9, 11, 3, 6, 10

59 Topological Sort As 7 must precede 12 in the topological sort, we must now add 7 to the sort 1, 2, 4, 8, 5, 9, 11, 3, 6, 10, 7

60 Topological Sort At this point, we add vertex 12 1, 2, 4, 8, 5, 9, 11, 3, 6, 10, 7, 12

61 Topological Sort And finally, vertex 13 1, 2, 4, 8, 5, 9, 11, 3, 6, 10, 7, 12, 13

62 Topological Sort At this point, there are no vertices left, and therefore we have completed our topological sorting of this graph 1, 2, 4, 8, 5, 9, 11, 3, 6, 10, 7, 12, 13

63 Topological Sort It should be obvious from this process that a topological sort is not unique At any point where we had a choice as to which vertex we could choose next, we could have formed a different topological sort

64 Topological Sort For example, at this stage, had we chosen vertex 7 instead of 6: 1, 2, 4, 8, 5, 9, 11, 3, 7

65 Topological Sort The resulting topological sort would have been required to be 1, 2, 4, 8, 5, 9, 11, 3, 7, 6, 10, 12, 13

66 Topological Sort Thus, two possible topological sorts are 1, 2, 4, 8, 5, 9, 11, 3, 6, 10, 7, 12, 13 1, 2, 4, 8, 5, 9, 11, 3, 7, 6, 10, 12, 13 As seen before, these are not the only topological sorts possible for this graph, for example 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 is equally acceptable

67 Topological Sort 深度优先得到逆序 void topsort(graph* G) { // Topological sort int i; for (i=0; i<g->n(); i++) // Initialize G->setMark(i, UNVISITED); for (i=0; i<g->n(); i++) // Do vertices if (G->getMark(i) == UNVISITED) tophelp(g, i); // Call helper } void tophelp(graph* G, int v) { // Process v G->setMark(v, VISITED); for (int w=g->first(v); w<g->n(); w = G->next(v,w)) if (G->getMark(w) == UNVISITED) tophelp(g, w); printout(v); // PostVisit for Vertex v }

68 Queue-Based Topsort 广度优先得到顺序 void topsort(graph* G, Queue<int>* Q) { int Count[G->n()]; int v, w; for (v=0; v<g->n(); v++) Count[v] = 0; for (v=0; v<g->n(); v++) // Process edges for (w=g->first(v); w<g->n(); w = G->next(v,w)) Count[w]++; // Add to v2's count for (v=0; v<g->n(); v++) // Initialize Q if (Count[v] == 0) // No prereqs Q->enqueue(v); while (Q->length()!= 0) { Q->dequeue(v); printout(v); // PreVisit for V for (w=g->first(v); w<g->n(); w = G->next(v,w)) { Count[w]--; // One less prereq if (Count[w] == 0) // Now free Q->enqueue(w); }}}

69 Implementation What are the tools necessary for a topological sort? Suppose first we keep an array of the in-degree of each of the vertices:

70 Implementation Now, think back to the breadthfirst traversal there, we placed the root vertex into a queue In this case, create some sort of container (stack or queue) which initially contains all vertices with an in-degree of

71 Implementation We will initially use the terminology of a queue Initially, this queue only contains vertex 1 We can then dequeue the head of the queue (in this case 1) and add this to our topological sort:

72 Implementation With a breadth-first traversal, we push all of the popped vertices children In this case, we will decrement the in-degree of all vertices which are adjacent to the popped vertex

73 Implementation Each time we decrement the indegree of a vertex, we check if the in-degree is reduced to zero If the in-degree is reduced to zero, we enqueue that vertex Consequently, our queue now contains 2 and

74 Implementation Next, we dequeue 2, add it to our topological sort 1, 2 and decrement the in-degrees of vertices 4 and 5 Both 4 and 5 are reduced to zero, and thus our queue contains 3, 4,

75 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 between all pairs of vertices Will actually calculate only distances.

76 SHORTEST PATHS PROBLEMS 76

77 Shortest Paths Definitions Given a weighted directed graph, one common problem is finding the shortest path between two given vertices Recall that in a weighted graph, the length of a path is the sum of the weights of each of the edges in that path 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) =.

78 Shortest Path An appropriate comic taken from xkcd: A webcomic of romance, sarcasm, math, and language.

79 Shortest Path Given the graph we used in the previous topic, suppose we wish to find the shortest path from vertex 1 to vertex 13

80 Shortest Path After some consideration, we may determine that the shortest path is as follows, with length 14 Other paths exists, but they are longer

81 Applications In circuit design, one application is circuit design: the time it takes for a change in input to affect an output depends on the shortest path

82 Applications The Internet is a collection of interconnected computer networks Information is passed through packets Packets are passed from the source, through routers, to their destination Routers are connected to either: individual computers, or other routers These may be represented as graphs

83 Applications A visualization of the graph of the routers and their various connections through a portion of the Internet

84 Applications The path a packet takes depends on the IP address Metrics for measuring the shortest path may include: low latency (minimize time), or minimum hop count (all edges have weight 1)

85 Applications - Navigating 85

86 Applications The shortest path using distance as a metric is obvious, however, a driver may be more interested in minimizing time For example, using the 人民南路 may be preferable to using the 科华北路 during rush hour, however, there is an added cost

87 Single-Source Shortest Paths Given 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 next vertex x. Problem: Shortest path to a vertex already processed might go through x. Solution: Process vertices in order of distance from s.

88 Dijkstra s Algorithm Example A B C D E Initial 0 Process A Process C Process B Process D Process E

89 单源最短路径 Dijkstra 算法 为求得这些最短路径, Dijkstra 提出按路径长度的递增次序, 逐步 产生最短路径的算法 首先求出长度最短的一条最短路 径, 再参照它求出长度次短的一条 最短路径, 依次类推, 直到从顶点 v 到其它各顶点的最短路径全部求出 为止

90 依最短路径的长 度递增的次序求得各 条路径 其中, 从源 点到顶点 v 1 的最 v 1 短路径是所有最 源点 v 2 短路径中长度最 短者

91 路径长度最短的最短路径的特点 在这条路径上, 必定只含一条 弧, 并且这条弧的权值最小

92 下一条路径长度次短的最短路径 的特点 它只可能有两种情况 : 或者是直接从源点到该点 ( 只含一条弧 ); 或者是从源点经过顶点 v 1, 再到达该顶点 ( 由两条弧组成 )

93 再下一条路径长度次短的最短路径的特点 它可能有三种情况 : 或者是直接从源点到该点 ( 只含一条弧 ); 或者是从源点经过顶点 v1, 再到达该顶点 ( 由两条弧组成 ); 或者是从源点经过顶点 v2, 再到达该顶点

94 其余最短路径的特点 它或者是直接从源点到该点 ( 只含一条弧 ); 或者是从源点经过已求得最短路径的顶点, 再到达该顶点

95 求最短路径的迪杰斯特拉算法 : 设置辅助数组 Dist,Dist[k] 表示当前所求得的从源点 0 到其余各顶点 k 的最短路径 一般情况下, Dist[k] = < 源点到顶点 k 的弧上的权值 > 或 = < 源点到其它顶点的路径长度 > + < 其它顶点到顶点 k 的弧上的权值 >

96 1) 初始 Dist[ k] arcs[ 0][ k] 0 和 k 之间有弧 0 和 k 之间没有弧 具有最小值者即为第一条最短路径 2) 从还没有求得最短路径的 Dist[k] 中, 选择一个值最小的, 假设为 Dist[u], 则顶点 u 即为本次求得的具有最短路径的顶点

97 3) 修改其它各顶点的 Dist[k] 值 假设上一次求得最短路径的顶点为 u, 若 Dist[u]+arcs[u][k]<Dist[k] 则 Dist[k] =Dist[u]+arcs[u][k] 4) 重复 2) 3) 共 n-1 次

98 Dijkstra 求解过程 源点终点 最短路径 路径长度 v 0 v 1 (v 0,v 1 ) 10 v 2 (v 1 0,v 3,v 2 ) v 3 (v 0,v 3 ) 30 v 4 (v (v 0 (v,v 03,v 4 ) 100 0,v 3,v 2,v 4 ) 90 60

99 Dijkstra 算法中各辅助数组的最终结果 序号顶点 1 顶点 2 顶点 3 顶点 4 Dist path 源点 0 到终点 v 的最短路径 : 以顶点 4 为例 : path[4]=2 path[2]=3 path[3]=0 反过来排列, 得到源点 0 到终点 4 的最短路径 :0, 3, 2, 4

100 Dijkstra s 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; i<g->n(); i++) { // Do vertices v = minvertex(g, D); if (D[v] == INFINITY) return; G->setMark(v, VISITED); for (w=g->first(v); w<g->n(); w = G->next(v,w)) if (D[w] > (D[v] + G->weight(v, w))) D[w] = D[v] + G->weight(v, w); } }

101 Implementing minvertex Issue: How to determine the next-closest vertex? (I.e., implement minvertex) Approach 1: Scan through the table of current distances. 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. Cost: (( V + E )log V )

102 Approach 1 // Find min cost vertex int minvertex(graph* G, int* D) { int i, v; // Set v to an unvisited vertex for (i=0; i<g->n(); i++) if (G->getMark(i) == UNVISITED) { v = i; break; } // Now find smallest D value for (i++; i<g->n(); i++) if ((G->getMark(i) == UNVISITED) && (D[i] < D[v])) v = i; return v; }

103 Approach 2 void Dijkstra(Graph* G, int* D, int s) { int i, v, w; // v is current vertex DijkElem temp; DijkElem E[G->e()]; // Heap array temp.distance = 0; temp.vertex = s; E[0] = temp; // Initialize heap array minheap<dijkelem, DDComp> H(E, 1, G->e()); for (i=0; i<g->n(); i++) {// Get distances do { if(!h.removemin(temp)) return; v = temp.vertex; } while (G->getMark(v) == VISITED); G->setMark(v, VISITED); if (D[v] == INFINITY) return; for(w=g->first(v); w<g->n(); w=g->next(v,w)) if (D[w] > (D[v] + G->weight(v, w))) { D[w] = D[v] + G->weight(v, w); temp.distance = D[w]; temp.vertex = w; H.insert(temp); // Insert in heap }}}

104 All-Pairs Shortest Paths For every vertex u, v V, calculate d(u, v). Could run Dijkstra s Algorithm V times. Better is Floyd s Algorithm. Define a k-path from u to v to be any path whose intermediate vertices all have indices less than k.

105 求每一对顶点之间的最短路径 Floyd( 弗洛伊德 ) 算法的基本思想是 : 从 v i 到 v j 的所有可能存在的 路径中, 选出一条长度最短的路 径

106 若 <v i,v j > 存在, 则存在路径 {v i,v j } // 路径中不含其它顶点 在路径上增加 v 1, 若 <v i,v 1 >,<v 1,v j > 存在, 则比较路径 {v i,v 1,v j } 和 {v i,v j } 长度, 取长度短者为从 v i 到 v j 中间只经过序号不大于 1 的顶点的最短路径, 即路径中所含顶点序号不大于 1;

107 在路径上增加 v 2, 若 <v i,,v 2 >,<v 2,,v j > 存在 ( 它们分别是在前一步中找到的最短路径 ), 则将路径 {v i,,v 2,,v j } 的长度与以前找到的 v i 到 v j 最短路径长度比较, 取长度短者为从 v i 到 v j 中间只经过序号不大于 2 的顶点的最短路径, 即路径中所含顶点序号不大于 2;

108 依次在路径上增加 v 3,,v n 经过 n 次比较后, 最后求得的必是从 v i 到 v j 的最短路径

109 dist -1 = path -1 = dist 0 = path 0 =

110 dist 0 = path 0 = dist 1 = path 1 =

111 dist 1 = path 1 = dist 2 = path 2 =

112 Floyd s Algorithm //Floyd's all-pairs shortest paths algorithm void Floyd(Graph* G) { int D[G->n()][G->n()]; // Store distances for (int i=0; i<g->n(); i++) // Initialize for (int j=0; j<g->n(); j++) D[i][j] = G->weight(i, j); // Compute all k paths for (int k=0; k<g->n(); k++) for (int i=0; i<g->n(); i++) for (int j=0; j<g->n(); j++) if (D[i][j] > (D[i][k] + D[k][j])) D[i][j] = D[i][k] + D[k][j]; }

113 MINIMAL COST SPANNING TREES 113

114 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.

115 MST Example

116 Minimum Spanning Trees Given a connected graph with V = n vertices, a spanning tree is defined a collection of n 1edges which connect all n vertices The n vertices and n 1edges define a connected sub-graph A spanning tree is not necessarily unique

117 Minimum Spanning Trees This graph has 16 vertices and 35 edges

118 Minimum Spanning Trees These 15 edges form a minimum spanning tree

119 Minimum Spanning Trees As do these 15 edges:

120 Spanning Trees Such a collection of edges is called a tree because if any vertex is taken to be the root, we form a tree by treating the adjacent vertices as children, and so on...

121 Spanning Trees Spanning trees are not unique This tree and choice of root forms a perfect tree

122 Spanning Trees Nor do they necessarily have nice properties

123 Minimum Spanning Trees The weight of a spanning tree is the sum of the weights on all the edges which comprise the spanning tree The weight of this spanning tree is 20

124 Minimum Spanning Trees Which spanning tree which minimizes the weight? Such a tree is termed a minimum spanning tree The weight of this spanning tree is 14

125 Minimum Spanning Trees If we use a different vertex as the root, we get a different tree, however, this is simply the result of one or more rotations

126 Unweighted Graphs Observation Recall that an unweighted graph may be interpreted as a weighted graph where all edges have weight 1 Minimum spanning trees make no sense for unweighted graphs, as all spanning trees will have the same weighted It is straight-forward to generate a spanning tree

127 Application Consider supplying power to All circuit elements on a board A number of loads within a building A minimum spanning tree will give the lowest-cost solution

128 Application Consider attempting to find the best means of connecting a number of LANs Minimize the number of bridges Costs not strictly dependant on distances

129 Application A minimum spanning tree will provide the optimal solution

130 Application Consider an ad hoc wireless network Any two terminals can connect with any others Problem: Errors in transmission increase with transmission length Can we find clusters of terminals which can communicate safely?

131 Application Find a minimum spanning tree

132 Application Remove connections which are too long This clusters terminals into smaller and more manageable sub-networks

133 Minimum Spanning Trees We will examine Prim s algorithm for finding the minimum spanning tree We will start with an arbitrary vertex to be the root of a trivial tree We will expand by adding vertices not already in the tree which can be added most cheaply Another possibility is Kruskal s algorithm

134 构造最小生成树的算法 算法一 : 普里姆算法 (Prim) 算法二 : 克鲁斯卡尔算法 (Kruskal)

135 一 Prim 算法的 基本思想

136 1. 取图中任意一个顶点 v 作为 生成树的根, 之后往生成树 上添加新的顶点 w;

137 2. 在添加的顶点 w 和已经在生成树上的顶点 v 之间必定存在一条边, 并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小 ;

138 3. 之后继续往生成树上添加顶 点, 直至生成树上含有 n 个顶点为止

139 一般情况下所添加的顶点应满足 下列条件 : 在生成树的构造过程中, 图中 n 个顶点分属两个集合 : 已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集 V-U, 则应在所有连通 U 中顶点和 V-U 中顶点的边中选取权值最小的边

140 U V-U

141 (c) 原图 (a) (b) (d) (e) (f)

142 18 a e 16 8 b c g d 27 f 21 所得生成树权值和 = = 67

143 二 Kruskal 算法的 基本思想

144 基本实现思路 : 为使生成树上边的权值之和达到最小, 则应使生成树中每一条边的权值尽可能地小

145 具体做法 : 先构造一个只含 n 个顶点的子图 SG, 然后从权值最小的边开始, 若它的添加不使 SG 中产生回路, 则在 SG 上加上这条边, 如此重复, 直至加上 n-1 条边为止

146 原图 (a) (b) 1 3 2

147 原图 (e) (c) (d) (f) (g)

148 18 19 a e 16 8 b c g d 27 f 21 所得生成树权值和 = = 67

149 Prim s MST Algorithm void Prim(Graph* G, int* D, int s) { int V[G->n()]; // Who's closest int i, w; for (i=0; i<g->n(); i++) {// Do vertices int v = minvertex(g, D); G->setMark(v, VISITED); if (v!= s) AddEdgetoMST(V[v], v); if (D[v] == INFINITY) return; for (w=g->first(v); w<g->n(); w = G->next(v,w)) if (D[w] > G->weight(v,w)) { D[w] = G->weight(v,w);// Update dist V[w] = v; // Update who it came from } } }

150 Alternate Implementation As with Dijkstra s algorithm, the key issue is determining which vertex is next closest. As with Dijkstra s algorithm, the alternative is to use a priority queue. Running times for the two implementations are identical to the corresponding Dijkstra s algorithm implementations.

151 Kruskal s MST Algorithm (1) Initially, each vertex is in its own MST. Merge two MST s 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 parentpointer representation.

152 Kruskal s MST Algorithm (2)

153 Kruskal s 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: ( V + E log E ).