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

 Page 20/24 Date 03.05.2017 Size 186.06 Kb. #18863

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

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

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