Graph Algorithms Flashcards
Depth First Search
Intuition: Explores a graph by visiting the first unexplored vertex adjacent to the vertex it’s currently looking at. It does this until it can’t find any unexplored adjacent vertices. It then backtracks until it either finds an unexplored vertex or stops.
Facts:
- Uses stack
- Creates dfs forest
Pseudo:
DFS(G, u) {
u.visited = true
for v in u.adjacent {
if !v.visited {
DFS(G, v)
}
}
}
O(V + E) running time
O(V) space (Stack can have at most |V| items)
Breadth First Search
Intuition: Explores a graph by first visiting all of its adjacent vertices before visiting all of its adjacent vertices’ adjacent vertices and so on.
Facts:
- Uses queue
- Creates bfs tree
Pseudo: q = new Queue() s = starting vertex
q.add(s)
while !q.isEmpty {
u = q.pop()
u.visited = true
for v in u.adjacent {
if !v.visited {
q.add(v)
}
}
}
O(V + E) running time
O(V) space
Kruskal’s Algorithm
Intuition: Builds an MST by, at each step, choosing the lowest weight edge from the graph that does not create a cycle in the current MST.
Facts:
- Each edge added combines distinct components
Pseudo:
A = empty MST
for edge(u, v) in Graph (ordered ascendingly by weight) {
if u and v not in same component {
add (u, v) to A
}
}
O(E log V) running time
O(V) space
Prim’s Algorithm
Intuition: Start at arbitrary vertex in graph. At each step, adds lowest cost edge that connects MST to vertex not already in MST.
Pseudo:
T = empty MST
while T not MST {
get minimum weight edge to vertex not in T
}
O(E + VlogV) running time
O(V) space
Dijkstra’s Algorithm
Intuition: Find the least weight paths from a starting node to all other nodes in graph (SSSP). At each step, finds the unvisited node with minimum distance and relaxes each of its edges.
Facts:
- Depends on min priority queue to select the node with the lowest weight path that has not yet been visited at each step
Pseudo:
q = new min-priority-queue()
for u in G {
u.dist = infinity
u.parent = null
if u not startVert {
q.add(u)
}
}
while !q.isEmpty {
u = q.getMinDist()
for v in u.adjacent {
if !v.visited and u.dist + weight(u, v) < v.dist {
v.dist = u.dist + weight(u, v)
v.parent = u
}
}
O(E + VlogV) running time (when using fibonacci heap)
O(V) space
Detect Cycle in Directed Graph
Intuition: Traverse graph using DFS while maintaining list of nodes on stack. Before recursing to next level, make sure next node is not on stack.
Pseudo:
CheckCycles(G, u, stack) {
for v in u.adjacent {
if v in stack {
return true
}
CheckCycles(G, v, stack.append(u)
}
}
O(V + E) running time (because DFS)
O(V) space
Kosaraju’s Algorithm
Intuition: Finds the strongly connected components of a directed graph by performing two passes of DFS; once on the graph and again on the transpose.
Facts:
- Maintains a stack of vertices added according to their finish times during the first round of DFS
O(V + E) running time (2 x DFS)
O(V) space
Bellman Ford
Intuition: SSSP algorithm that also works on graphs with negative weight edges. Works by “relaxing” all edges in graph |V| - 1 times.
Facts:
- Can detect the presence of negative weight cycles in a graph by performing a |V|-th relaxation of the edges and checking if the distances of any nodes has changed.
O(V^2) average running time O(v^3) in worst case (Worst case occurs in case of complete graph)
O(V) space
Topological Sort
Intuition: Creates linear ordering of vertices in directed acyclic graph (DAG) such that if u appears before v, then there is an edge (u, v) in graph. Performs DFS on graph and pushes vertices to stack in the order that they finish. Stack then contains topologically sorted vertices.
Facts:
- Often used for ordering events that require some events to happen first.
- Method is identical to first run of Kosaraju’s algorithm.
O(V + E) running time (DFS)
O(V) space
Floyd-Warshall Algorithm
Intuition: Solves all pairs shortest path (APSP) problem using a dynamic programming approach. Computes matrices A^i for i in set {0, …, |V|} where each entry (i, j) in matrix A^i is the weight of the minimum weigh path from vertex i to vertex j that uses vertices from set {1, …, j} as intermediate steps (A^0 only looks at direct paths between vertices). At each step, compares previous entries to entries that use newly introduced vertex.
O(V^3) running time
O(V^2) space (Matrices)
Graph Transpose
Version of graph with all directed edges reversed.
Ford-Fulkerson Algorithm
Intuition: Solves maximum flow problem by augmenting paths whenever possible. When there are no more possible augmentations, the graph’s flow has been maximized.
Facts:
- Utilizes a “residual” graph that indicates additional possible flow
- If there is a path from source node S to sink node T in residual graph, then the path can be augmented in the original graph
O(MaxFlow * E) running time
O(V) space
Min Cut/Max Flow
The maximum flow in a graph is the determined by the minumum value S-T cut of the graph. A cut is a bipartition of the vertices of the graph such that one part contains S and the other contains T. The flow capacity over a cut is the capacity of all edges that flow from one partition to another.
The min cut can be determined by observing the residual graph after running Ford-Fulkerson and finding the set of vertices reachable from S. The edges from reachable to non reachable vertices are the edges that compose the min cut.
