Page 21/24 Date 03.05.2017 Size 186.06 Kb.

Articulation Points Connection does not have to be a direct edge We could go down through Y's descendents, then eventually back up to a vertex above X If any child is not able to do this, X is an articulation point How to determine this on the computer? For each vertex, when we visit it, we need to keep track of the minimum DFS # that we can reach from this vertex and any of its descendents We then use this min reachable DFS # to determine if a vertex is an articulation point or not: Articulation Points int visit(int k) // DFS to find articulation points { struct node *t; int m, min; val[k] = ++id; // assign DFS number to current vertex min = id; // initialize min reachable vertex to DFS // number of vertex itself for (t = adj[k]; t != z; t = t->next) // go through adj list if (val[t->v] == unseen) // if neighbor is unseen, will { // be a child in DFS tree m = visit(t->v); // get min reachable DFS # of child // via recursive call if (m < min) min = m; // if this is a smaller DFS # // than previous, update min if (m >= val[k]) cout << name(k); // if it is >= to // current DFS #, node is an } // articulation point else if (val[t->v] < min) min = val[t->v]; // seen neighbor // this is a back edge. If DFS # of return min ; // this neighbor less than previous, } // update min Articulation Points Algorithm shown works for all vertices except the root of the DFS tree Child of root cannot possibly reach a smaller DFS # than that of the root, since the root has DFS # 1 Root of DFS tree is an articulation point if it has two or more children in the DFS tree Idea is that since we backtrack only when necessary in the DFS algorithm, having two children in the tree means that we couldn't reach the second child except by going back through the root This implies that the first child and second child have no way of connecting except through the root Thus in this case the root is an articulation point Weighted Graphs In unweighted graphs, all edges are equivalent Often in modeling we need edges to represent distance, flow, capacity, bandwidth, etc Thus we must put WEIGHTS on the edges to represent these values Representations: In an adjacency matrix , we can substitute the weight for one (zero still means no edge) In an adjacency list, we can add a field to our linked list nodes for weight of the edge Spanning Trees and Shortest Paths In an unweighted graph, we have seen algorithms to determine Spanning Tree of the graph Both DFS and BFS generate this during the traversal process Shortest Path between two vertices BFS does this by determining spanning tree based on number of edges vertex is away from starting point The spanning tree generated by BFS shows the shortest path (in terms of number of edges) from the starting vertex to all other vertices in the graph However, in a weighted graph, these ideas can be more complex MSTs and Weighted Shortest Paths Minimum Spanning Tree Weighted Shortest Path The path between two vertices whose edge weights sum to the minimum value Note that now the fewest edges does not necessarily imply the shortest path Finding the MST Prim's Algorithm Idea of Prim's is very simple: Let T be the current tree, and T' be all vertices and edges not in the current tree Initialize T to the starting vertex (T' is everything else) while (#vertices in T < v) Find the smallest edge connecting a vertex in T to a vertex in T' Add the edge and vertex to T (remove them from T') As is often the case , implementation is not as simple as the idea Finding the MST Naïve implementation: At each step look at all possible edges that could be added at that step Let's look at the worst case for this impl: Complete graph (all edges are present) Step 1: (v-1) possible edges (from start vertex) Step 2: 2(v-2) possible edges (first two vertices each have (v-1) edges, but shared edge between them is not considered) Step 3: 3(v-3) possible edges (same idea as above) … Total: Sum (i = 1 to v-1) of i(v-i) This evaluates to Theta(v3) Finding the MST Better implementation: Do we have to consider so many edges at each step? No. Instead, let's just keep track of the current "best" edge for each vertex in T' Then at each step we do the following: Look at all of the "best" edges for the vertices in T' Add the overall best edge and vertex to T Update the "best" edges for the vertices remaining in T', considering now edges from latest added vertex This is the idea of Priority First Search (PFS) PFS In the PFS implementation (adj. list) "Best" edges for each vertex are kept in the val[] array and are also maintained in a priority queue At each step the overall best vertex (i.e. the one with the smallest edge) is removed from the PQ Algorithm continues until the PQ is empty Adj. matrix implementation has some important differences – see later notes See graphs2.txt and handout for trace Also see PFS.cpp for commented code Share with your friends:

The database is protected by copyright ©sckool.org 2020

send message