# 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

```java
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](https://jaywin.gitbook.io/leetcode/topics/graph)
* [207-Course Schedule](https://jaywin.gitbook.io/leetcode/topics/graph)

  ```java
  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](https://github.com/jaywinhuang/leetcode/blob/master/topics/0499-the-maze-iii.md)
* [0505. The Maze II](https://github.com/jaywinhuang/leetcode/blob/master/topics/0505-the-maze-ii.md)
* [0743. Network Delay Time](https://github.com/jaywinhuang/leetcode/blob/master/topics/0743-network-delay-time.md)
* [1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](https://github.com/jaywinhuang/leetcode/blob/master/topics/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md)
* [1514. Path with Maximum Probability](https://github.com/jaywinhuang/leetcode/blob/master/topics/1514-path-with-maximum-probability.md)
* [1631. Path With Minimum Effort](https://github.com/jaywinhuang/leetcode/blob/master/topics/1631-path-with-minimum-effort.md)

### 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](https://github.com/jaywinhuang/leetcode/blob/master/topics/0743-network-delay-time.md)
* [1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](https://github.com/jaywinhuang/leetcode/blob/master/topics/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md)

### 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](https://github.com/jaywinhuang/leetcode/blob/master/topics/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md)