Black Box Algorithms

DFS

Inputs: simple graph (in adjacency list)

Output:

ccnum[] of connected components

prev[] of parent vertex

pre/post numbers

Runtime: O(n+m)

Uses: Finding connected components, finding a cycle, finding a path between vertices


Topological Sort

Input: Simple, directed, acyclic graph

Output: order[] of vertices from source to sink, [also DFS outputs]

Runtime: O(n+m)

Uses: Finding topo order of a DAG


SCC

Input: simple, directed graph

Output: G_SCC=(V_SCC,E_SCC) the SCC metagraph, [also DFS outputs]

Runtime: O(n+m)


BFS

Input: simple graph, starting vertex

Output: dist[] of unweighted distances from the starting vertex to indexed vertex, prev[] of parent vertices (used to create a path, and unreachable vertices have a parent of nil)

Runtime: O(n+m)

Uses: Reachability analysis, unweighted shortest path determination, finding a path


Dijkstras

Input: simple graph, starting vertex, non-negative edge weights

Output: dist[] containing weighted distance from start to index vertex, prev[] of parents

Runtime: O((n+m) log n)

Uses: Reachability, weighted shortest path, finding a path


Bellman-Fod

Input: Simple graph, starting vertex, edge weights

Output:

  • dist[] distance from starting vertex to index vertex - unreachable vertices have value of inf and values are based on the n-1 iteration.

  • Prev[] a list of the parents (unreachable are nil)

  • Iter[i][j] - a 2d list containing the i’th iteration of the path to the j’th vertex

Runtime: O(nm)

Uses: Reachability, weightest shortest path, negative cycle detection, finding paths

Floyd-Warshall (FW)

Input: simple graph and list of edge weights

Output:

  • dist[ u ][ v ] 2d list containing the shortest path from u to v (based on nth iteration)

  • iter [ i ][ u ][ v ] - a 3d list containing the i-th iteration of the distance from u to v

Runtime: O(n^3)

Uses: Reachability, weighted shorted path, negative cycle detection



Fun facts:

To find negative cycles using Bellman-Ford, compare n-1 iteration to n iteration. If they are different = negative cycle. If they aren’t different = no negative cycle.


To find negative cycles using Floyd-Warshall, look at the diagonals of the nth iteration. What do they need to be?


Kruskals

Input: a simple, connected, undirected graph AND a list of edge weights

Output: edges[ ] - a list of n-1 edges that represent a minimum spanning tree

Runtime: O(m log n)

Uses: produce a MST


Prims

Input: A simple, connected, undirected graph AND a list of edge weights

Output: prev[ ] - a list containing the parent vertex of the indexed vertex, which are the connecting edges of a MST for the input graph.

Runtime: O(m log n)


Floyd-Fulkerson

Input:

  • simple, connected, directed graph

  • a list of positive integer edge capacities

  • Starting and ending vertices

Output:

  • Flow[ ] - a list of edges representing the amount capacity used per each indexed edge

  • C - the value of the maximum flow from the starting vertex to the terminating vertex

Runtime: O(mC)


Edmonds-Karp

Input:

  • simple, connected, directed graph

  • a list of positive edge capacities (not necessarily integer)

  • Starting and ending vertices

Output:

  • Flow[ ] - a list of edges representing the amount capacity used per each indexed edge

  • C - the value of the maximum flow from the starting vertex to the terminating vertex

Runtime: O(nm^2)


2-SAT

Input: A boolean formula in conjunctive normal form such that each clause contains at most 2 literals

Output: assignments[ ] - a list indexable by the variables that back the original input formula containing whether that variable is set to true or false. Also all outputs of SCC are available.

Runtime: O(n+m)

Uses: converting non-graph domain problems to graph algorithms