Graph Blackboxes

Question 1

EXPLORE

Answer 1

INPUT: graph G = (V, E) which is directed or undirected

OUTPUT: visited[u] set to true for all nodes u reachable from v

RUNTIME: O(m)

NOTE: ccnum, prev, post, pre are set in explore subroutine

Question 2

DFS

Answer 2

INPUT: graph G = (V, E) directed or undirected

OUTPUT:

• -> prev[z]: parent of z
• -> pre[z]: pre num
• -> post[z]: post num
• -> ccnum[z]: connected component # of vertex z (or –> SCC number if using this in SCC algorithm)

RUNTIME: O(m+n)

Question 3

Dijkstra’s

Answer 3

INPUT:

• -> graph G = (V,E)
• -> vertex s
• -> positive edge weights w

OUTPUT:

• -> dist[u]: distances from s to u (if possible)
• -> prev[z]: parent index of vertex z

RUNTIME: O((n+m) * logn)

Question 4

BFS

Answer 4

INPUT:

• -> graph G = (V,E) directed or undirected
• -> vertex s

OUTPUT:

• -> dist[u]: dist from s to u (in terms of number of edges)
• -> prev[z]: parent index of vertex z

RUNTIME: O(n + m)

NOTE: used for unweighted single source shortest path

Question 5

SCC

Answer 5

INPUT:
Graph G = (V, E), directed

OUTPUT:
Handwave: Strongly Connected Components and Metagraph

Runtime:
O(n + m)

Question 6

2-SAT

Answer 6

INPUT:
formula f in CNF with n variables and m clauses, each of size 2

OUTPUT:
boolean assignment for each variable or “no” if not satisfiable (satisfied when graph is empty)

RUNTIME:
O(n + m)

Question 7

Kruskals

Answer 7

INPUT:
Directed graph G = (V,E)
Edge weights w(e)

OUTPUT:
minimum spanning tree of G

RUNTIME:
O(m logn)

Question 8

Prims

Answer 8

Everything same as Kruskal’s but runtime is O(n+m logn)

Question 9

Building Residual Network

Answer 9

INPUT:
G(V,E), c, f

OUTPUT:
residual graph (which includes residual capacities)

RUNTIME:
O(n + m)