Mincut Problem An s-t cut is a cut with \(s\) in one set and \(t\) in the other. Call the sets \(A\) and \(B\). Given a digraph, with...
There are many “kinds” of shortest paths. Algorithm Constraint Typical Worst Case Topological Sort No directed cycles \(N+M\) \(N+M\)...
A negative cycle is a directed cycle where the sum of the edge weights is negative. A shortest paths tree exists if and only if there...
Given a digraph, we may wish to find the shortest distance between two nodes, or between a node and all other nodes, etc. Each edge has...
Given a connected graph \(G\), with positive edge weights, the spanning tree is a subgraph \(T\) that is both a tree (connected and...
Applications When looking at code/library dependencies, one may want to see which code pieces form strongly connected components, and...
Topological Sort A topological sort is a traversal of a digraph with ordering constraints. Let each node have some value/weight. It is a...
A cut of a graph is a partitioning of the nodes into two nonempty sets. A minimum cut is a cut that minimizes the number of edges...
NetworkX is a Python library for handling graphs. In [1]: %matplotlib inline In [14]: import networkx as nx import pylab as plt In [3]:...
We wish to find the distance between two nodes \(a\) and \(b\). Let’s generalize this further and find the distance from \(a\) to all...
The depth first search algorithm is a way to traverse all the nodes in a graph. The algorithm is trivial: Start at a given node. Mark it...
An undirected graph is defined by \((V, E)\) where \(V\) is a set of nodes and \(E\) is a set of edges (each edge is an unordered set of...