Blackbox Algorithms

Question 1

Undirected Graph

Depth First Search

Purpose, Input, Output, Runtime

Answer 1

Purpose: Perform a depth first search on an undirected graph G.

Input: Undirected Graph G = (V, E)

Output: 4 arrays: prev, pre, post each of length n

1. Prev[z] The parent index of vertex Z in the DFS visition
2. pre[z] the pre number of vertex z in the DFS visitation
3. post[z] the post number of the vertex z in the DFS visitation
4. (Optional) ccnum[z] the connected component number, if stored after SCC algorithm run on graph.

Runtime: O(n + m)

AKA:O(|V| + (|E|)

Question 2

Directed Graph

Depth First Search

Input, Output, Runtime

Answer 2

Purpose: Perform a depth first search on a directed graph G

Input: Directed Graph G=(V, E)

Output: 3 arrays, prev, pre, post, each of length n

1. prev[z]: The parent index of vertex Z in the DFS visitation
2. pre[z]: the pre order number of vertex Z
3. post[z]: the post order number of vertex Z.

Runtime: O(n + m)

AKA: O(|V| + |E|)

Question 3

Topographial Sort Directed

Purpose, input, output, runtime.

Answer 3

Purpose: Sort the verticies of an input graph in topological order. (Following left to right on resulting list means all preconditions will be done in order)

Input: directed acyclic graph G = (V, E)

Output: array topo length n

1. topo[i]: The vertex number of the i’th vertex in topological order from left to right (in descending post order)

Runtime: O(n + m) no need to do sort after DFS, we know post order numbers and their ranges.

AKA: O(|V| + |E|)

Question 4

Find Directed Strongly Connected Components

Purpose, input, output, runtime

Answer 4

Purpose: Find the strongly conencted components in a directed graph G.

Input: Directed Graph G=(V,E)

Output: Array ccnum of length n, array topo length t, where t is the number of SCCs, a directed acyclic metagraph Ga = Va, Ea

1. ccnum[z]: The connected component numer of vertex z for z in V.
2. topo[i] the SCC number for the ith SCC in topological order from left to right.
3. Ga = the SCC acyclic metagraph.

Runtime: O(n + m)

AKA: O(|V| + |E|)

Question 5

BFS_Explore

Purpose, Input, Output, Runtime, Note

Answer 5

Purpose: Explore a graph G (directed or undirected) from a given vertex s using the breath-frist strategy.

Input: a graph G = (V, E) (directed or undirected) and a “source” vertex s in V

Output: an array dist such that dist[u] = distantce (in terms of #edges crossed from vertex s to vertex u

Runtime: O(n + m). AKA: O(V + E)

note: dist[u] = +inf if the vertex u is not reachable from s, and BFS doesn’t account for edge weights, it can only find the shortest path from s to u in terms of edge count.

Question 6

dfs_explore

Purpose, input, output, runtime

Answer 6

Purpose: Explore a graph G (directed or undirected) from a given vertex v

Input: G=(V, E), v in Vertexes

Output: (For reachable nodes, -1 for the rest)

1. prev[z]
2. pre[z]
3. post[z]

Runtime: O(m) AKA O(E), only iterating over edges.

Question 7

Reverse Directed Graph

(Considered housekeeping not need to be black boxed)

Purpose, Input, output, runtime

Answer 7

Purpose: Reverse a given directed graph G

input: A driected Graph G=(V,E)
output: A reversed graph Gr = (Vr, Er)
runtime: O(n + m) AKA O(|V| + |E|)

Question 8

KruskalMST

Purpose, Input, Output, Runtime

+Note

Answer 8

Purpose: Finds the minimum spanning tree over an input undirected connected graph. (Sorts edges and selects edges not traversing graph)

Input: an undirected graph G = (V,E) and a weight function w such that w(u,v) = weight of edge.

Output: a set of edges X, which is the minimum spannign tree of G.

Runtime: O(m log n) AKA: O(E log (v))

Note:If the graph is not connected, we get a minimum spanning forest.

Question 9

Prim MST

Purpose, input, output, runtime, note

Answer 9

Purpose: Finds the minimum spanning tree G over an input undirected connected graph.

Input: An undirected graph G=(V,E) and a weight function w such that w(u,v) = weight of edge.

Ouptut: an array prev where prev[n] is the parent vertex number of vertex v. prev[root] = null by def.

runtime: O(m log(n)) AKA: O(E log (V))

Note: PRIM expects a connected graph. This is similar to dikjstra’s only instead of using the weight of the full path in the priority tree, it uses the weight of the solitary edge to build up on the frontier.

Question 10

Dijkstra’s Single Source Shortest Path

Purpose, input, output, runtime, note

Answer 10

Purpose: Finds the shortest path to all nodes from a source s in a weighted graph G (directed or undirected) with non-negative weights.

Input: A graph G=(V,E) directed or undirected, a source vertex and edge weights.

Output: dist[v] shortest distance from s to v, and prev[v] = prev of v in the shortest path from s to v.

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

Note: if the graph is connected, M dominates n+m and our time is O(mlog(n))

Question 11

Directed Acyclic Graph Single Shorted Path

Purpose, Input, output, runtime, note

Answer 11

Purpose: Find the shortest path and its length from the given source vertex s to all vertices v in V, in a directed acyclic weighted graph G=(V,E)

“Same as depth first search, topological sorting”

Input: a DAG G=(V,E), a source vertex s in V, and weights

Output: dist[v] the shortest distance from s to v and prev[v] = the prev of v in the shortest path from s to v.

Runtime: O(n + m)

Note: If it is not possible to reach a vertex u from s, then dist[u] = inf, and negative edges are allowed in this algorithm.

Question 12

BellmanFord Single Source Shortest Path

Purpose, Input, Output, Runtime, Note

Answer 12

Purpose: Find the shortest path to all nodes from a source s in a weight graph. With postiive or negative weights.

Input: A graph G=(V,E), a source vertex s in v, and edge weights

Output: Dist[v] shortest distance from s to v, prev[v] previous vertex in shortest path from s to v.

Runtime: O(nm)

Note: Normally runs in V-1 cycles, however runnin gone more cycle can help detect negative weighted cycles. Also only cycles reachable from s can be detected.

Question 13

FloydWarshall All Point Shortest Path

Purpose, input, output, runtime, note

Answer 13

Purpose: Finds the shortest path for all pairs, with positive or negative edge weights.

Input: A graph G(V,E) directed or undirected and edge weights.

Output: dist[s,t]: the shortest distance from s to t. (dist is an nxn array

Runtime O(n³)

Can detect any negative cycles by checking distance from node to itself, if it is less than zero, there is a negative weight cycle.

Question 14

Ford-Fulkerson (max flow/min cut)

Purpose, Input, output, runtime

Answer 14

Purpose: Finds the maximum st-flow in a flow network

Input: Flow Network G=(V,E) with capacities and source sink s & t

Output: Flow fe for e in Edges

Runtime: O(mC) where C is the size of the maximium flow.

Question 15

Edmonds-Karp (max flow/min-cut)

purpose, input, output, runtime, note

Answer 15

Purpose: Finds the maximium st-flow in a flow network (a directed graph G=(V,E) with capacities

Input: Flow network G=(V,E) with capacties, a source, and a sink

Ouput: Flow fe for edges

Runtime: O(m²n)

Note: Same as F-F, but uses a BFS to find augmenting paths to give a runtime without the C.

Question 16

Vertex Represenation (notes)

Simple Array:

cost of addition O(n)

cost of deletion O(n)

Question 17

Adjacency list format:

array of linked list. The index into the array is the vertex number. The linked list is a list of vertex numbers for outgoing edges.

Vertex Addition Cost O(n)

Vertex Deletion Cost O(n+m)

Edge Addition Cost O(1)

Edge Deletion Cost O(n)

Question 18

Adjacency Matrix Format (Best to avoid)

Matrix nxn intersection is edge.

Vertex Addition O(n²)

Vertex Deletion O(n)

Single Edge addition O(1)

Single Edge Deletion O(1)

Question 19

What is a Valid Flow?

What is a Maximum Flow?

Answer 19

A Valid flow in a flow network is a flow in g that satisfies all capacity constraints for the edges. (E.g. fe <= C(E)

A Maximum flow is a flow of maximum value.

Question 20

Let G = (V,E) be a flow network with source s, sink t and integer capacities. Suppose that we are given a maximum flow in G.

Suppose that the capacity of a single edge (u, v) ∈ E is increased by 1. Give an O(V + E) time algorithm to update the maximum flow.

Answer 20

Compose the residual graph on the original flow. Add a positive 1 capacity on the edge that has been increased. Using BFS, search for an augmenting path; if the path exists, we can update the flow, otherwise, the flow is unchanged. We only need to do this once, as the augmenting path, if it exists, increases the flow by 1, which is the maximum increase possible.

Question 21

Let G = (V,E) be a flow network with source s, sink t and integer capacities. Suppose that we are given a maximum flow in G.

Suppose that the capacity of a single edge (u, v) ∈ E is decreased by 1. Give an O(V + E) time algorithm to update the maximum flow.

Answer 21

Again, compose the residual graph on the original flow. If the decreased edge was not at capacity (that is, it still has positive residual capacity), then we can decrease the edge capacity by one without affecting the maximum flow. If not, then we add one to the negative capacity on the edge, and look for an augmenting path in reverse (going from t to s instead of from s to t) which includes the decreased edge.

Question 22

Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine whether the solution does indeed give a maximum flow.

Answer 22

First, verify that the solution is a valid flow by comparing the flow on each edge to the capacity of each edge, for cost O(|E|). If the solution is a valid flow, then compose the residual graph (O(|E|)) and look for an augmenting path, which using BFS is O(|V | + |E|). The existence of an augmenting path would mean the solution is not a maximum flow.