›
›

Cơ sở dữ liệu - Chapter 9: Graph

pdf 85 trang vanle 4480
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Chapter 9: Graph", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfco_so_du_lieu_chapter_9_graph.pdf

Nội dung text: Cơ sở dữ liệu - Chapter 9: Graph

  1. Chapter 9 - Graph • 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. • If the pairs are unordered, G is called an undirected graph or a graph. Otherwise, G is called a directed graph or a digraph. • Two vertices in an undirected graph are called adjacent if there is an edge from the first to the second. 1
  2. Chapter 9 - Graph • A path is a sequence of distinct vertices, each adjacent to the next. • A cycle is a path containing at least three vertices such that the last vertex on the path is adjacent to the first. • A graph is called connected if there is a path from any vertex to any other vertex. • A free tree is defined as a connected undirected graph with no cycles. 2
  3. Chapter 9 - Graph • In a directed graph a path or a cycle means always moving in the direction indicated by the arrows. • 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 3
  4. Examples of Graph 4
  5. Examples of Graph 5
  6. Digraph as an adjacency table Directed graph Adjacency set Adjacency table Digraph count // Number of vertices edge > > // Adjacency table End Digraph 6
  7. Weighted-graph as an adjacency table Weighted-graph vertex vector adjacency table WeightedGraph count // Number of vertices edge >> // Adjacency table End WeightedGraph 7
  8. Weighted-graph as an adjacency list 8
  9. Digraph as an adjacency list Directed graph contiguous structure linked structure mixed structure 9
  10. Digraph as an adjacency list (not using List ADT) VertexNode first_edge next_vertex Directed graph End VertexNode first_vertex EdgeNode vertex_to next_edge End EdgeNode DiGraph first_vertex End DiGraph linked structure 10
  11. Digraph as an adjacency list (using List ADT) head digraph GraphNode vertex // (key field) head 0 1 2 adjVertex > indegree are hidden 1 head 2 3 outdegree from the isMarked image below 2 head End GraphNode 3 head 0 1 2 GraphNode ADT List is linked list: vertex adjVertex DiGraph 2 head digraph > End DiGraph 11
  12. Digraph as an adjacency list (using List ADT) GraphNode vertex // (key field) adjVertex > indegree outdegree isMarked End GraphNode mixed list ADT List is contiguous list: DiGraph digraph > End DiGraph 12
  13. Digraph as an adjacency list (using List ADT) GraphNode vertex // (key field) adjVertex > indegree outdegree isMarked End GraphNode contiguous list ADT List is contiguous list: DiGraph digraph > End DiGraph 13
  14. GraphNode GraphNode() // constructor of GraphNode 1. indegree = 0 2. outdegree = 0 3. adjVertex.clear() // By default, constructor of adjVertex made it empty. End GraphNode GraphNode vertex adjVertex head 14
  15. Operations for Digraph  Insert Vertex  Delete Vertex  Insert edge  Delete edge  Traverse 15
  16. Digraph Digraph private: digraph > // using of List ADT . Remove_EdgesToVertex(val VertexTo ) public: InsertVertex (val newVertex ) DeleteVertex (val Vertex ) InsertEdge (val VertexFrom , val VertexTo ) DeleteEdge (val VertexFrom , val VertexTo ) // Other methods for Graph Traversal. End Digraph 16
  17. Methods of List ADT Methods of Digraph will use these methods of List ADT: Insert (val DataIn ) // (success, overflow) Search (ref DataOut ) // (found, notFound) Remove (ref DataOut ) // (success , notFound) Retrieve (ref DataOut ) // (success , notFound) Retrieve (ref DataOut , position ) // (success , range_error) Replace (val DataIn , position ) // (success, range_error) Replace (val DataIn , val DataOut ) // (success, notFound) isFull() isEmpty() Size() 17
  18. Insert New Vertex into Digraph InsertVertex (val newVertex ) Inserts new vertex into digraph. Pre newVertex is a vertex needs to be inserted. Post if the vertex is not in digraph, it has been inserted and no edge is involved with this vertex. Return success, overflow, or duplicate_error 18
  19. Insert New Vertex into Digraph InsertVertex (val newVertex ) 1. DataOut.vertex = newVertex 2. if (digraph.Search(DataOut) = success) 1. return duplicate_error 3. else 1. return digraph.Insert(DataOut) // success or overflow End InsertVertex GraphNode vertex // (key field) adjVertex > indegree outdegree isMarked End GraphNode 19
  20. Delete Vertex from Digraph DeleteVertex (val Vertex ) Deletes an existing vertex. Pre Vertex is the vertex needs to be removed . Post if Vertex 's indegree <>0, the edges ending at this vertex have been removed. Finally, this vertex has been removed. Return success, or notFound Uses Function Remove_EdgeToVertex. 20
  21. Delete Vertex from Digraph DeleteVertex (val Vertex ) 1. DataOut.vertex = Vertex 2. if (digraph.Retrieve(DataOut) = success) 1. if (DataOut.indegree>0) 1. digraph.Remove_EdgeToVertex(Vertex) 2. digraph.Remove(DataOut) 3. return success 3. else 1. return notFound GraphNode End DeleteVertex vertex // (key field) adjVertex > indegree outdegree isMarked End GraphNode 21
  22. Auxiliary function Remove all Edges to a Vertex Remove_EdgesToVertex(val VertexTo ) Removes all edges from any vertex to VertexTo if exist. 1. position = 0 2. loop (digraph.Retrieve(DataFrom, position) = success) 1. if (DataFrom.outdegree>0) 1. if (DataFrom.adjVertex.Remove(VertexTo) = success) 1. DataFrom.outdegree = DataFrom.outdegree - 1 2. digraph.Replace(DataFrom, position) 2. position = position + 1 GraphNode End Remove_EdgesToVertex vertex // (key field) adjVertex > indegree outdegree isMarked End GraphNode 22
  23. Insert new Edge into Digraph InsertEdge (val VertexFrom , val VertexTo ) Inserts new edge into digraph. Post if VertexFrom and VertexTo are in the digraph, and the edge from VertexFrom to VertexTo is not in the digraph, it has been inserted. Return success, overflow, notFound_VertexFrom , notFound_VertexTo or duplicate_error 23
  24. 1. DataFrom.vertex = VertexFrom 2. DataTo.vertex = VertexTo 3. if ( digraph.Retrieve(DataFrom) = success ) 1. if ( digraph.Retrieve(DataTo) = success ) 1. newData = DataFrom 2. if ( newData.adjVertex.Search(VertexTo) = found ) 1. return duplicate_error 3. if ( newData.adjVertex.Insert(VertexTo) = success ) 1. newData.outdegree = newData.outdegree +1 2. digraph.Replace(newData, DataFrom) 3. return success GraphNode 4. else vertex // (key field) 1. return overflow adjVertex > 2. else 1. return notFound_VertexTo indegree 4. else outdegree 1. return notFound_VertexFrom isMarked End InsertEdge End GraphNode 24
  25. Delete Edge from Digraph DeleteEdge (val VertexFrom , val VertexTo ) Deletes an existing edge in the digraph. Post if VertexFrom and VertexTo are in the digraph, and the edge from VertexFrom to VertexTo is in the digraph, it has been removed Return success, notFound_VertexFrom , notFound_VertexTo or notFound_Edge 25
  26. 1. DataFrom.vertex = VertexFrom 2. DataTo.vertex = VertexTo 3. if ( digraph.Retrieve(DataFrom) = success ) 1. if ( digraph.Retrieve(DataTo) = success ) 1. newData = DataFrom 2. if ( newData.adjVertex.Remove(VertexTo) = success ) 1. newData.outdegree = newData.outdegree -1 2. digraph.Replace(newData, DataFrom) 3. return success 3. else 1. return notFound_Edge GraphNode 2. else vertex // (key field) 1. return notFound_VertexTo adjVertex > 4. else indegree 1. return notFound_VertexFrom outdegree End DeleteEdge isMarked End GraphNode 26
  27. Graph Traversal  Depth-first traversal: analogous to preorder traversal of an oredered tree.  Breadth-first traversal: analogous to level-by-level traversal of an ordered tree. 27
  28. Depth-first traversal 28
  29. Breadth-first traversal 29
  30. Depth-first traversal DepthFirst (ref Operation ( ref Data )) Traverses the digraph in depth-first order. Post The function Operation has been performed at each vertex of the digraph in depth-first order. Uses Auxiliary function recursiveTraverse to produce the recursive depth-first order. 30
  31. Depth-first traversal DepthFirst (ref Operation ( ref Data )) 1. loop (more vertex v in Digraph) 1. unmark (v) 2. loop (more vertex v in Digraph) 1. if (v is unmarked) 1. recursiveTraverse (v, Operation) End DepthFirst 31
  32. Depth-first traversal recursiveTraverse (ref v , ref Operation ( ref Data ) ) Traverses the digraph in depth-first order. Pre v is a vertex of the digraph. Post The depth-first traversal, using function Operation, has been completed for v and for all vertices that can be reached from v. Uses function recursiveTraverse recursively. 32
  33. Depth-first traversal recursiveTraverse(ref v , ref Operation ( ref Data ) ) 1. mark(v) 2. Operation(v) 3. loop (more vertex w adjacent to v) 1. if (vertex w is unmarked) 1. recursiveTraverse (w, Operation) End Traverse 33
  34. Breadth-first traversal BreadthFirst (ref Operation ( ref Data ) ) Traverses the digraph in breadth-first order. Post The function Operation has been performed at each vertex of the digraph in breadth-first order. Uses Queue ADT. 34
  35. // BreadthFirst 1. queueObj 2. loop (more vertex v in digraph) 1. unmark(v) 3. loop (more vertex v in Digraph) 1. if (vertex v is unmarked) 1. queueObj.EnQueue(v) 2. loop (NOT queueObj .isEmpty()) 1. queueObj.QueueFront(w) 2. queueObj.DeQueue() 3. if (vertex w is unmarked) 1. mark(w) 2. Operation(w) 3. loop (more vertex x adjacent to w) 1. queueObj.EnQueue(x) End BreadthFirst 35
  36. Topological Order A topological order for G, a directed graph with no cycles, 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. 36
  37. Topological Order 37
  38. Topological Order 38
  39. Applications of Topological Order Topological order is used for:  Courses available at a university, • Vertices: course. • Edges: (v,w), v is a prerequisite for w. • A topological order is a listing of all the courses such that all perequisites for a course appear before it does.  A glossary of technical terms: no term is used in a definition before it is itself defined.  The topics in the textbook. 39
  40. Topological Order DepthTopoSort (ref TopologicalOrder ) Traverses the digraph in depth-first order and made a list of topological order of digraph's vertices. Pre Acyclic digraph. Post The vertices of the digraph are arranged into the list TopologicalOrder with a depth-first traversal of those vertices that do not belong to a cycle. Uses List ADT and function recursiveDepthTopoSort to perform depth-first traversal. Idea: • Starts by finding a vertex that has no successors and place it last in the list. • Repeatedly add vertices to the beginning of the list. • By recursion, places all the successors of a vertex into the topological order. • Then, place the vertex itself in a position before any of its successors. 40
  41. Topological Order 41
  42. Topological Order DepthTopoSort (ref TopologicalOrder ) 1. loop (more vertex v in digraph) 1. unmark(v) 2. TopologicalOrder.clear() 3. loop (more vertex v in Digraph) 1. if (vertex v is unmarked) 1. recursiveDepthTopoSort(v, TopologicalOrder) End DepthTopoSort 42
  43. Topological Order recursiveDepthTopoSort (val v , ref TopologicalOrder ) Pre Vertex v in digraph does not belong to the partially completed list TopologicalOrder. Post All the successors of v and finally v itself are added to TopologicalOrder with a depth-first order traversal. Uses List ADT and the function recursiveDepthTopoSort. Idea: • Performs the recursion, based on the outline for the general function traverse. • First, places all the successors of v into their positions in the topological order. • Then, places v into the order. 43
  44. Topological Order recursiveDepthTopoSort (val v , ref TopologicalOrder ) 1. mark(v) 2. loop (more vertex w adjacent to v) 1. if (vertex w is unmarked) 1. recursiveDepthTopoSort(w, TopologicalOrder) 3. TopologicalOrder.Insert(0, v) End recursiveDepthTopoSort 44
  45. Topological Order BreadthTopoSort (ref TopologicalOrder ) Traverses the digraph in depth-first order and made a list of topological order of digraph's vertices. Post The vertices of the digraph are arranged into the list TopologicalOrder with a breadth-first traversal of those vertices that do not belong to a cycle. Uses List and Queue ADT. Idea: • Starts by finding the vertices that are not successors of any other vertex. • Places these vertices into a queue of vertices to be visited. • As each vertex is visited, it is removed from the queue and placed in the next available position in the topological order (starting at the beginning). • Reduces the indegree of its successors by 1. • The vertex having the zero value indegree is ready to processed and is places into the queue. 45
  46. Topological Order 46
  47. BreadthTopoSort (ref TopologicalOrder ) 1. TopologicalOrder.clear() 2. queueObj 3. loop (more vertex v in digraph) 1. if (indegree of v = 0) 1. queueObj.EnQueue(v) 4. loop (NOT queueObj.isEmpty()) 1. queueObj.QueueFront(v) 2. queueObj.DeQueue() 3. TopologicalOrder.Insert(TopologicalOrder.size(), v) 4. loop (more vertex w adjacent to v) 1. decrease the indegree of w by 1 2. if (indegree of w = 0) 1. queueObj.EnQueue(w) End BreadthTopoSort 47
  48. Shortest Paths • Given a directed graph in which each edge has a nonnegative weight. • Find a path of least total weight from a given vertex, called the source, to every other vertex in the graph. • A greedy algorithm of Shortest Paths: Dijkstra's algorithm (1959). 48
  49. Dijkstra's algorithm .Let tree is the subgraph contains the shotest paths from the source vertex to all other vertices. .At first, add the source vertex to the tree. .Loop until all vertices are in the tree: • Consider the adjacent vertices of the vertices already in the tree. • Examine all the paths from those adjacent vertices to the source vertex. • Select the shortest path and insert the corresponding adjacent vertex into the tree. 49
  50. Dijkstra's algorithm in detail • S: Set of vertices whose closest distances to the source are known. • Add one vertex to S at each stage. • For each vertex v, maintain the distance from the source 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, apply the greedy criterion of choosing the vertex v with the smallest distance. • Add v to S. • Update distance from the source for all w not in S, if the path through v and then directly to w is shorter than the previously recorded distance to w. 50
  51. Dijkstra's algorithm 51
  52. Dijkstra's algorithm 52
  53. Dijkstra's algorithm 53
  54. Dijkstra's algorithm 54
  55. Dijkstra's algorithm 55
  56. Dijkstra's algorithm 56
  57. Dijkstra's algorithm ShortestPath (val source , ref listOfShortestPath >) Finds the shortest paths from source to all other vertices in digraph. Post Each node in listOfShortestPath gives the minimal path weight from vertex source to vertex destination in distance field. DistanceNode destination distance End DistanceNode 57
  58. // ShortestPath 1. listOfShortestPath.clear() 2. Add source to set S 3. loop (more vertex v in digraph) // Initiate all distances from source to v 1. distanceNode.destination = v 2. distanceNode.distance = weight of edge(source, v) // = infinity if // edge(source,v) isn't in digraph. 3. listOfShortestPath.Insert(distanceNode) 4. loop (more vertex not in S) // Add one vertex v to S on each step. 1. minWeight = infinity // Choose vertex v with smallest distance. 2. loop (more vertex w not in S) 1. Find the distance x from source to w in listOfShortestPath 2. if (x 2. minWeight = x distance 3. Add v to S. End DistanceNode 58
  59. // ShortestPath (continue) 4. loop (more vertex w not in S) // Update distances from source // to all w not in S 1. Find the distance x from source to w in listOfShortestPath 2. if ( (minWeight + weight of edge from v to w) distance End DistanceNode 59
  60. Another example of Shortest Paths Select the adjacent vertex having minimum path to the source vertex 60
  61. Minimum spanning tree DEFINITION: Spanning tree: tree that contains all of the vertices in a connected graph. Minimum spanning tree: spanning tree such that the sum of the weights of its edges is minimal. 61
  62. Spanning Trees Two spanning trees in a network 62
  63. A greedy Algorithm: Minimum Spanning Tree  Shortest path algorithm in a connected graph found an its spanning tree.  What is the algorithm finding the minimum spanning tree?  A small change to shortest path algorithm can find the minimum spanning tree, that is Prim's algorithm since 1957. 63
  64. Prim's algorithm .Let tree is the minimum spanning tree. .At first, add one vertex to the tree. .Loop until all vertices are in the tree: • Consider the adjacent vertices of the vertices already in the tree. • Examine all the edges from each vertices already in the tree to those adjacent vertices. • Select the smallest edge and insert the corresponding adjacent vertex into the tree. 64
  65. Prim's algorithm in detail • Let S is the set of vertices already in the minimum spanning tree. • At first, add one vertex to S. • For each vertex v not in S, maintain the distance from a vertex x to v, where x is a vertex in S and the edge(x,v) is the smallest in all edges from another vertices in S to v (this edge(x,v) is called the distance from S to v). As usual, all edges not being in graph have infinity value. • To determine what vertex to add to S at each step, apply the greedy criterion of choosing the vertex v with the smallest distance from S. • Add v to S. • Update distances from S to all vertices v not in S if they are smaller than the previously recorded distances. 65
  66. Prim's algorithm Select the adjacent vertex having minimum edge to the vertices already in the tree. 66
  67. Prim's algorithm MinimumSpanningTree (val source , ref tree ) Finds the minimum spanning tree of a connected component of the original graph that contains vertex source. Post tree is the minimum spanning tree of a connected component of the original graph that contains vertex source. Uses local variables: DistanceNode • Set S vertexFrom • listOfDistanceNode vertexTo • continue distance End DistanceNode 67
  68. 1. tree.clear() 2. tree.InsertVertex(source) 3. Add source to set S 4. listOfDistanceNode.clear() 5. distanceNode.vertexFrom = source 6. loop (more vertex v in graph)//Initiate all distances from source to v 1. distanceNode.vertexTo = v 2. distanceNode.distance = weight of edge(source, v) // = infinity if // edge(source,v) isn't in graph. 3. listOfDistanceNode.Insert(distanceNode) DistanceNode vertexFrom vertexTo distance End DistanceNode 68
  69. 7. continue = TRUE 8. loop (more vertex not in S) and (continue) //Add one vertex to S on // each step 1. minWeight = infinity //Choose vertex v with smallest distance toS 2. loop (more vertex w not in S) 1. Find the node in listOfDistanceNode with vertexTo is w 2. if (node.distance vertexTo distance End DistanceNode 69
  70. 3. if (minWeight weight of edge(v,w) ) 1. node.vertexFrom = v 2. node.distance = weight of edge(v,w) ) 3. Replace this node with its old node in listOfDistance 4. else DistanceNode 1. continue = FALSE vertexFrom End MinimumSpanningTree vertexTo distance End DistanceNode 70
  71. Maximum flows 71
  72. Maximum flows 72
  73. Maximum flows 73
  74. Maximum flows 74
  75. Maximum flows 75
  76. Matching 76
  77. Matching 77
  78. Matching 78
  79. Matching 79
  80. Matching 80
  81. Graph coloring 81
  82. Graph coloring 82
  83. Graph coloring 83
  84. Graph coloring 84
  85. Graph coloring 85