Guidelines

Whenever you have a clear relation between different elements given by the problem statement you should think if you can reframe the initial problem to a graph. Below you find cheatsheet for most common graph algorithms.

Generalized topological sort implementation

Java

private List<Integer> topologicalSort(Map<Integer, List<Integer>> graph, int[] degree, int n) {
    List<Integer> result = new ArrayList<Integer>();
    Queue<Integer> q = new LinkedList();

    for (int key : graph.keySet()) {
        if(degree[key] == 0) {
        q.add(key);
        }
    }

    while(!q.isEmpty()) {
        int node = q.poll();
        result.add(node);
        for (int neighbor : graph.get(node)) {
        if(--degree[neighbor] == 0) {
            q.add(neighbor);
        }
        }
    }
    return result.size() == n ? result : new ArrayList();
}

JavaScript

function topologicalSort(graph, degree, n) {
  const result = [];
  const queue = [];

  for (const key in graph) {
    if (degree[key] === 0) {
      queue.push(key);
    }
  }

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of graph[node]) {
      if (--degree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  return result.length === n ? result : [];
}

Python

def topologicalSort(graph, degree, n):
    result = []
    queue = deque()

    for key in graph.keys():
        if degree[key] == 0:
            queue.append(key)

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            degree[neighbor] -= 1
            if degree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == n else []

C++

vector<int> topologicalSort(map<int, vector<int>>& graph, vector<int>& degree, int n) {
    vector<int> result;
    queue<int> q;

    for (const auto& entry : graph) {
        int key = entry.first;
        if (degree[key] == 0) {
            q.push(key);
        }
    }

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        result.push_back(node);
        for (int neighbor : graph[node]) {
            degree[neighbor]--;
            if (degree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    return result.size() == n ? result : vector<int>();
}

Java

public class MinimumSpanningTree {

    // Prim's Algorithm
    public static List<Edge> primMST(Graph graph) {
        List<Edge> mst = new ArrayList<>();
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        Set<Integer> visited = new HashSet<>();
        visited.add(0);
        pq.addAll(graph.adjList.get(0));

        while (!pq.isEmpty() && visited.size() < graph.vertices) {
            Edge minEdge = pq.poll();
            if (!visited.contains(minEdge.to)) {
                mst.add(minEdge);
                visited.add(minEdge.to);
                pq.addAll(graph.adjList.get(minEdge.to));
            }
        }

        return mst;
    }

    // Kruskal's Algorithm
    public static List<Edge> kruskalMST(Graph graph) {
        List<Edge> mst = new ArrayList<>();
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        UnionFind uf = new UnionFind(graph.vertices);
        pq.addAll(graph.edges);

        while (!pq.isEmpty() && mst.size() < graph.vertices - 1) {
            Edge minEdge = pq.poll();
            if (uf.find(minEdge.from) != uf.find(minEdge.to)) {
                mst.add(minEdge);
                uf.union(minEdge.from, minEdge.to);
            }
        }

        return mst;
    }

    static class UnionFind {
        int[] parent, rank;

        public UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootX] = rootY;
                rank[rootY]++;
            }
        }
    }
}

JavaScript

class MinimumSpanningTree {
  static primMST(graph) {
    const mst = [];
    const pq = new PriorityQueue((a, b) => a.weight - b.weight);
    const visited = new Set();
    visited.add(0);
    pq.enqueueAll(graph.adjList.get(0));

    while (!pq.isEmpty() && visited.size < graph.vertices) {
      const minEdge = pq.dequeue();
      if (!visited.has(minEdge.to)) {
        mst.push(minEdge);
        visited.add(minEdge.to);
        pq.enqueueAll(graph.adjList.get(minEdge.to));
      }
    }

    return mst;
  }

  static kruskalMST(graph) {
    const mst = [];
    const pq = new PriorityQueue((a, b) => a.weight - b.weight);
    const uf = new UnionFind(graph.vertices);
    pq.enqueueAll(graph.edges);

    while (!pq.isEmpty() && mst.length < graph.vertices - 1) {
      const minEdge = pq.dequeue();
      if (uf.find(minEdge.from) !== uf.find(minEdge.to)) {
        mst.push(minEdge);
        uf.union(minEdge.from, minEdge.to);
      }
    }

    return mst;
  }
}

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = Array.from({ length: size }, () => 0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) {
      return;
    }
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootX] = rootY;
      this.rank[rootY]++;
    }
  }
}

Python

class MinimumSpanningTree:
    @staticmethod
    def primMST(graph):
        mst = []
        pq = PriorityQueue()
        visited = set()
        visited.add(0)
        pq.put((0, 0))

        while not pq.empty() and len(visited) < graph.vertices:
            weight, node = pq.get()
            if node not in visited:
                mst.append(graph.adjList[node])
                visited.add(node)
                for edge in graph.adjList[node]:
                    pq.put((edge.weight, edge.to))

        return mst

    @staticmethod
    def kruskalMST(graph):
        mst = []
        pq = PriorityQueue()
        uf = UnionFind(graph.vertices)
        for edge in graph.edges:
            pq.put((edge.weight, edge))

        while not pq.empty() and len(mst) < graph.vertices - 1:
            weight, edge = pq.get()
            if uf.find(edge.from_) != uf.find(edge.to):
                mst.append(edge)
                uf.union(edge.from_, edge.to)

        return mst

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootX] = rootY
            self.rank[rootY] += 1

C++

struct Edge {
    int from, to, weight;
};

class MinimumSpanningTree {
public:
    static vector<Edge> primMST(Graph& graph) {
        vector<Edge> mst;
        priority_queue<Edge, vector<Edge>, function<bool(const Edge&, const Edge&)>> pq([](const Edge& a, const Edge& b) {
            return a.weight > b.weight;
        });
        vector<bool> visited(graph.vertices, false);
        visited[0] = true;
        for (const auto& edge : graph.adjList[0]) {
            pq.push(edge);
        }

        while (!pq.empty() && count(visited.begin(), visited.end(), true) < graph.vertices) {
            Edge minEdge = pq.top();
            pq.pop();
            if (!visited[minEdge.to]) {
                mst.push_back(minEdge);
                visited[minEdge.to] = true;
                for (const auto& edge : graph.adjList[minEdge.to]) {
                    pq.push(edge);
                }
            }
        }

        return mst;
    }

    static vector<Edge> kruskalMST(Graph& graph) {
        vector<Edge> mst;
        priority_queue<Edge, vector<Edge>, function<bool(const Edge&, const Edge&)>> pq([](const Edge& a, const Edge& b) {
            return a.weight > b.weight;
        });
        UnionFind uf(graph.vertices);
        for (const auto& edge : graph.edges) {
            pq.push(edge);
        }

        while (!pq.empty() && mst.size() < graph.vertices - 1) {
            Edge minEdge = pq.top();
            pq.pop();
            if (uf.find(minEdge.from) != uf.find(minEdge.to)) {
                mst.push_back(minEdge);
                uf.unionSet(minEdge.from, minEdge.to);
            }
        }

        return mst;
    }

private:
    class UnionFind {
    public:
        UnionFind(int size) : parent(size), rank(size, 0) {
            for (int i = 0; i < size; ++i) {
                parent[i] = i;
            }
        }

        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void unionSet(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }

    private:
        vector<int> parent;
        vector<int> rank;
    };
};

The minimum spanning tree is the spanning tree with the lowest cost (sum of edge weights).

The time complexity of Prim's Algorithm is O(E log V), where E is the number of edges and V is the number of vertices. The space complexity of Prim's Algorithm is O(V + E), where V is the number of vertices and E is the number of edges. If the graph is fully connected the time complexity can degenerate to O(V^2). The algorithm uses a priority queue to keep track of the minimum edge weights, and the queue is updated each time a new vertex is added to the MST. The size of the priority queue is at most E, and each operation to add or remove an element from the queue takes O(log E) time. (E log E <= E log V as show below).

The time complexity of Kruskal's Algorithm is O(E log V), where E is the number of edges and V is the number of vertices. The space complexity of Kruskal's Algorithm is O(V + E), where V is the number of vertices and E is the number of edges (we keep all edges in priority queue, and also parent array for union for all vertices). Note that you can also make a case that time complexity is O(E log E) but we prefer tight upper bound. We have E <= V^2 (fully connected graph), so ElogE <= ElogV^2 = 2 Elog V = O(E log V).

To choose between Prim's and Kruskal's algorithm, it is important to consider the density of the graph. If the graph is dense, Prim's algorithm is generally preferred, while if the graph is sparse, Kruskal's algorithm is a better choice.

A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color.

Java

boolean isBipartite() {
    boolean[] visited = new boolean[V];
    int[] color = new int[V];

    for (int i = 0; i < V; i++) {
        if (!visited[i] && !dfs(i, visited, color, 1)) {
            return false;
        }
    }
    return true;
}

boolean dfs(int v, boolean[] visited, int[] color, int c) {
    visited[v] = true;
    color[v] = c;
    for (int i = 0; i < adjList[v].size(); i++) {
        int neighbor = adjList[v].get(i);
        if (!visited[neighbor]) {
            if (!dfs(neighbor, visited, color, 3-c)) {
                return false;
            }
        } else if (color[neighbor] == c) {
            return false;
        }
    }
    return true;
}

JavaScript

function isBipartite() {
  const visited = new Array(V).fill(false);
  const color = new Array(V).fill(0);

  for (let i = 0; i < V; i++) {
    if (!visited[i] && !dfs(i, visited, color, 1)) {
      return false;
    }
  }
  return true;
}

function dfs(v, visited, color, c) {
  visited[v] = true;
  color[v] = c;
  for (const neighbor of adjList[v]) {
    if (!visited[neighbor]) {
      if (!dfs(neighbor, visited, color, 3 - c)) {
        return false;
      }
    } else if (color[neighbor] === c) {
      return false;
    }
  }
  return true;
}

Python

def isBipartite():
    visited = [False] * V
    color = [0] * V

    for i in range(V):
        if not visited[i] and not dfs(i, visited, color, 1):
            return False
    return True

def dfs(v, visited, color, c):
    visited[v] = True
    color[v] = c
    for neighbor in adjList[v]:
        if not visited[neighbor]:
            if not dfs(neighbor, visited, color, 3 - c):
                return False
        elif color[neighbor] == c:
            return False
    return True

C++

bool isBipartite() {
    vector<bool> visited(V, false);
    vector<int> color(V, 0);

    for (int i = 0; i < V; i++) {
        if (!visited[i] && !dfs(i, visited, color, 1)) {
            return false;
        }
    }
    return true;
}

bool dfs(int v, vector<bool>& visited, vector<int>& color, int c) {
    visited[v] = true;
    color[v] = c;
    for (int neighbor : adjList[v]) {
        if (!visited[neighbor]) {
            if (!dfs(neighbor, visited, color, 3 - c)) {
                return false;
            }
        } else if (color[neighbor] == c) {
            return false;
        }
    }
    return true;
}

It's graph coloring problem, if we can color the graph with two colors we know it's a bipartite graph. We do a DFS search and each time check if we can color all adjancent vertices with different color (either 1 or 2, we use 3-c).

Java

public static int[] dijkstra(List<List<Edge>> adjList, int start) {
    int n = adjList.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(v -> dist[v]));
    pq.add(start);

    while (!pq.isEmpty()) {
        int u = pq.poll();
        for (Edge e : adjList.get(u)) {
            int v = e.to;
            int weight = e.weight;
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.add(v);
            }
        }
    }

    return dist;
}


public static int[] bellmanFord(List<List<Edge>> adjList, int start, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    for (int i = 0; i < n - 1; i++) {
        for (List<Edge> edges : adjList) {
            for (Edge edge : edges) {
                if (dist[edge.from] != Integer.MAX_VALUE &&
                    dist[edge.from] + edge.weight < dist[edge.to]) {
                    dist[edge.to] = dist[edge.from] + edge.weight;
                }
            }
        }
    }

    // Check for negative cycles
    for (List<Edge> edges : adjList) {
        for (Edge edge : edges) {
            if (dist[edge.from] != Integer.MAX_VALUE &&
                dist[edge.from] + edge.weight < dist[edge.to]) {
                throw new IllegalArgumentException("Graph contains a negative cycle");
            }
        }
    }

    return dist;
}

JavaScript

function dijkstra(adjList, start) {
  const n = adjList.length;
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;

  const pq = new PriorityQueue((a, b) => dist[a] - dist[b]);
  pq.enqueue(start);

  while (!pq.isEmpty()) {
    const u = pq.dequeue();
    for (const e of adjList[u]) {
      const v = e.to;
      const weight = e.weight;
      if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
        pq.enqueue(v);
      }
    }
  }

  return dist;
}

function bellmanFord(adjList, start, n) {
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;

  for (let i = 0; i < n - 1; i++) {
    for (const edges of adjList) {
      for (const edge of edges) {
        if (
          dist[edge.from] !== Infinity &&
          dist[edge.from] + edge.weight < dist[edge.to]
        ) {
          dist[edge.to] = dist[edge.from] + edge.weight;
        }
      }
    }
  }

  // Check for negative cycles
  for (const edges of adjList) {
    for (const edge of edges) {
      if (
        dist[edge.from] !== Infinity &&
        dist[edge.from] + edge.weight < dist[edge.to]
      ) {
        throw new Error("Graph contains a negative cycle");
      }
    }
  }

  return dist;
}

Python

def dijkstra(adjList, start):
    n = len(adjList)
    dist = [float('inf')] * n
    dist[start] = 0

    pq = []
    heapq.heappush(pq, (0, start))

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for e in adjList[u]:
            v = e.to
            weight = e.weight
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))

    return dist

def bellmanFord(adjList, start, n):
    dist = [float('inf')] * n
    dist[start] = 0

    for _ in range(n - 1):
        for edges in adjList:
            for edge in edges:
                if (
                    dist[edge.from] != float('inf') and
                    dist[edge.from] + edge.weight < dist[edge.to]
                ):
                    dist[edge.to] = dist[edge.from] + edge.weight

    # Check for negative cycles
    for edges in adjList:
        for edge in edges:
            if (
                dist[edge.from] != float('inf') and
                dist[edge.from] + edge.weight < dist[edge.to]
            ):
                raise ValueError("Graph contains a negative cycle")

    return dist

C++

vector<int> dijkstra(const vector<vector<Edge>>& adjList, int start) {
    int n = adjList.size();
    vector<int> dist(n, numeric_limits<int>::max());
    dist[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) {
            continue;
        }

        for (const Edge& e : adjList[u]) {
            int v = e.to;
            int weight = e.weight;
            if (dist[u] != numeric_limits<int>::max() && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

vector<int> bellmanFord(const vector<vector<Edge>>& adjList, int start, int n) {
    vector<int> dist(n, numeric_limits<int>::max());
    dist[start] = 0;

    for (int i = 0; i < n - 1; i++) {
        for (const vector<Edge>& edges : adjList) {
            for (const Edge& edge : edges) {
                if (dist[edge.from] != numeric_limits<int>::max() && dist[edge.from] + edge.weight < dist[edge.to]) {
                    dist[edge.to] = dist[edge.from] + edge.weight;
                }
            }
        }
    }

    // Check for negative cycles
    for (const vector<Edge>& edges : adjList) {
        for (const Edge& edge : edges) {
            if (dist[edge.from] != numeric_limits<int>::max() && dist[edge.from] + edge.weight < dist[edge.to]) {
                throw invalid_argument("Graph contains a negative cycle");
            }
        }
    }

    return dist;
}

Bellman-Ford algorithm is a single-source (we have a start) shortest path algorithm, which allows for negative edge weight and can detect negative cycles in a graph. Dijkstra algorithm is also another single-source shortest path algorithm. However, the weight of all the edges must be non-negative. In Bellman-Ford if there is a negative cycle in the graph, then the shortest path between some vertices can have an infinite negative weight. This is because we can keep going around the negative cycle and decreasing the weight of the path. The time complexit of Bellman-Ford is O(VE), while for Dijkstra we have the same time complexity as for Prim algo O(E log V) (you can also present int as O(V + E log E), but in dense graph E dominates the V, E <= V^2).

If we have a DAG (direct acyclig graph) we can get the shortest path using topological order of the vertices.

Java

public static int[] dagShortestPath(Graph graph, int source) {
    List<Integer> sortedVertices = topologicalSort(graph);
    int[] distances = new int[graph.vertices];
    Arrays.fill(distances, Integer.MAX_VALUE);
    distances[source] = 0;
    for (int u : sortedVertices) {
        for (Edge edge : graph.adjList.get(u)) {
            int v = edge.to;
            int weight = edge.weight;
            distances[v] = Math.min(distances[v], distances[u] + weight);
        }
    }
    return distances;
}

JavaScript

function dagShortestPath(graph, source) {
  const sortedVertices = topologicalSort(graph);
  const distances = new Array(graph.vertices).fill(Infinity);
  distances[source] = 0;

  for (const u of sortedVertices) {
    for (const edge of graph.adjList[u]) {
      const v = edge.to;
      const weight = edge.weight;
      distances[v] = Math.min(distances[v], distances[u] + weight);
    }
  }

  return distances;
}

Python

def dagShortestPath(graph, source):
    sortedVertices = topologicalSort(graph)
    distances = [float('inf')] * graph.vertices
    distances[source] = 0

    for u in sortedVertices:
        for edge in graph.adjList[u]:
            v = edge.to
            weight = edge.weight
            distances[v] = min(distances[v], distances[u] + weight)

    return distances

C++

vector<int> dagShortestPath(const Graph& graph, int source) {
    vector<int> sortedVertices = topologicalSort(graph);
    vector<int> distances(graph.vertices, numeric_limits<int>::max());
    distances[source] = 0;

    for (int u : sortedVertices) {
        for (const Edge& edge : graph.adjList[u]) {
            int v = edge.to;
            int weight = edge.weight;
            distances[v] = min(distances[v], distances[u] + weight);
        }
    }

    return distances;
}

And if we want all pairs shortest path we can use Floyd-Warshall algorithm

Java

public static int[][] floydWarshall(int[][] graph) {
    int V = graph.length;
    int[][] dist = new int[V][V];

    // Initialize distance array
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // Calculate shortest path between all pairs of vertices
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE &&
                    dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    return dist;
}

JavaScript

function floydWarshall(graph) {
  const V = graph.length;
  const dist = [...graph];

  // Calculate shortest path between all pairs of vertices
  for (let k = 0; k < V; k++) {
    for (let i = 0; i < V; i++) {
      for (let j = 0; j < V; j++) {
        if (
          dist[i][k] !== Infinity &&
          dist[k][j] !== Infinity &&
          dist[i][j] > dist[i][k] + dist[k][j]
        ) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist;
}

Python

def floydWarshall(graph):
    V = len(graph)
    dist = [row[:] for row in graph]

    # Calculate shortest path between all pairs of vertices
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if (
                    dist[i][k] != float('inf') and
                    dist[k][j] != float('inf') and
                    dist[i][j] > dist[i][k] + dist[k][j]
                ):
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

C++

vector<vector<int>> floydWarshall(const vector<vector<int>>& graph) {
    int V = graph.size();
    vector<vector<int>> dist = graph;

    // Calculate shortest path between all pairs of vertices
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (
                    dist[i][k] != numeric_limits<int>::max() &&
                    dist[k][j] != numeric_limits<int>::max() &&
                    dist[i][j] > dist[i][k] + dist[k][j]
                ) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    return dist;
}

The time complexity is O(V^3). With minor modification we can implement Warshall's algorithm to find the transitive closure of a directed graph. The transitive closure of a graph is a new graph that represents the transitive relationship between the vertices of the original graph. In other words, it tells us if there is a path from one vertex to another in the original graph.

Java

public static int[][] transitiveClosure(int[][] graph) {
    int n = graph.length;
    int[][] closure = new int[n][n];

    // Copy the graph to closure
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            closure[i][j] = graph[i][j];
        }
    }

    // Apply Warshall's algorithm
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                closure[i][j] = closure[i][j] | (closure[i][k] & closure[k][j]);
            }
        }
    }

    return closure;
}

JavaScript

function transitiveClosure(graph) {
  const n = graph.length;
  const closure = Array.from({ length: n }, () => Array(n));

  // Copy the graph to closure
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      closure[i][j] = graph[i][j];
    }
  }

  // Apply Warshall's algorithm
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        closure[i][j] = closure[i][j] | (closure[i][k] & closure[k][j]);
      }
    }
  }

  return closure;
}

Python

def transitiveClosure(graph):
    n = len(graph)
    closure = [row[:] for row in graph]

    # Apply Warshall's algorithm
    for k in range(n):
        for i in range(n):
            for j in range(n):
                closure[i][j] = closure[i][j] | (closure[i][k] & closure[k][j])

    return closure

C++

vector<vector<int>> transitiveClosure(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> closure = graph;

    // Apply Warshall's algorithm
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                closure[i][j] = closure[i][j] | (closure[i][k] & closure[k][j]);
            }
        }
    }

    return closure;
}

Fold-Fulkerson can find a maximum matching in a bipartite graph by reducing the problem of maximum bipartite matching to network flow.

Java

private static int fordFulkerson(int source, int sink) {
    int maxFlow = 0;
    while (bfs(source, sink)) {
        int pathFlow = Integer.MAX_VALUE;
        int u = sink;
        while (u != source) {
            int v = parent[u];
            pathFlow = Math.min(pathFlow, graph[v][u]);
            u = v;
        }
        u = sink;
        while (u != source) {
            int v = parent[u];
            graph[v][u] -= pathFlow;
            graph[u][v] += pathFlow;
            u = v;
        }
        maxFlow += pathFlow;
    }
    return maxFlow;
}
private static boolean bfs(int source, int sink) {
    Arrays.fill(visited, false);
    Queue<Integer> queue = new LinkedList<>();
    queue.add(source);
    visited[source] = true;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v = 0; v < graph.length; v++) {
            if (!visited[v] && graph[u][v] > 0) {
                visited[v] = true;
                parent[v] = u;
                queue.add(v);
            }
        }
    }
    return visited[sink];
}

JavaScript

function fordFulkerson(source, sink) {
  let maxFlow = 0;
  while (bfs(source, sink)) {
    let pathFlow = Infinity;
    let u = sink;
    while (u !== source) {
      let v = parent[u];
      pathFlow = Math.min(pathFlow, graph[v][u]);
      u = v;
    }
    u = sink;
    while (u !== source) {
      let v = parent[u];
      graph[v][u] -= pathFlow;
      graph[u][v] += pathFlow;
      u = v;
    }
    maxFlow += pathFlow;
  }
  return maxFlow;
}

function bfs(source, sink) {
  const visited = new Array(graph.length).fill(false);
  const queue = [];
  queue.push(source);
  visited[source] = true;
  while (queue.length > 0) {
    const u = queue.shift();
    for (let v = 0; v < graph.length; v++) {
      if (!visited[v] && graph[u][v] > 0) {
        visited[v] = true;
        parent[v] = u;
        queue.push(v);
      }
    }
  }
  return visited[sink];
}

Python

def fordFulkerson(source, sink):
    maxFlow = 0
    while bfs(source, sink):
        pathFlow = float('inf')
        u = sink
        while u != source:
            v = parent[u]
            pathFlow = min(pathFlow, graph[v][u])
            u = v
        u = sink
        while u != source:
            v = parent[u]
            graph[v][u] -= pathFlow
            graph[u][v] += pathFlow
            u = v
        maxFlow += pathFlow
    return maxFlow

def bfs(source, sink):
    visited = [False] * len(graph)
    queue = []
    queue.append(source)
    visited[source] = True
    while queue:
        u = queue.pop(0)
        for v in range(len(graph)):
            if not visited[v] and graph[u][v] > 0:
                visited[v] = True
                parent[v] = u
                queue.append(v)
    return visited[sink]

C++

vector<vector<int>> graph;
vector<int> parent;
vector<bool> visited;

int fordFulkerson(int source, int sink) {
    int maxFlow = 0;
    while (bfs(source, sink)) {
        int pathFlow = INT_MAX;
        int u = sink;
        while (u != source) {
            int v = parent[u];
            pathFlow = min(pathFlow, graph[v][u]);
            u = v;
        }
        u = sink;
        while (u != source) {
            int v = parent[u];
            graph[v][u] -= pathFlow;
            graph[u][v] += pathFlow;
            u = v;
        }
        maxFlow += pathFlow;
    }
    return maxFlow;
}

bool bfs(int source, int sink) {
    fill(visited.begin(), visited.end(), false);
    queue<int> q;
    q.push(source);
    visited[source] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 0; v < graph.size(); v++) {
            if (!visited[v] && graph[u][v] > 0) {
                visited[v] = true;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    return visited[sink];
}

We use BFS (the number of edges on the path) to check for path between source and sink. The time complexity is O(V * E^2) (there are at most EV augmenting paths and to find each of those we spend O(E) time, actually O(E+V), but V get dominated by E since we're generally talking about connected graphs). The maximum matching problem asks to find a maximum-size set of node pairs in an undirected graph such that each pair is connected with an edge and each node belongs to at most one pair. We can reduce the bipartite maximum matching problem to the maximum flow problem by adding two new nodes to the graph: a source and a sink. We also add edges from the source to each left node and from each right node to the sink. After this, the size of a maximum flow in the graph equals the size of a maximum matching in the original graph. Note that all edges now will have a weight of 1.

Finding a maximum flow: What is the maximum amount of flow we can send from a node to another node? Finding a minimum cut: What is a minimum-weight set of edges that separates two nodes of the graph? It turns out that a maximum flow and a minimum cut are always equally large, so the concepts are two sides of the same coin.

Kosaraju’s algorithm is an efficient method for finding the strongly connected components of a directed graph. The algorithm performs two depth-first searches: the first search constructs a list of nodes according to the structure of the graph, and the second search forms the strongly connected components. The time complexity is that of DFS. This works because even when reversing the graph edges the strongly connectect component will remain connected, only the links between different component will be affected.

Java

public static List<List<Integer>> stronglyConnectedComponents(List<List<Integer>> graph) {
    int n = graph.size();

    // step 1: compute the reverse graph
    List<List<Integer>> reverseGraph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        reverseGraph.add(new ArrayList<>());
    }
    for (int u = 0; u < n; u++) {
        for (int v : graph.get(u)) {
            reverseGraph.get(v).add(u);
        }
    }

    // step 2: run depth-first search on the reverse graph
    Stack<Integer> stack = new Stack<>();
    boolean[] visited = new boolean[n];
    for (int u = 0; u < n; u++) {
        if (!visited[u]) {
            dfs(reverseGraph, u, visited, stack);
        }
    }

    // step 3: run depth-first search on the original graph in reverse order of finishing times
    List<List<Integer>> components = new ArrayList<>();
    visited = new boolean[n];
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (!visited[u]) {
            List<Integer> component = new ArrayList<>();
            dfs(graph, u, visited, component);
            components.add(component);
        }
    }

    return components;
}

// helper method for depth-first search
public static void dfs(List<List<Integer>> graph, int u, boolean[] visited, List<Integer> path) {
    visited[u] = true;
    for (int v : graph.get(u)) {
        if (!visited[v]) {
            dfs(graph, v, visited, path);
        }
    }
    path.add(u);
}

JavaScript

function stronglyConnectedComponents(graph) {
  const n = graph.length;

  // Step 1: Compute the reverse graph
  const reverseGraph = new Array(n).fill().map(() => []);
  for (let u = 0; u < n; u++) {
    for (let v of graph[u]) {
      reverseGraph[v].push(u);
    }
  }

  // Step 2: Run depth-first search on the reverse graph
  const stack = [];
  const visited = new Array(n).fill(false);
  for (let u = 0; u < n; u++) {
    if (!visited[u]) {
      dfs(reverseGraph, u, visited, stack);
    }
  }

  // Step 3: Run depth-first search on the original graph in reverse order of finishing times
  const components = [];
  visited.fill(false);
  while (stack.length > 0) {
    const u = stack.pop();
    if (!visited[u]) {
      const component = [];
      dfs(graph, u, visited, component);
      components.push(component);
    }
  }

  return components;
}

// Helper method for depth-first search
function dfs(graph, u, visited, path) {
  visited[u] = true;
  for (let v of graph[u]) {
    if (!visited[v]) {
      dfs(graph, v, visited, path);
    }
  }
  path.push(u);
}

Python

def stronglyConnectedComponents(graph):
    n = len(graph)

    # Step 1: Compute the reverse graph
    reverseGraph = [[] for _ in range(n)]
    for u in range(n):
        for v in graph[u]:
            reverseGraph[v].append(u)

    # Step 2: Run depth-first search on the reverse graph
    stack = []
    visited = [False] * n
    for u in range(n):
        if not visited[u]:
            dfs(reverseGraph, u, visited, stack)

    # Step 3: Run depth-first search on the original graph in reverse order of finishing times
    components = []
    visited = [False] * n
    while stack:
        u = stack.pop()
        if not visited[u]:
            component = []
            dfs(graph, u, visited, component)
            components.append(component)

    return components

# Helper method for depth-first search
def dfs(graph, u, visited, path):
    visited[u] = True
    for v in graph[u]:
        if not visited[v]:
            dfs(graph, v, visited, path)
    path.append(u)

C++

vector<vector<int>> stronglyConnectedComponents(vector<vector<int>>& graph) {
    int n = graph.size();

    // Step 1: Compute the reverse graph
    vector<vector<int>> reverseGraph(n);
    for (int u = 0; u < n; u++) {
        for (int v : graph[u]) {
            reverseGraph[v].push_back(u);
        }
    }

    // Step 2: Run depth-first search on the reverse graph
    stack<int> st;
    vector<bool> visited(n, false);
    for (int u = 0; u < n; u++) {
        if (!visited[u]) {
            dfs(reverseGraph, u, visited, st);
        }
    }

    // Step 3: Run depth-first search on the original graph in reverse order of finishing times
    vector<vector<int>> components;
    visited.assign(n, false);
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        if (!visited[u]) {
            vector<int> component;
            dfs(graph, u, visited, component);
            components.push_back(component);
        }
    }

    return components;
}

// Helper method for depth-first search
void dfs(vector<vector<int>>& graph, int u, vector<bool>& visited, stack<int>& st) {
    visited[u] = true;
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(graph, v, visited, st);
        }
    }
    st.push(u);
}

An Eulerian path is a path that goes exactly once through each edge of the graph. An Eulerian circuit is an Eulerian path that starts and ends at the same node. Hierholzer’s algorithm is an efficient method for constructing an Eulerian circuit.

Java

public static List<Integer> eulerianCycle(List<List<Integer>> graph) {
    int n = graph.size();

    // initialize the degree array and the stack
    int[] degree = new int[n];
    for (int u = 0; u < n; u++) {
        for (int v : graph.get(u)) {
            degree[u]++;
        }
    }
    Stack<Integer> stack = new Stack<>();
    stack.push(0);

    // find the cycle using depth-first search
    List<Integer> cycle = new ArrayList<>();
    while (!stack.isEmpty()) {
        int u = stack.peek();
        if (degree[u] == 0) {
            cycle.add(u);
            stack.pop();
        } else {
            int v = graph.get(u).get(degree[u] - 1);
            degree[u]--;
            stack.push(v);
            graph.get(v).remove(Integer.valueOf(u));
        }
    }

    // reverse the cycle to get the correct order
    Collections.reverse(cycle);
    return cycle;
}

JavaScript

function eulerianCycle(graph) {
  const n = graph.length;

  // Initialize the degree array and the stack
  const degree = new Array(n).fill(0);
  for (let u = 0; u < n; u++) {
    for (let v of graph[u]) {
      degree[u]++;
    }
  }
  const stack = [0];

  // Find the cycle using depth-first search
  const cycle = [];
  while (stack.length > 0) {
    const u = stack[stack.length - 1];
    if (degree[u] === 0) {
      cycle.push(u);
      stack.pop();
    } else {
      const v = graph[u][degree[u] - 1];
      degree[u]--;
      stack.push(v);
      graph[v].splice(graph[v].indexOf(u), 1);
    }
  }

  // Reverse the cycle to get the correct order
  cycle.reverse();
  return cycle;
}

Python

def eulerianCycle(graph):
    n = len(graph)

    # Initialize the degree array and the stack
    degree = [0] * n
    for u in range(n):
        degree[u] = len(graph[u])
    stack = [0]

    # Find the cycle using depth-first search
    cycle = []
    while stack:
        u = stack[-1]
        if degree[u] == 0:
            cycle.append(u)
            stack.pop()
        else:
            v = graph[u][degree[u] - 1]
            degree[u] -= 1
            stack.append(v)
            graph[v].remove(u)

    # Reverse the cycle to get the correct order
    cycle.reverse()
    return cycle

C++

vector<int> eulerianCycle(vector<vector<int>>& graph) {
    int n = graph.size();

    // Initialize the degree array and the stack
    vector<int> degree(n, 0);
    for (int u = 0; u < n; u++) {
        degree[u] = graph[u].size();
    }
    stack<int> st;
    st.push(0);

    // Find the cycle using depth-first search
    vector<int> cycle;
    while (!st.empty()) {
        int u = st.top();
        if (degree[u] == 0) {
            cycle.push_back(u);
            st.pop();
        } else {
            int v = graph[u][degree[u] - 1];
            degree[u]--;
            st.push(v);
            graph[v].erase(find(graph[v].begin(), graph[v].end(), u));
        }
    }

    // Reverse the cycle to get the correct order
    reverse(cycle.begin(), cycle.end());
    return cycle;
}