Exam 2 Study Guide

• Simple Graph
• Starting vertex (optional, arbitrary)

• ccnum[]
  • Connected Component Number Array
  • A list containing the connected component number of the indexed vertex.
  • Vertices reachable from the starting vertex will have a connected component number of 1.
    • YOU NEED TO STATE YOU ARE USING CCNUM IF YOU ARE USING THIS FOR REACHABILITY ANALYSIS
• prev[]
  • A list containing the parent vertex of the indexed vertex, which can be used to create a path from the starting vertex to any reachable vertex.
  • Unreachable vertices and the starting vertex have a parent of nil.
• pre[]
  • A list containing the pre-visit number for the indexed vertex.
• post[]
  • A list containing the post-visit number for the indexed vertex.

• Finding connected components on a graph
• Finding a cycle in a graph
• Producing a path from starting vertex to a reachable vertex

O(n + m)

A simple, directed, acyclic graph in adjacency list format

• order[]
  • A list of vertices, sorted in topological ordering from source to sink. Note: This output is indexed numerically rather than by vertex.
  • All outputs from the run of Depth-First Search (DFS) are also available to you.

Finding the topological sorting in a DAG

O(n + m)

A simple, directed graph in adjacency list format

$G_{SCC} = \left(V_{SCC}, E_{SCC}\right)$

• The strongly connected components metagraph, provided in adjacency list format.
  • By construction, the metagraph is a DAG with vertices sorted from sink to source
    • This ordering is known as reverse topological ordering.
• All outputs from the final run of Depth-First Search (DFS) are also available to you.
  • This data is used to connect entities in the metagraph to the original input graph.
    • For example, the first vertex in $V_{SCC}$ represents all vertices with ccnum[v] = 1 from the DFS outputs from the original input graph.

• Finding strongly connected components on a graph
  • Particularly useful for finding source and sink SCCs

O(n + m)

• A simple graph in adjacency list format
• A starting vertex (not optional)

• dist[]
  • A list containing the unweighted distance from the starting vertex to the indexed vertex for all vertices in the graph.
    • Unreachable vertices have a distance of inf.
• prev[]
  • A list containing the parent vertex of the indexed vertex, which can be used to create a path from the starting vertex to any reachable vertex.
    • Unreachable vertices and the starting vertex have a parent of nil.

• Reachability analysis
• Unweighted shortest path determination
• Producing a path from starting vertex to a reachable vertex

O(n + m)

• A simple graph in adjacency list format
• A starting vertex
• A list of non-negative edge weights

• dist[]
  • A list containing the weighted distance from the starting vertex to the indexed vertex for all vertices in the graph.
    • Unreachable vertices have a distance of inf.
• prev[]
  • A list containing the parent vertex of the indexed vertex, which can be used to create a path from the starting vertex to any reachable vertex.
    • Unreachable vertices and the starting vertex have a parent of nil.

• Reachability analysis
• Weighted shortest path determination
• Producing a path from starting vertex to a reachable vertex

O((n + m) log n)

• A simple graph in adjacency list format
• A starting vertex
• A list of edge weights

• dist[]
  • A list containing the weighted distance from the starting vertex to the indexed vertex for all vertices in the graph.
    • Unreachable vertices have a distance of inf.
    • Values are based on the n-1 th iteration.
• prev[]
  • A list containing the parent vertex of the indexed vertex, which can be used to create a path from the starting vertex to any reachable vertex.
    • Unreachable vertices and the starting vertex have a parent of nil.
  • iter[][] - A 2-dimensional list containing the first indexed iteration’s shortest path from the starting vertex to the second indexed vertex.
    • For example, iter[3][v] contains the distance from the starting vertex to v at the end of the 3rd iteration.
    • This table contains iterations 0 through n.

• Reachability analysis
• Weighted shortest path determination
• Negative cycle detection
• Producing a path from starting vertex to a reachable vertex

O(nm)

• A simple graph in adjacency list format
• A list of edge weights

• dist[][]
  • A 2-dimensional list containing the weighted distance from the first indexed vertex to the second indexed vertex.
    • For example, dist[u][v] would contain the shortest path from vertex u to vertex v.
    • Unreachable vertex pairs have a distance of inf.
    • Values are based on the nth iteration.
• iter[][][]
  • A 3-dimensional list containing the first indexed iteration’s shortest path from the second indexed vertex to the third indexed vertex.
    • For example, iter[3][u][v] contains the distance from u to v at the end of the 3rd iteration.
    • This table contains iterations 0 through n.

• Reachability analysis
• Weighted shortest path determination
• Negative cycle detection

$O\left( n^3 \right)$

• A simple, connected, undirected graph in adjacency list format
• A list of edge weights

• edges[]
  • A list of n-1 edges that represent a minimum spanning tree for the input graph.

Producing a minimum spanning tree

O(m log n )

• A simple, connected, undirected graph in adjacency list format
• A list of edge weights

• prev[]
  • A list containing the parent vertex of the indexed vertex, which represent the connecting edges of a minimum spanning tree for the input graph.
    • The starting vertex is chosen arbitrarily and has a parent of nil.

Producing a minimum spanning tree

O(m log n)

• A simple, connected, directed graph in adjacency list format
• A list of positive, integer edge capacities
• A starting source vertex
• A terminating sink vertex

• flow[]
  • A list of edges representing the amount capacity used per each indexed edge such that the flow is maximized from the starting vertex to the terminating vertex.
• C
  • The value of the maximum flow from the starting vertex to the terminating vertex.

Finding max flows on a graph

O(mC)

• A simple, connected, directed graph in adjacency list format
• A list of positive, integer edge capacities
• A starting source vertex
• A terminating sink vertex

• flow[]
  • A list of edges representing the amount capacity used per each indexed edge such that the flow is maximized from the starting vertex to the terminating vertex.
• C
  • The value of the maximum flow from the starting vertex to the terminating vertex.

Finding max flows on a graph

$O(nm^2)$

• A Boolean formula in conjunctive normal form such that each clause contains at most 2 literals.
  • This formula is backed by a list of n variables, representing at most 2n literals and m clauses.

• assignments[]
  • A list indexable by the variables that back the original input formula containing whether that variable is set to true or false.
    • If the input is not satisfiable, this will instead return “NO”
  • All outputs from the Strongly Connected Components (SCC) run are also available to you.

• Example of how graphs algorithms can be used to solve a problem that starts in a non-graphs domain
• Converting a graph representation into a Boolean formula to determine satisfiability of the task at hand

O(n + m)