# 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](graph)
*   [207-Course Schedule](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/](https://leetcode.com/problems/number-of-islands/description/)

## BFS

[https://leetcode.com/problems/number-of-islands/description/](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)
