1,存圖方式

1.1 鄰接矩陣

這是一種使用二維矩陣來進行存圖的方法。

適用于邊數(shù)較多的稠密圖使用，當邊數(shù)量接近點的數(shù)量的平方，即 m≈n2 時，可定義為稠密圖。

//定義無窮大為INF，若使用Interger.MAX_VALUE即0x7fffffff,在松弛操作時會溢出為較小的負數(shù)
int INF = 0x3f3f3f3f;

// 鄰接矩陣數(shù)組：w[a][b] = c 代表從 a 到 b 有權(quán)重為 c 的邊
int[][] w = new int[N][N];

// 加邊操作
void add(int a, int b, int c) {
    w[a][b] = c;
}

// 初始化鄰接矩陣數(shù)組
void init(){
  for (int i=1;i<=n;i++){
    for (int j=1;j<=n;j++){
      w[i][j] = w[j][i] = i == j ? 0 : INF;
    }
  }
}

1.2 鄰接表（鏈式前向星）

這也是一種在圖論中十分常見的存圖方式，與數(shù)組存儲單鏈表的實現(xiàn)一致（頭插法）。

這種存圖方式又叫鏈式前向星存圖。

適用于邊數(shù)較少的稀疏圖使用，當邊數(shù)量接近點的數(shù)量，即 m≈n 時，可定義為稀疏圖。

int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
int idx;
int[] d = new int[N];//存儲節(jié)點的深度
int[] indeg = new int[N];//存儲節(jié)點的入度
boolean[] vis = new boolean[N];

void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = he[a];
    he[a] = idx;
    w[idx] = c;
    idx++;
  
    indeg[b]++;
}

{
  // 初始化鏈表頭
  Arrays.fill(he, -1);
}

void dfs(int u){
        vis[u] = true;
        for (int i=he[u];i!=-1;i=ne[i]){
            int v = e[i];
            if (!vis[v]){
                dfs(v);
            }
        }
    }

void bfs(int u){
  Queue<Integer> queue = new ArrayDeque<>();
  queue.offer(u);
  d[u]=1;
  vis[u] = true;
  while (!queue.isEmpty()){
    int x = queue.poll();
    for (int i=he[x];i!=-1;i=ne[i]){
      int y = e[i];
      if (vis[y])
        continue;
      queue.offer(y);
      d[y] = d[x] + 1;
    }
  }
}

void topsort(){
  Queue<Integer> queue = new ArrayDeque<>();
  for (int i=0;i<N;i++){
    if (indeg[i]==0){
      queue.offer(i);
    }
  }
  while (!queue.isEmpty()){
    int x = queue.poll();
    System.out.println(x);
    for (int i=he[x];i!=-1;i++){
      int y = e[i];
      indeg[y]--;
      if (indeg[y]==0){
        queue.offer(y);
      }
    }
  }
}

首先 idx 是用來對邊進行編號的，然后對存圖用到的幾個數(shù)組作簡單解釋：

• he 數(shù)組：he[i],表示以i為起點的第一條邊在邊集數(shù)組的位置（編號）(head)
• e 數(shù)組：用于訪問某一條邊指向的節(jié)點；(end)
• ne 數(shù)組：該數(shù)組就是用于找到下一條邊；(nextEdge)
• w 數(shù)組：用于記錄某條邊的權(quán)重為多少。(weight)

因此當我們想要遍歷所有由 a 點發(fā)出的邊時，可以使用如下方式：

for (int i = he[a]; i != -1; i = ne[i]) {
    int b = e[i], c = w[i]; // 存在由 a 指向 b 的邊，權(quán)重為 c
}

2，F(xiàn)loyd算法+鄰接矩陣

Floyd算法的基本思想如下：從任意節(jié)點A到任意節(jié)點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過若干個節(jié)點到B，所以，我們假設(shè)dist(AB)為節(jié)點A到節(jié)點B的最短路徑的距離，對于每一個節(jié)點K，我們檢查dist(AK) + dist(KB) < dist(AB)是否成立，如果成立，證明從A到K再到B的路徑比A直接到B的路徑短，我們便設(shè)置 dist(AB) = dist(AK) + dist(KB)，這樣一來，當我們遍歷完所有節(jié)點K，dist(AB)中記錄的便是A到B的最短路徑的距離。

void floyd() {
    // floyd 基本流程為三層循環(huán)：
    // 枚舉中轉(zhuǎn)點 - 枚舉起點 - 枚舉終點 - 松弛操作，必須首先枚舉中轉(zhuǎn)點       
    for (int p = 1; p <= n; p++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          w[i][j] = Math.min(w[i][j], w[i][p] + w[p][j]);
        }
      }
    }
 }

• 時間復(fù)雜度：O(n3)
• 空間復(fù)雜度：O(n2)

3，Dijkstra算法+鄰接矩陣

同理，我們可以使用復(fù)雜度為 O(n^2)O(n2) 的「單源最短路」算法樸素 Dijkstra 算法進行求解，同時使用「鄰接矩陣」來進行存圖。Dijkstra算法不能處理負權(quán)邊。

迪杰斯特拉(Dijkstra)算法按路徑長度遞增次序產(chǎn)生最短路徑。先把V分成兩組：

• S：已求出最短路徑的頂點的集合

• V-S=T：尚未確定最短路徑的頂點集合

  將T中頂點按最短路徑遞增的次序加入到S中，依據(jù)：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的直接路徑的權(quán)值或是從V0經(jīng)S中頂點到Vk的路徑權(quán)值之和（反證法可證）。

        // 頂點數(shù)N，變數(shù)M
    int N = 110,M = 6010;
        // 鄰接矩陣數(shù)組：w[a][b] = c 代表從 a 到 b 有權(quán)重為 c 的邊
    int[][] w = new int[N][N];
    // dist[x] = y 代表從「源點/起點」到 x 的最短距離為 y
    int[] dist = new int[N];
    // 記錄哪些點已經(jīng)被更新過
    boolean[] vis = new boolean[N];
    int INF = 0x3f3f3f3f;

        void dijkstra() {
        // 起始先將所有的點標記為「未更新」和「距離為正無窮」
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        // 只有起點最短距離為 0
        dist[k] = 0;
        // 迭代 n 次
        for (int p = 1; p <= n; p++) {
            // 每次找到「最短距離最小」且「未被更新」的點 t
            int t = -1;
            for (int i = 1; i <= n; i++) {
                if (!vis[i] && (t == -1 || dist[i] < dist[t])) t = i;
            }
            // 標記點 t 為已更新
            vis[t] = true;
            // 用點 t 的「最小距離」更新其他點
            for (int i = 1; i <= n; i++) {
                dist[i] = Math.min(dist[i], dist[t] + w[t][i]);
            }
        }
    }

• 時間復(fù)雜度：O(n2)
• 空間復(fù)雜度：O(n2)

4，Dijkstra+鄰接表

        // 頂點數(shù)N，變數(shù)M
    int N = 110,M = 6010;
        // 鄰接表
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
        int idx;
    // dist[x] = y 代表從「源點/起點」到 x 的最短距離為 y
    int[] dist = new int[N];
    // 記錄哪些點已經(jīng)被更新過
    boolean[] vis = new boolean[N];
    int INF = 0x3f3f3f3f;

        void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        w[idx] = c;
        idx++;
    }
        {
        // 初始化鏈表頭
        Arrays.fill(he, -1);
    }

        void dijkstra() {
        // 起始先將所有的點標記為「未更新」和「距離為正無窮」
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        // 只有起點最短距離為 0
        dist[k] = 0;
        // 使用「優(yōu)先隊列」存儲所有可用于更新的點
        // 以 (點編號, 到起點的距離) 進行存儲，優(yōu)先彈出「最短距離」較小的點
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1]-b[1]);
        q.add(new int[]{k, 0});
        while (!q.isEmpty()) {
            // 每次從「優(yōu)先隊列」中彈出
            int[] poll = q.poll();
            int id = poll[0], step = poll[1];
            // 如果彈出的點被標記「已更新」，則跳過
            if (vis[id]) continue;
            // 標記該點「已更新」，并使用該點更新其他點的「最短距離」
            vis[id] = true;
            for (int i = he[id]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[id] + w[i]) {
                    dist[j] = dist[id] + w[i];
                    q.add(new int[]{j, dist[j]});
                }
            }
        }
    }

• 時間復(fù)雜度：O(mlogn+n)
• 空間復(fù)雜度：O(m)

5，Bellman-Ford算法

為了能夠求解邊上帶有負值的單源最短路徑問題，Bellman(貝爾曼，動態(tài)規(guī)劃提出者)和Ford(福特)提出了從源點逐次繞過其他頂點，以縮短到達終點的最短路徑長度的方法。 Bellman-ford算法是求含負權(quán)圖的單源最短路徑算法，效率很低，但代碼很容易寫。即進行不停地松弛，每次松弛把每條邊都更新一下，若n-1次松弛后還能更新，則說明圖中有負環(huán)，無法得出結(jié)果，否則就成功完成。Bellman-ford算法有一個小優(yōu)化：每次松弛先設(shè)一個flag，初值為FALSE，若有邊更新則賦值為TRUE，最終如果還是FALSE則直接成功退出。

如果沒有負權(quán)回路的話,應(yīng)當會在 n - 1 次松弛之后結(jié)束算法。原因在于考慮對每條邊進行 1 次松弛的時候,得到的實際上是至多經(jīng)過 0 個點的最短路徑(初始化每個點到源點的距離為無窮,這里的經(jīng)過 0 個點意思為路徑僅由源點和終點組成),對每條邊進行兩次松弛的時候得到的至多是經(jīng)過 1 個點的最短路徑。如果沒有負權(quán)回路,那么任意兩點的最短路徑至多經(jīng)過 n - 2 個點(不包含源點和終點這兩個點),因此經(jīng)過 n - 1 次松弛操作后應(yīng)當可以得到最短路徑。如果有負權(quán)回路,那么第 n 次松弛操作仍然會成功(即第 n 次松弛仍然存在一條邊可以對其進行松弛操作),但是不存在負權(quán)回路的圖應(yīng)該在第 n - 1 次松弛之后,已經(jīng)不存在可以松弛的邊了,所以Bellman -Ford算法就利用了這個性質(zhì)以達到判定負環(huán)的目的。

例787. K 站中轉(zhuǎn)內(nèi)最便宜的航班

有 n 個城市通過一些航班連接。給你一個數(shù)組 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示該航班都從城市 fromi 開始，以價格 pricei 抵達 toi。

現(xiàn)在給定所有的城市和航班，以及出發(fā)城市 src 和目的地 dst，你的任務(wù)是找到出一條最多經(jīng)過 k 站中轉(zhuǎn)的路線，使得從 src 到 dst 的 價格最便宜 ，并返回該價格。 如果不存在這樣的路線，則輸出 -1。

解：「限制最多經(jīng)過不超過 k個點」等價于「限制最多不超過 k + 1 條邊」

class Solution {
    int N = 110, INF = 0x3f3f3f3f;
    int[][] g = new int[N][N];
    int[] dist = new int[N];
    int n, m, s, t, k;
    public int findCheapestPrice(int _n, int[][] flights, int _src, int _dst, int _k) {
        n = _n; s = _src; t = _dst; k = _k + 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                g[i][j] = i == j ? 0 : INF;
            }
        }
        for (int[] f : flights) {
            g[f[0]][f[1]] = f[2];
        }
        int ans = bf();
        return ans > INF / 2 ? -1 : ans;
    }
    int bf() {
        Arrays.fill(dist, INF);
        dist[s] = 0;
        for (int limit = 0; limit < k; limit++) {
            //每次松弛都使用上次的結(jié)果
            int[] clone = dist.clone();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[j] = Math.min(dist[j], clone[i] + g[i][j]);
                }
            }
        }
        return dist[t];
    }
}

6，SPFA算法

用一個隊列來進行維護。初始時將源加入隊列。每次從隊列中取出一個元素，并對所有與他相鄰的點進行松弛，若某個相鄰的點松弛成功，則將其入隊。直到隊列為空時算法結(jié)束；這個算法，簡單的說就是隊列優(yōu)化的bellman-ford，利用了每個點不會更新次數(shù)太多的特點發(fā)明的此算法。

class Solution {
    int N = 110, M = 6010;
    // 鄰接表
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    // dist[x] = y 代表從「源點/起點」到 x 的最短距離為 y
    int[] dist = new int[N];
    // 記錄哪一個點「已在隊列」中
    boolean[] vis = new boolean[N];
    int INF = 0x3f3f3f3f;
    int n, k, idx;
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        w[idx] = c;
        idx++;
    }
    public int networkDelayTime(int[][] ts, int _n, int _k) {
        n = _n; k = _k;
        // 初始化鏈表頭
        Arrays.fill(he, -1);
        // 存圖
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            add(u, v, c);
        }
        // 最短路
        spfa();
        // 遍歷答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void spfa() {
        // 起始先將所有的點標記為「未入隊」和「距離為正無窮」
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        // 只有起點最短距離為 0
        dist[k] = 0;
        // 使用「雙端隊列」存儲，存儲的是點編號
        Deque<Integer> d = new ArrayDeque<>();
        // 將「源點/起點」進行入隊，并標記「已入隊」
        d.addLast(k);
        vis[k] = true;
        while (!d.isEmpty()) {
            // 每次從「雙端隊列」中取出，并標記「未入隊」
            int poll = d.pollFirst();
            vis[poll] = false;
            // 嘗試使用該點，更新其他點的最短距離
            // 如果更新的點，本身「未入隊」則加入隊列中，并標記「已入隊」
            for (int i = he[poll]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[poll] + w[i]) {
                    dist[j] = dist[poll] + w[i];
                    if (vis[j]) continue;
                    d.addLast(j);
                    vis[j] = true;
                }
            }
        }
    }
}