DFS (Depth-First Search)

DFS is an algorithm for traversing or searching tree or graph data structures. It

starts at the root or an arbitrary node of a graph and explores as far as possible
along each branch before backtracking.
Input:
 G = (V, E)
Output:
 ccnum[]
 a topological sort on a DAG (Directed Acyclic Graph).
o it takes O(1) to access the first or last vertex of the topological sorting.

More specifically, it outputs:

 Undirected graph G, where the vertices are labeled by connected component
number (ccnum).
 Directed graph G, a list of connected components.
We have access to the prev, pre, and post-arrays.
Graphs that can use DFS:
 Unweighted graphs
 Undirected/Directed graphs
 DAGs
Runtime:
 O(m + n)
BFS (Breadth-First Search)
BFS is an algorithm for traversing or searching tree or graph data structures. It
starts at the tree root (or some arbitrary node of a graph) and explores the neighbor
nodes at the present depth before moving on to nodes at the next depth level.
Input:
 G = (V, E)
 Start vertex v in V
Output:
 dist[]
o For all vertices u reachable from the starting vertex v, dist[u] is the
shortest path distance from v to u. If no such path exists, infinity
otherwise.
 prev[]
o Vertex preceding u in the shortest path from v to reachable vertex u.

Graphs that can use BFS:

 Unweighted graphs
 Undirected/Directed graphs
Runtime:
 O(m + n)
Dijkstra's Algorithm
Dijkstra's algorithm is used to find the shortest distance from a source vertex to all
other vertices. A path can be recovered by backtracking over all of the pre-labels.
Dijkstra's in 3 minutes
Input:
 G = (V, E)
 Start vertex v in V
Output:
 dist[]
o Shortest distance between vertex v and reachable vertex u or infinity
otherwise if not reachable.
We have access to:
 prev[]
o Vertex preceding u in the shortest path from v to reachable vertex u

Graphs that can use Dijkstra's:

 Weighted graphs
 Undirected/Directed graphs
 NO negative weights
Runtime:
 O((m + n) log n)
 O(m log n) if the graph is strongly connected
BF (Bellman-Ford)
Bellman-Ford is used to derive the shortest path from s to all vertices in V. It does
not find a path between all pairs of vertices in V. To do this, we would have to run BF
|V| times. Negative weights are allowed.
Bellman-Ford: Theory in 4 minutes
Bellman-Ford: Example in 5 minutes
Input:
 G = (V, E)
 Start vertex s
Output:
 The shortest path from vertex s to all other vertices.
We have access to:
 Detect negative weight cycles. We can compare T[n, *] to T[n - 1, *].
o We can only find negative weight cycles that can be reached from
starting vertex s.
Graphs that can use BF:
 Weighted graphs
 Undirected/Directed graphs
 CAN HAVE negative weights
Runtime:
 O(mn)
FW (Floyd-Warshall)
FW is primarily used to find the shortest path from ALL nodes to all other nodes
where negative weights are allowed.
Floyd-Warshall in 4 minutes
Input:
 G = (V, E)
Output:
 The shortest path from all vertices to all other vertices
We have access to:
 We can detect negative weight cycles by checking the diagonals (T[n, i, i]).
Graphs that can use FW:
 Weighted graphs
 Undirected/Directed graphs
 CAN HAVE negative weights
Runtime:
 O(n^3)
SCC (Strongly Connected Components)
The SCC algorithm is used to determine the strongly connected components as well
as the meta-graph of connected components in a given directed graph.
Input:
 G = (V, E)
Output:
 meta-graph (DAG) that contains the connected components
 Reverse Topological sorting of the meta-graph
We have access to:
 ccnum[] - strongly connected components produced from the 2nd DFS run
Graphs that can use SCC:
 directed graphs
Runtime:
 O(m + n)
Kruskal’s Algorithm
Kruskal's is one of the two algorithms used to find the Minimum Spanning Tree
(MST) discussed in class.
Kruskal's Algorithm in 2 minutes
Input:
 Connected, Undirected Graph G = (V, E) with edge weights w_e
Output:
 An MST defined by the edges E
Graphs that can use Kruskal's:
 Connected
 Undirected
 Weighted
Runtime:
 O(m log n)

Prim’s Algorithm
Prim's algorithm is the second and final algorithm used to find the MSTs as
discussed in class.
Prim's Algorithm in 2 minutes
Input:
 Connected, Undirected Graph G = (V, E) with edge weights w_e
Output:
 An MST defined by the prev[] array
Graphs that can use Prim's:
 Connected
 Undirected
 Weighted
Runtime:
 O(m log n) if graph is connected
 O((m + n) log n) if graph is not connected
2SAT
The 2-SAT problem is to determine whether there exists an assignment to variables
of a given Boolean formula in 2-CNF (conjunctive normal form) such that the
formula evaluates to true. The algorithm for solving 2-SAT uses graph theory by
constructing an implication graph and then checking for the existence of a path that
satisfies the conditions.
Input:
 A Boolean formula in 2-CNF is represented as a set of clauses where each
clause is a disjunction of exactly two literals.
Output:
 A Boolean value indicates whether the given 2-CNF formula is satisfiable. If it
is satisfiable, the algorithm may also provide a satisfying assignment of
variables.
Graphs that can use 2-SAT:
 Directed graphs
o The implication graph is inherently directed since each implication (¬x
→ y) has a direction.
Runtime:
 O(m + n) - m is the number of clauses in the 2-CNF formula, n is the number
of literal or variables.
o This runtime stems from the linear runtime of SCC finding algorithms
and the construction of the implication graph.
FF (Ford-Fulkerson)
A greedy algorithm to find max flow on networks. The algorithm continually sends
flow along paths from the source (starting node) to the sink (end node), provided
there is available capacity on all edges involved. This flow continues until no further
augmenting paths with available capacity are detected.
Ford-Fulkerson in 5 minutes
Ford-Fulkerson Algorithm Web Animation
Input:
 G = (V, E)
 Flow capacity c
 Source node s
 Sink node t
Output:
 Max flow
We have access to:
 Can trivially create the final residual network with G
 Max flow of G
Example use:
We run FF on the flow network to get the maximum flow.
We use this to construct the residual graph.
Graphs that can use FF:
 Directed graphs with capacity of edges
Runtime:
 O(C * m)
o C is the maximum flow in the network

o m is the number of edges

EK (Edmonds-Karp)
The Edmonds-Karp (EK) algorithm is utilized to determine the maximum flow in a
network. This is analogous to the Ford-Fulkerson method but with one distinct
difference: the order of search for finding an augmenting path must involve the
shortest path with available capacity (BFS for G where all edge weights equal 1).
Input:
 G = (V, E)
 Flow capacity c
 Source node s
 Sink node t
Output:
 Max flow
We have access to:
 Can trivially create the final residual network with G
 Max flow of G
Example use:
We run EK on the flow network to get the maximum flow.
We use this to construct the residual graph.
Graphs that can use EK:
 Directed graphs with capacity of edges
Runtime:
 O(nm^2)
o n is the number of vertices

o m^2 is the number of edges

What are the differences between FF and EK?
Edmonds-Karp uses BFS. Ford-Fulkerson does not specify the search algorithm (BFS
or DFS) it uses to find the augmenting paths in a flow network. The choice of BFS or
DFS can influence the performance and characteristics of the resulting maximum
flow algorithm.
Edmonds-Karp only needs positive capacities whereas Ford-Fulkerson requires
positive integer capacities.
Edmonds-Karp is an algorithm that was introduced after Ford-Fulkerson to address
some of the issues with Ford-Fulkerson. It is a specific implementation of Ford-
Fulkerson.

So why use Edmonds-Karp over Ford-Fulkerson?

This is assuming Ford-Fulkerson uses DFS.
Choice of Augmenting Path
Edmonds-Karp uses BFS in the residual graph to find an augmenting path. This
guarantees that the path found is always the shortest (in terms of the number of
edges). This is crucial because, in Ford-Fulkerson, the use of DFS can lead to long
unyieldly path traversals in dense graphs (graphs where the number of edges is
close to the maximum possible number of edges), where DFS can get "stuck"
exploring a deep path that becomes very inefficient. By using BFS, the Edmonds-
Karp algorithm ensures that it always finds the most efficient augmenting path first,
minimizing the path length, and thereby significantly improving the efficiency of the
algorithm in comparison to Ford-Fulkerson.
Termination
Unlike the Ford-Fulkerson method, the Edmonds-Karp algorithm always terminates,
even for irrational capacities. When the capacities are irrational numbers, the
augmenting fails in Ford-Fulkerson because it is possible for the Ford-Fulkerson
algorithm to keep increasing the flow by diminishing amounts without ever
concluding, essentially getting stuck in an infinite loop. This is because the
algorithm could keep choosing augmenting paths that contribute an ever-
decreasing amount of flow. The Edmonds-Karp algorithm resolves this issue by
always choosing the shortest augmenting path (in terms of the number of edges)
for flow augmentation. This method ensures that the number of augmentations is
bounded by the number of edges times the number of vertices, resulting in
guaranteed termination, even in cases where the edge capacities are irrational. The
explicit use of BFS for the selection of augmenting paths prevents the possibility of
an infinite loop occurring due to constantly decreasing flow augmentation.
Therefore, unlike the Ford-Fulkerson algorithm, Edmonds-Karp always terminates.
Running Time
Edmonds-Karp algorithm, with its worst-case runtime of O(nm^2), offers an
improvement over Ford-Fulkerson because its time complexity is dependent on the
number of vertices (n) and edges (m), rather than the maximum flow in the graph
(C). This guarantees that the algorithm is polynomial concerning the input, ensuring
better efficiency, especially for graphs with high capacities. Ford-Fulkerson, on the
other hand, has a worst-case run time of O(mC), where m denotes the number of
edges and C represents the maximum flow in the network. This complexity arises if
the algorithm is unfortunate enough to always pick the path with the smallest
possible flow. Consequently, this leads to a maximum of mC iterations, resulting in a
potentially highly inefficient algorithm, especially in scenarios with large graphs and
high capacities.

Creating Residual Networks

We can create the Residual Network trivially after running Edmonds-Karp or Ford-
Fulkerson first.
Algorithm
Create Residual Network; obtain G_f, c_f.
Correctness
The residual network is created after the max flow is found either because it was
given in the problem statement or we previously ran EK or FF on the flow network to
obtain it. It correctly returns a new flow network G_f and capacities c_f.
Runtime
Creating the Residual Network takes O(m + n) time.

How are Prim's and Dijkstra's runtimes related?

The runtimes of both Dijkstra's and Prim's algorithms depend on the
implementation of the priority queue, along with the number of edges (m) and the
number of vertices (n) in the graph. When we use a binary heap as the priority
queue, both Dijkstra's and Prim's algorithms have a time complexity of O((m + n)
log n).
The analysis is based on three main operations as discussed in DPV figure 5.9:
• makequeue(V) initiates n insertions to the priority queue where each insertion
costs O(log n).
• decreasekey(H,z) runs m times, each call costing O(log n).
• deletemin() executes n times, with each execution costing O(log n).
Therefore, the operations collectively result in a time complexity of O((m + n) log n)
for both algorithms. However, when we're dealing with connected graphs, Prim's
algorithm can be simplified to O(m log n) because the number of edges m in a
connected graph is at least n - 1, meaning m closely approximates to n. Hence, the
term (m + n) becomes nearly equivalent to 2m, resulting in a time complexity of
O(m log n).