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



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

Intro to Graphs

    • 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
      • Has exactly v-1 edges

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
    • 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

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