These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else



Download 186.06 Kb.
Page21/24
Date03.05.2017
Size186.06 Kb.
1   ...   16   17   18   19   20   21   22   23   24

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
    • The spanning tree of a graph whose edge weights sum to the minimum amount
    • Clearly, a graph has many spanning trees, not all of which are minimum
  • 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

Download 186.06 Kb.

Share with your friends:
1   ...   16   17   18   19   20   21   22   23   24




The database is protected by copyright ©sckool.org 2020
send message

    Main page