Graph

Graph types

• Undirected

• Directed

  • Cycle detection

• Weighted

  • Shortest path -> Dijkstras algorithm

Implementation

• Adjacent list List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);

• Usually, the implementation fuse into Solution, no need to new a Graph Class.

• detect loop

class Graph {
    private final int V;
    private int E;
    List<List<Integer>> adjList;
    public Graph(int v) {
        this.V = v; this.E = 0;
        adjList = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<Integer>());
        }
    }
    public void addEdge(int v, int w) {
        adjList.get(v).add(w);
        adjList.get(w).add(v);
        E++;
    }
    public List<Integer> adj(int v) {
        return adjList.get(v);
    }
}

Topological sorting

• Most classic: dependency issue, like course schedule

• Iterate every node in a Graph, where nodes order decided by in/out degree. 310-Minimum Height Trees

• 207-Course Schedule

  class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) return false;
  
        // have a graph. (Maybe map is more compatible than adjacent list, eliminate duplicate element)
        List<List<Integer>> adjList = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<Integer>());
        }
  
        // get indegree
        int[] indegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            indegree[pre[0]]++;
            adjList.get(pre[1]).add(pre[0]);
        }
  
        // BFS
        Queue<Integer> q = new LinkedList<Integer>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) q.offer(i);
        }
        while (!q.isEmpty()) {
            int head = q.poll();
            for (int next : adjList.get(head)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.offer(next);
                }
            }
        }
  
        // Determine
        for (int inde : indegree) {
            if (inde != 0) return false;
        }
  
        return true;
    }
  }

DFS

https://leetcode.com/problems/number-of-islands/description/

BFS

https://leetcode.com/problems/number-of-islands/description/

Cycle detection

1) graph, DFS/BFS 2) topological sort 3) Floyd cycle 4) Union Find

Shortest Path problem

Simple BFS

Not weighted graph

Dijkstra's Algorithm

• Use case: find shortest path from A to B, in a weighted graph

• Time complexity: O(ElogV)

  • E is at most V^2

• Cannot handle negative weight

• Similar to BFS, but use PriorityQueue to track the least-weights-path

• 0499. The Maze III

• 0505. The Maze II

• 0743. Network Delay Time

• 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

• 1514. Path with Maximum Probability

• 1631. Path With Minimum Effort

Bellman–Ford Algorithm

• Use case: find shortest path from A to any other nodes, in a weighted graph

• Step: 1) iterate each V; 2) iterate each edge try to relax u-v

• Time complexity: O(EV)

• Can handle negative weight

• Proof: https://cp-algorithms.com/graph/bellman_ford.html

• 0743. Network Delay Time

• 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

Shortest Path Faster Algorithm (SPFA) - improvement of the Bellman-Ford

• O(EV) worst case, in practice it's faster though.

• Different from Bellman-Ford: only track those nodes with updated distance, whereas BF track every node.

• Can handle negative weight: one node cann't be enqueued more than V times;

Floyd–Warshall algorithm

• Find shortest distances between every pair of vertices

• Step: 1) iterate each V; 2) assume k is the mid point from i to j, relax dist[i][j];

• O(V^3) time

• 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance