Page 20/24 Date 03.05.2017 Size 186.06 Kb. #18863
Plusses: Theta(e) memory For sparse graphs this could be much less than v2 Theta(d) to find neighbors of a vertex d is the degree of a vertex (# of neighb) For sparse graphs this could be much less than v Minuses Theta(e) memory For dense graphs, nodes will use more memory than simple location in adjacency matrix Theta(v) worst case to find one neighbor Linked list gives sequential access to nodes – neighbor could be at end of the list Intro to Graphs More Graph Definitions Path: A sequence of adjacent vertices Simple Path: A path in which no vertices are repeated Simple Cycle: A simple path except that the last vertex is the same as the first Connected Graph: A graph in which a path exists between all vertex pairs Connected Component: connected subgraph of a graph Acyclic Graph: A graph with no cycles Tree: A connected, acyclic graph Graph Traversals How to traverse a graph Unlike linear data structures, it is not obvious how to systematically visit all vertices in a graph Two famous, well-known traversals Depth First Search (DFS) Visit deep into the graph quickly, branching in other directions only when necessary Breadth First Search (BFS) Visit evenly in all directions Visit all vertices distance i from starting point before visiting any vertices distance i+1 from starting point DFS DFS is usually done recursively Current node recursively visits first unseen neighbor What if we reach a "dead-end" (i.e. vertex with no unseen neighbors)? Backtrack to previous call, and look for next unseen neighbor in that call See code in graphs graphs1.txt See example in graph.doc See trace on board from in-class notes BFS BFS is usually done using a queue Current node puts all of its unseen neighbors into the queue Vertices that have been seen but not yet visited are called the FRINGE Front item in the queue is the next vertex to be visited Algorithm continues until queue is empty See graphs1.txt and graph.doc See trace on board from in-class example DFS and BFS Both DFS and BFS Are initially called by a "search" function If the graph is connected, the search function will call DFS or BFS only one time, and (with a little extra code) a SPANNING TREE for the graph is built If the graph is not connected , the search function will call DFS or BFS multiple times First call of each will terminate with some vertices still unseen, and loop in "search" will iterate to the next unseen vertex, calling visit() again Each call (with a little extra code) will yield a spanning tree for a connected component of the graph DFS and BFS Run-times Run-times? DFS and BFS have the same run-times, since each must look at every edge in the graph twice However, run-times differ depending upon how the graphs are represented Recall that we can represent a graph using either an adjacency matrix or an adjacency list DFS and BFS Run-times Adjacency Matrix For a vertex to consider all of its neighbors we must traverse a row in the matrix -> Theta(v) Since all vertices consider all neighbors, the total run-time is Theta(v2) Adjacency List For a vertex to consider all of its neighbors we must traverse its list in the adjacency list array Each list may vary in length However, since all vertices consider all neighbors, we know that all adjacency list nodes are considered This is 2e, so the run-time here is Theta(v + e) We need the v in there since e could be less than v (even 0). In this case we still need v time to visit the nodes Biconnected Graph A biconnected graph has at least 2 distinct paths (no common edges or vertices) between all vertex pairs Idea: If one path is disrupted or broken, there is always an alternate way to get there Any graph that is not biconnected has one or more articulation points Vertices, that, if removed, will separate the graph See on board and bicon.html for example Any graph that has no articulation points is biconnected Thus we can determine that a graph is biconnected if we look for, but do not find any articulation points Articulation Points How to find articulation points? Variation of DFS Consider graph edges during DFS Tree Edge: edge crossed when connecting a new vertex to the spanning tree Back Edge: connects two vertices that were already in the tree when it was considered These back edges are critical in showing biconnectivity These represent the "alternate" paths between vertices in the graph Will be used in finding articulation points Articulation Points Consider now the DFS spanning tree in a "top-to-bottom" way Root is the top node in the tree , with DFS # = 1 Every vertex "lower" in the tree has a DFS number that is larger than the vertices that are "higher" in the tree (along path back to the root) Given this DFS spanning tree A vertex, X is not an articulation point if every child of X, say Y, is able to connect to a vertex "higher" in the tree (above X, with smaller DFS # than X) without going through X Share with your friends:
The database is protected by copyright ©sckool.org 2023
send message
