2008级计算机 内部资料,仅供课堂教学使用 Chapter 2 Graph P569 Mathematical Background 5. A Greedy Algorithm: Shortest Paths 2. Computer Representation 6. Minimal Spanning Trees 3. Graph Traversal 7. Graphs as Data Structures 4. Topological Sorting [12. 1]Mathematical Background P 570 Graphs: Definitions P570-572 1. A graph G consists of a set V, whose members are called the vertices of G, together with a set E of pairs of distinct vertices from v The pairs in E are called the edges of G 3. Ife=(v, w)is an edge with vertices v and w, then v and w are said to lie on e, and e is said to be incident with v and w 4. If the pairs are unordered, G is called an undirected graph 5. If the pairs are ordered, G is called a directed graph. The term directed graph is often shortened to digraph, and the unqualified term graph usually means undirected graph 6. Two vertices in an undirected graph are called adjacent if there is an edge from the first to the second 7. A path is a sequence of distinct vertices, each adjacent to the next. 8. A cycle is a path containing at least three vertices such that the last vertex on the path is adjacent to the first 9. A graph is called connected if there is a path from any vertex to any other vertex 10. A free tree is defined as a connected undirected graph with no cycles 1. In a directed graph a path or a cycle means always moving in the direction indicated by the arrows. Such a path(cycle)is called a directed path(cycle) 13. The valence of a vertex is the number of edges on which it lies, hence also the number of vertices adjacent to ted ppress 12. a directed graph is called strongly connected if there is a directed path from any vertex to any other vertex. If we suppress the direction of the edges and the resulting undirected graph is connected, we call the directed graph weakly connected Examples of Graphs P 570 Various kinds of graphs P571-572 [12.2]Computer Representation P572 Set Implementations of Digraphs DEFINITION: A digraph G consists of a set V, called the vertices of G, and, for all vEV, a subset Av of v, called the set of vertices adjacent to v Set as a bit string: P573 Digraph as a bit-string set: P573 Digraph as an adjacency table: P574 List Implementation of Digraphs P574-575 112.3 Graph Traversal P 575-576 Depth-first traversal of a graph is roughly analogous to preorder traversal of an ordered tree. Suppose that the traversal has just visited a vertex v, and let wi, W2,., W be the vertices adjacent to v. Then we shall next visit wI and keep w2,.,w aiting. After visiting WI, we traverse all the vertices to which it is adjacent before returning to traverse w2,.,Wk visited a vertex v, then it next visits all the vertices adjacent to v, putting the vertices adjacent to these in a waiting ist st Breadth-first traversal of a graph is roughly analogous to level-by-level traversal of an ordered tree. If the traversal has ju to be traversed after all vertices adjacent to v have been visited Depth-First Algorithm P.577 The recursion is performed in an auxiliary function traverse. P 578 Breadth-First Algorithm P578 112.4 Topological Sorting P579 Let g be a directed graph with no cycles. a topological order for g is a sequential listing of all the vertices in G such that, for all vertices V, wEG, if there is an edge from v to w, then v precedes w in the sequential listing. P. 580 Digraph class Topological Sort P579 Depth-First Algorithm P.580-581 Breadth-First Algorithm P 582 [12.5 A Greedy Algorithm: Shortest Paths P.583
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 12 Graph P.569 ----------------------------------------------------------------------------------------------------------------------------------------------- 1. Mathematical Background 2. Computer Representation 3. Graph Traversal 4. Topological Sorting 5. A Greedy Algorithm: Shortest Paths 6. Minimal Spanning Trees 7. Graphs as Data Structures [12.1] Mathematical Background P. 570 Graphs: Definitions P. 570-572 1. A graph G consists of a set V , whose members are called the vertices of G, together with a set E of pairs of distinct vertices from V . 2. The pairs in E are called the edges of G. 3. If e = (v, w) is an edge with vertices v and w , then v and w are said to lie on e , and e is said to be incident with v and w . 4. If the pairs are unordered, G is called an undirected graph. 5. If the pairs are ordered, G is called a directed graph. The term directed graph is often shortened to digraph, and the unqualified term graph usually means undirected graph. 6. Two vertices in an undirected graph are called adjacent if there is an edge from the first to the second. 7. A path is a sequence of distinct vertices, each adjacent to the next. 8. A cycle is a path containing at least three vertices such that the last vertex on the path is adjacent to the first. 9. A graph is called connected if there is a path from any vertex to any other vertex. 10. A free tree is defined as a connected undirected graph with no cycles. 11. In a directed graph a path or a cycle means always moving in the direction indicated by the arrows. Such a path (cycle) is called a directed path (cycle). 12. A directed graph is called strongly connected if there is a directed path from any vertex to any other vertex. If we suppress the direction of the edges and the resulting undirected graph is connected, we call the directed graph weakly connected. 13. The valence of a vertex is the number of edges on which it lies, hence also the number of vertices adjacent to it. Examples of Graphs P. 570 Various kinds of graphs P. 571-572 [12.2] Computer Representation P. 572 Set Implementations of Digraphs DEFINITION: A digraph G consists of a set V , called the vertices of G, and, for all v∈V , a subset Av of V , called the set of vertices adjacent to v . Set as a bit string: P. 573 Digraph as a bit-string set: P. 573 Digraph as an adjacency table: P. 574 List Implementation of Digraphs P. 574-575 [12.3] Graph Traversal P. 575-576 ⚫ Depth-first traversal of a graph is roughly analogous to preorder traversal of an ordered tree. Suppose that the traversal has just visited a vertex v , and let w1 , w2 ,..., wk be the vertices adjacent to v . Then we shall next visit w1 and keep w2 ,..., wk waiting. After visiting w1 , we traverse all the vertices to which it is adjacent before returning to traverse w2 ,..., wk . ⚫ Breadth-first traversal of a graph is roughly analogous to level-by-level traversal of an ordered tree. If the traversal has just visited a vertex v , then it next visits all the vertices adjacent to v , putting the vertices adjacent to these in a waiting list to be traversed after all vertices adjacent to v have been visited. Depth-First Algorithm P. 577 The recursion is performed in an auxiliary function traverse. P. 578 Breadth-First Algorithm P. 578 [12.4] Topological Sorting P. 579 Let G be a directed graph with no cycles. A topological order for G is a sequential listing of all the vertices in G such that, for all vertices v, w∈G, if there is an edge from v to w , then v precedes w in the sequential listing. P. 580 Digraph Class, Topological Sort P. 579 Depth-First Algorithm P. 580-581 Breadth-First Algorithm P. 582 [12.5] A Greedy Algorithm: Shortest Paths P. 583
203级计算机专业数据结构课堂教学笔记 内部资料,仅供课堂教学使用 The problem of shortest paths: Given a directed graph in which each edge has a nonnegative weight or cost, find a path of least total weight from a given vertex, called the source, to every other vertex in the graph. P. 583 Method: We keep a set S of vertices whose closest distances to the source, vertex 0, are known and add one vertex to S at each stage. We maintain a table distance that gives, for each vertex V, the distance from 0 to v along a path all of whose vertices are nS, except possibly the last one. To determine what vertex to add to S at each step, we apply the greedy criterion of choosing the vertex v with the smallest distance recorded in the table distance, such that v is not already in distance. P. 584 Finding a Shortest Path P584 Example of shortest PathP585-586 Implementation P586-587 112.6 Minimal Spanning Trees P 588 Shortest paths from source 0 to all vertices in a network If the original network is based on a connected graph G, then the shortest paths from a particular source vertex to all other vertices in G form a tree that links up all the vertices of g A(connected)tree that is build up out of all the vertices and some of the edges of G is called a spanning tree of G DEFINITION: A minimal spanning tree of a connected network is a spanning tree such that the sum of the weights of it edges is as small as possible Two Spanning Trees P 589 Prim's algorithm for minimal Spanning trees P. 589-590 Start with a source vertex. Keep a set X of those vertices whose paths to source in the minimal spanning tree that we are building have been found. Keep the set Y of edges that link the vertices in X in the tree under construction. The vertices in X and edges in Y make up a small tree that grows to become our final spanning tree Initially, source is the only vertex in X, and Y is empty. At each step, we add an additional vertex to X: This vertex is chosen so that an edge back to X has as small as possible a weight. This minimal edge back to X is added to Y For implementation, we shall keep the vertices in X as the entries of a Boolean array component. We keep the edges in Y as the edges of a graph that will grow to give the output tree from our program We maintain an auxiliary table neighbor that gives, for each vertex v, the vertex of X whose edge to v has minimal cost vertices v, and distance is initialized by setting distance[v] to the weight of the edge from source to v if it exists and to infinity if not o To determine what vertex to add to X at each step, we choose the vertex v with the smallest value recorded in the table distance, such that v is not already in X. After this we must update our tables to reflect the change that we have made to X We do this by checking, for each vertex w not in X, whether there is an edge linking v and w, and if so, whether this edge has a weight less than distance w. In case there is an edge(v, w) with this property, we reset neighbor[ w] tov and distance w) to the weight of the edge Example of Prim's Algorithm P591 Implementation of Prims algorithm P 590-592 The class ofNetwork P 590 Read is overridden to make sure that the weight of any edge(v, w) matches that of the edge(w, v): In this way,we preserve our data structure from the potential corruption of undirected edges make empty (int size)creates a Network with size vertices and no edges dd edge adds an edge with a specified weight to a Network As for the shortest-path algorithm, we assume that the class Weight has comparison operators We expect clients to declare a largest possible Weight value called infinity The method of minimal spanning P592 Verification of Prim's algorithm P.593-594 [12.7]Graphs as Data Structures P 594 A Story P.594-559 o I married a widow who had a grown-up daughter. My father, who visited us quite often, fell in love with my step-daughter and married her. Hence, my father became my son-in-law, and my step-daughter became my mother Some months later, my wife gave birth to a son, who became the brother-in-law of my father as well as my uncle. The wife of my father, that is my step-daughter, also had a son. Thereby, I got a brother and at the same time a grandson My wife is my grandmother, since she is my mothers mother. Hence, I am my wife s husband and at the same time her step-grandson; in other words, I am my own grandfath Pointers and Pitfalls 4 items P 596 Errata: p. 591, Fig. 12. 13(g): Top circle should contain a 3
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 The problem of shortest paths: Given a directed graph in which each edge has a nonnegative weight or cost, find a path of least total weight from a given vertex, called the source, to every other vertex in the graph. P. 583 Method: We keep a set S of vertices whose closest distances to the source, vertex 0, are known and add one vertex to S at each stage. We maintain a table distance that gives, for each vertex v , the distance from 0 to v along a path all of whose vertices are in S , except possibly the last one. To determine what vertex to add to S at each step, we apply the greedy criterion of choosing the vertex v with the smallest distance recorded in the table distance, such that v is not already in distance. P. 584 Finding a Shortest Path P. 584 Example of Shortest Path P. 585-586 Implementation P. 586-587 [12.6] Minimal Spanning Trees P. 588 ⚫ Shortest paths from source 0 to all vertices in a network: ⚫ If the original network is based on a connected graph G, then the shortest paths from a particular source vertex to all other vertices in G form a tree that links up all the vertices of G. ⚫ A (connected) tree that is build up out of all the vertices and some of the edges of G is called a spanning tree of G. DEFINITION: A minimal spanning tree of a connected network is a spanning tree such that the sum of the weights of its edges is as small as possible. Two Spanning Trees P. 589 Prim’s Algorithm for Minimal Spanning Trees P. 589-590 ⚫ Start with a source vertex. Keep a set X of those vertices whose paths to source in the minimal spanning tree that we are building have been found. Keep the set Y of edges that link the vertices in X in the tree under construction. The vertices in X and edges in Y make up a small tree that grows to become our final spanning tree. ⚫ Initially, source is the only vertex in X, and Y is empty. At each step, we add an additional vertex to X: This vertex is chosen so that an edge back to X has as small as possible a weight. This minimal edge back to X is added to Y. ⚫ For implementation, we shall keep the vertices in X as the entries of a Boolean array component. We keep the edges in Y as the edges of a graph that will grow to give the output tree from our program. ⚫ We maintain an auxiliary table neighbor that gives, for each vertex v , the vertex of X whose edge to v has minimal cost. We also maintain a second table distance that records these minimal costs. If a vertex v is not joined by an edge to X we shall record its distance as the value infinity. The table neighbor is initialized by setting neighbor[v] to source for all vertices v, and distance is initialized by setting distance[v] to the weight of the edge from source to v if it exists and to infinity if not. ⚫ To determine what vertex to add to X at each step, we choose the vertex v with the smallest value recorded in the table distance, such that v is not already in X. After this we must update our tables to reflect the change that we have made to X. We do this by checking, for each vertex w not in X, whether there is an edge linking v and w, and if so, whether this edge has a weight less than distance[w]. In case there is an edge (v, w) with this property, we reset neighbor[w] to v and distance[w] to the weight of the edge. Example of Prim’s Algorithm P. 591 Implementation of Prim’s Algorithm P. 590-592 The class of Network P. 590 ⚫ Read is overridden to make sure that the weight of any edge (v, w) matches that of the edge (w, v): In this way, we preserve our data structure from the potential corruption of undirected edges. ⚫ make_empty(int size) creates a Network with size vertices and no edges. ⚫ add_edge adds an edge with a specified weight to a Network. ⚫ As for the shortest-path algorithm, we assume that the class Weight has comparison operators. ⚫ We expect clients to declare a largest possible Weight value called infinity. The method of minimal_spanning P. 592 Verification of Prim’s Algorithm P. 593-594 [12.7] Graphs as Data Structures P. 594 A Story P. 594-559 ⚫ I married a widow who had a grown-up daughter. My father, who visited us quite often, fell in love with my step-daughter and married her. Hence, my father became my son-in-law, and my step-daughter became my mother. ⚫ Some months later, my wife gave birth to a son, who became the brother-in-law of my father as well as my uncle. The wife of my father, that is my step-daughter, also had a son. Thereby, I got a brother and at the same time a grandson. ⚫ My wife is my grandmother, since she is my mother’s mother. Hence, I am my wife’s husband and at the same time her step-grandson; in other words, I am my own grandfather. Pointers and Pitfalls 4 items P.596 Errata :p. 591, Fig. 12.13(g): Top circle should contain a 3