图 | 一隅

图(Graph)是表示物件与物件之间的网状关系的数学对象,是图论基本研究对象，本文将对图相关知识进行总结。

图类问题解决步骤

图的表示：邻接矩阵或邻接表

邻接矩阵或邻接表能够方便地查询顶点之间的关系，在邻接表中，键为起点，值为终点，而邻接矩阵中，joint[i][j] == 1表示从$i$到$j$有连接，邻接表占用空间较小而邻接矩阵占用空间较大。邻接表和邻接矩阵建立方法如下：

//无向图邻接表
for(auto &v : edges){
    graph[v[0]].push_back(v[1]);
    graph[v[1]].push_back(v[0]);
}
 
//有向图邻接表    
for(auto &v : edges){
    graph[v[0]].push_back(v[1]); 
}

图的基本要素

一般来说，当讨论图问题时，会有如下要素：

顶点及顶点值，顶点集的大小叫做图的阶
顶点的度，即与某个顶点相连的边数。（对于有向图，度可进一步分为入度和出度即顶点的入边条数及出边条数）
边及边权重

图的基本操作

图的DFS和BFS遍历

DFS

Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组
Status (*VisitFunc)(int v); // VisitFunc是访问函数，对图的每个顶点调用该函数
void DFSTraverse (Graph G, Status(*Visit)(int v)) {
    VisitFunc = Visit;
    for (v = 0; v < G.vexnum; ++v)
        visited[v] = FALSE; // 访问标志数组初始化
    for (v = 0; v < G.vexnum; ++v)
        if (!visited[v])
            DFS(G, v);  // 对尚未访问的顶点调用DFS
}
void DFS(Graph G, int v) { // 从第v个顶点出发递归地深度优先遍历图G
    visited[v] = TRUE;
    VisitFunc(v);   // 访问第v个顶点
    for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
        // FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。
        // 若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。
        // 若w是v的最后一个邻接点，则返回空（0）。
        if (!visited[w])
            DFS(G, w);  // 对v的尚未访问的邻接顶点w调用DFS
}

BFS

Boolean visited[ MAX_VERTEX_NUM ]; // 访问标志数组
Status (* VisitFunc)(int v); // VisitFunc是访问函数，对图的每个顶点调用该函数

void BFSTraverse(Graph G, Status(* Visit)(int v)) {
    VisitFunc = Visit;
    for (v = 0; v < G.vexnum; ++v)
        visited[v] = FALSE;
    initQueue(Q); // 置空辅助队列Q
    for (v = 0; v < G.vexnum; ++v) {
        if (!visited[v]) {
            visited[v] = TRUE;
            VisitFunc(v);
            EnQueue(Q, v); // v入队列
            while (!QueueEmpty(Q)) {
                DeQueue(Q, u); // 队头元素出队并置为u
                for (w = FirstAdjVex(G, u);
                        w >= 0; w = NextAdjVex(G, u, w))
                    if (!Visited[w]) { // w为u的尚未访问的邻接顶点
                        Visited[w] = TRUE;
                        VisitFunc(w);
                        EnQueue(Q, w);
                    }
            }
        }
    }
}

二分图

二分图定义¹

二分图（Bipartite graph）是一类特殊的图，它可以被划分为两个部分，每个部分内的点互不相连。下图是典型的二分图。可以看到，$X$与$Y$内部节点互不连接，而相互之间有连接。

图片名称

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

二分图性质

一个图若果为合法的二分图应是不存在一个或多个包含奇数个元素的环。

二分图基本操作

判断二分图（染色法）

思路

二分图和红黑树有一些类似，对于红黑树来说，一个节点要么是红要么是黑；同理，对于二分图，其节点要么为红，要么为黑。我们可以使用贪心的方法给图进行着色，一个节点为黑，那么所有邻接节点均为红，其邻接节点的邻接节点均为黑，以此类推。我们可以使用DFS或BFS解决此类问题。需要注意的是因为图中可能存在孤岛，因此需要遍历所有的节点。

代码

 bool isBipartite(vector<vector<int>>& graph) {
     int n = graph.size();
     vector<int> visited(n,0);
     for(int i=0;i<n;i++){
         if(!dfs(graph, visited,i,0)) return false;
     }
     return true;
 }

bool dfs(vector<vector<int>>& graph,
         vector<int>& visited,
         int cur,
         int last_color){
    if(visited[cur] != 0){   //说明当前节点已经被访问 1: 节点属于1, -1：节点属于-1
        return visited[cur] != last_color;
    }

    visited[cur] = last_color == 1 ? 2 : 1;
    for(int i=0;i<graph[cur].size();i++){
        if(!dfs(graph, visited, graph[cur][i],visited[cur])) return false;
    }
    return true;
}

匈牙利算法（用于解决二分图最大匹配和最小点覆盖问题）

最大匹配问题

在上面的图中，如果X和Y中节点只能是一一匹配的关系，那么最大能够有多少个匹配数？

最小点覆盖问题

另外一个关于二分图的问题是求最小点覆盖：我们想找到最少的一些点，使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是，删除包含这些点的边，可以删掉所有边。在上面的图中，删除Y2、X3、Y4即可删除所有的边。

匈牙利算法应用

棋盘覆盖（LeetCode LCP4）²

你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌，你想把这些骨牌不重叠地覆盖在完好的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。

输入：n = 2, m = 3, broken = [[1, 0], [1, 1]]
输出：2
解释：我们最多可以放两块骨牌：[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。

图片名称

棋盘覆盖是一个经典的问题，查看下面的棋盘：

图片名称

我们将棋盘染色，使黑白相互间隔，那么染色之后棋盘构成了一个二分图，白格只与黑格相连接，每个未删除的格子都与上下左右紧邻的未删除的格子相连，那么二分图的最大匹配数就是能放下的多米诺骨牌数目。

无向图

无向图的定义

在无向图中没有方向，节点u和v如果连接，则可以相互访问。

无向图基本操作

保存索引

在使用无向图直线，要先将边的两个节点构成的索引对利用哈希进行保存，从而实现快速查找，需要注意的是，一个节点可能与多个节点相连，所以索引的值是vector

for(auto &v : edges){
    graph[v[0]].push_back(v[1]);
    graph[v[1]].push_back(v[0]);
}

深拷贝

133. 图的深拷贝图的深拷贝过程中，由于有环的存在，可能会出现重复搜索的情况，因此我们需要一个hashmap，对已经访问过的节点进行保存，如果发现某个节点已经被拷贝，那么直接返回复制的节点即可。

class Node {
public:
    int val;
    vector<Node*> neighbors;
    
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
    unordered_map<Node*, Node*> node_map{};
public:
    Node* cloneGraph(Node* node) {
        if(node == nullptr) return nullptr;

        if(node_map.find(node) != node_map.end()) return node_map[node];

        Node* result = new Node(node->val);
        node_map[node] = result;
        for(auto &v : node->neighbors){
            result->neighbors.push_back(cloneGraph(v));
        }
        
        return result;
    }
};

相关问题还包括二叉树或链表的深拷贝

计算无向图中连通分量的数目

323. 无向图中连通分量的数目

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

示例 1:

输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]
0          3
|          |
1 --- 2    4 
输出: 2
示例 2:

输入: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
0           4
|           |
1 --- 2 --- 3
输出: 1
注意:
你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，[0, 1] 与 [1, 0] 相同，所以它们不会同时在 edges 中出现。

示例 1:

输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]

 0          3
 |          |
 1 --- 2    4

输出: 2
你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，[0, 1] 与 [1, 0] 相同，所以它们不会同时在 edges 中出现。

解法1：DFS

代码

int countComponents(int n, vector<vector<int>>& edges) {
    if(edges.empty() )return n;
    map<int,vector<int>> graph{};
    vector<int> visited(n,0);
    for(auto &v : edges){
        graph[v[0]].push_back(v[1]);
        graph[v[1]].push_back(v[0]);
    }

    int ans = 0;
    for(int i=0;i<n;i++){
        if(visited[i] == 0){
            ans ++;
            dfs(graph, visited, i);
        }
    }
    return ans;
}

void dfs(map<int, vector<int>>& graph, vector<int>& visited, int i){
    visited[i] = 1;
    for(auto &v : graph[i]){
        if(!visited[v]){
            dfs(graph, visited, v);
        }
    }
}

解法2：BFS

解法3：查并集

判断是否成环

图片名称

解法1：DFS

思路

我们从下面的图进行考虑

点击显示/隐藏

      0
    /   \
   1     2 
       /   \
     3-------4
     
可以看到，图中2,3,4顶点构成了环，我们把没访问过的顶点记录为i，访问过的记录为i*，从顶点0开始进行访问，设定其父顶点为-1

      0*
    /   \
   1     2 
       /   \
     3-------4
访问后，顶点0状态改变，顶点

代码

stack<int> point{};
point.push(0);
vector<bool> visited(n,0);
while(!point.empty()){
    int cur = point.top();
    point.pop();
    visited[cur] = true;

    for(int i=0;i<n;i++){
        if(graph[cur][i] == 1){    //添加和当前搜索点相连的节点
            if(visited[i] == true) return false;     //例如有三个节点 i,j,k；通过i可以访问j和k，因此j和k要被压入栈中，而如果通过j访问到了k，且k已经被访问，说明i,j,k之间构成了环形
            visited[i] = true;
            
           	graph[cur][i] = 0;  //已经访问过的节点要删掉，防止重复访问
            graph[i][cur] = 0;
            
            point.push(i);
        }
    }
}

解法2：BFS

和DFS类似

解法3：查并集

查并集这种数据结构对于判断环是非常有用的，我们只需要判断一条边两个节点是否已经连接在一起，即可判断是否成环。

例题

261. 以图判树

判断图中子图的连通性

在有些图中，子图之间可能没有桥，从而子图被分割为了两个部分，这种情况下需要我们对连通性进行判断，判断方法也比较简单，对图进行遍历，更新visited矩阵，然后遍历visited矩阵，看是否所有的图都能被访问到。

1
2
3

for(int i=0;i<n;i++){
    if(!visited[i]) return false; //有顶点没有被访问，说明出现了断桥
}

专题：染色问题

染色问题要求我们在图中对节点进行染色，相邻的节点为不同的颜色。本节将对常见的染色问题进行总结。

例题

1042. 不邻接植花

有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。

paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。

另外，没有花园有 3 条以上的路径可以进入或者离开。

你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。

以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。

思路

我们的染色集合为$C={1,2,3,…,n}$，假设目前我们处理第$i$个节点，与节点$i$相连的节点集合为$Pi={j_1,j_2,…,j_m}$，其颜色集合为$C_i={C{j1},C{j2},C{j3}…,C{j_m}}$，那么$i$可选取的颜色为$C\cap C_i$

代码

vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
    map<int, vector<int>> paths_table{};
    for(auto &v: paths){
        paths_table[v[0]-1].push_back(v[1]-1);
        paths_table[v[1]-1].push_back(v[0]-1);
    }

    vector<int> ans(N,0);
    for(int i=0;i<N;i++){
        set<int> color{1,2,3,4};
        for(int k = 0;k < paths_table[i].size();k++){
            color.erase(ans[paths_table[i][k]]);
        }
        ans[i] = *(color.begin());
    }
    return ans;
}

有向图

有向图的定义

有向图基本操作

判断是否成环（有向无环图）

算法流程

借助一个标志表visited，用于判断每个节点i的状态
- $i=0$：尚未访问
- $i=1$：已被当前节点出发的DFS访问
- $i=-1$：已被其他节点出发的DFS访问
对图中所有节点依次执行DFS，判断每个节点出发的DFS是否存在环，存在则返回False，流程如下：
- 终止条件
  - 当visited == -1，说明当前访问节点已被其他节点出发的DFS访问，无需重复搜索，直接返回$true$
  - 当visited == 1，说明当前访问节点已被本节点出发的DFS第二次访问，存在环，直接返回$false$
- 将当前节点i对应的visited[i]置1，代表本节点已被访问
- 递归访问i的邻接节点，发现环直接返回$false$
- 当前节点所有邻接节点已被访问，不存在环，则将visited[i]设为-1并返回$true$
整个图均未发现环，则返回$true$

代码

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    map<int, vector<int>> graph{};
    vector<int> visited(numCourses,0);
    for(auto &v : prerequisites){
        graph[v[0]].push_back(v[1]);
    }
    for(int i=0;i<numCourses;i++){
        if(!dfs(graph, visited, i)) return false;
    }
    return true;
}

bool dfs(map<int, vector<int>>& graph, vector<int>& visited, int cur_course){ //true : 图无环
    if(visited[cur_course] == 1) return false;
    else if(visited[cur_course] == -1) return true;
    else{
        visited[cur_course] = 1; //正在搜索状态
        for(int i=0; i < graph[cur_course].size();i++){
            int next_course = graph[cur_course][i];
            if(!dfs(graph,visited,next_course)) return false;
        }
        visited[cur_course] = -1;  //搜索完成状态
        return true;
    }

}

判断是否有路径

查并集

例题

面试题 04.01. 节点间通路

节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。

输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
输出：true

使用图的深度优先搜索即可完成，这一部分请参考图的深度优先搜索部分。

带权值有向图

使用查并集处理带权有向图问题

例题

399. 除法求值

给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。

示例 :
给定 a / b = 2.0, b / c = 3.0
问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]

输入为: vector> equations, vector& values, vector> queries(方程式，方程式结果，问题方程式)，其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。返回vector类型。

基于上述例子，输入如下：

equations(方程式) = [ [“a”, “b”], [“b”, “c”] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ [“a”, “c”], [“b”, “a”], [“a”, “e”], [“a”, “a”], [“x”, “x”] ].
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。

思路

本题目就是典型的带权有向图问题。在解决问题之前，我们先做出如下定义：

$f(a,b) = \frac{a}{b}$
parent[b] = a
令$b$在查并集中的根节点为root(b)
weight[b]表示root(b)/b的值，即

$w_b=\frac{r_b}{b}$

假设root(a)到a的路径为

graph LR
    nodera((root_a))
    nodea1((a1))
    nodea2((a2))
    nodean((an))
    nodea((a))

    nodera-->nodea1
    nodea1-->nodea2
    nodea2-->|...|nodean
    nodean-->nodea

考虑$\frac{r_a}{r_b}$，我们有如下递推关系式：

$\begin{aligned} \frac{r_a}{r_b} &= \frac{r_a/a_1}{r_b/b_1}\frac{a_1}{b_1}\\ &=\frac{f(r_a,a_1)*a_1}{f(r_b,b_1)*b_1}\\ &=\frac{f(r_a,a_1)*f(a_1,a_2)*a_2}{f(r_b,b_1)*f(b_1,b_2)*b_2}\\ &...\\ &=\frac{f(r_a,a_1)*f(a_1,a_2)*...*f(a_n,a)*a}{f(r_b,b_1)*f(b_1,b_2)*...*f(b_m,b)*b}\\ &=\frac{pm(a)}{pm(b)}\frac{a}{b} \end{aligned}$

如果我们知道了$r_a,r_b,pm(a),pm(b)$，即可求出$a/b$的值，$pm(a)=f(p(a),a)*pm(p(a))$，其中$p(a)$为$a$的父节点

代码

专题：有向图的出度与入度

对有向图而言，度可以分为入度和出度，有些问题需要我们计算有向图顶点的静流量，此时我们需要利用入度和出度进行计算。

使用出入度的常见场景

对于一棵二叉树，根节点入度一定为0，叶节点出度为0，中间节点则既有出度也有入度

1361. 验证二叉树

二叉树上有 n 个节点，按从 0 到 n - 1 编号，其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。只有所有节点能够形成且只形成一颗有效的二叉树时，返回 true；否则返回 false。如果节点 i 没有左子节点，那么 leftChild[i] 就等于 -1。右子节点也符合该规则。注意：节点没有值，本问题中仅仅使用节点编号。

graph TB
    node0((0))
    node1((1))
    node2((2))
    node3((3))

    node0-->node1
    node0-->node2
    node2-->node3

输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
输出：true

思路

我们首先要找到根节点，即入度为0的节点（可能不止一个，稍后讨论不止一个的情况），然后从该节点开始，进行搜索，看所有的节点是否都只访问了一次（如果多次，说明存在环或者多条路径，如果没访问，说明存在孤岛节点），从而判断是否为二叉树。

代码

//注意，本题使用中序遍历时间复杂度过高，所以采用前序实现
class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        vector<int> inIndex(n,0);
        int root = -1;
        for(int i=0;i<n;++i){
            if(leftChild[i] !=-1)  inIndex[leftChild[i]]++;
            if(rightChild[i]!=-1) inIndex[rightChild[i]]++;
        }
        for(int i=0;i<n;i++){
            if(inIndex[i] == 0){
                root = i;
                break;
            }
        }
        if(root == -1) return false;

        stack<int> nodes{};
        vector<int> seen(n,0);
        int curr = root;
        int seen_nodes_num = 0;

        nodes.push(curr);
        seen[curr]++;
        seen_nodes_num++;

        while(!nodes.empty()){
            int u = nodes.top();
            nodes.pop();

            if(leftChild[u] != -1){
                if(seen[leftChild[u]] != 0) return false;
                else{
                    seen[leftChild[u]]++;
                    seen_nodes_num++;
                    nodes.push(leftChild[u]);
                } 
                
            }
            if(rightChild[u] != -1){
                if(seen[rightChild[u]] != 0) return false;
                else{
                    seen[rightChild[u]]++;
                    seen_nodes_num++;
                    nodes.push(rightChild[u]);
                } 
                
            }
        }

        return seen_nodes_num == n;
    }
};
//其实就是在前序中多了几步判断，要求每个节点至少且至多访问一次。

例题

997. 找到小镇的法官

找到阶为N的图中的某个顶点，其入度为N-1，出度为0

思路

只要计算每个定点的出度与入度即可。

最短路径问题

拓扑排序

拓扑排序的定义

假设有$n$个变量，还有$m$个二元组$(u,v)$，分别表示变量$u$小于$v$，那么所有变量从小到大排列的结果应该为什么样呢？例如四个变量$a,b,c,d$，如果已知$a<b,c<d,d<c$，则可能排序结果为：$a<d<c<b$或$d<a<c<b$。如果我们将变量视为一个点，小于关系看作一条有向边，那么就得到了一个有向图。我们的实际任务是把图所有节点排序，使$(u,v)$对应的$u$排在$v$之前。

拓扑排序的性质

如果图 $G$ 中存在环，那么图 $G$ 不存在拓扑排序
有向无环图拓扑排序可能不唯一

拓扑排序实现代码

解法1：DFS

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    this->numCourses = numCourses;
    graph.resize(numCourses);
    visited.resize(numCourses);
    hasCircle = false;

    for(const auto& v:prerequisites){
        graph[v[0]].push_back(v[1]);
    }

    for(int i=0;i<numCourses && !hasCircle;i++){
        if(visited[i] == 0){
            dfs(i);
        }

    }
    if(hasCircle) return {};
    return ans;
}

void dfs(int u){
    visited[u] = 1; //搜索中
    for(auto &v : graph[u]){
        if(visited[v] == 0){ //节点未搜索
            dfs(v);
            if(hasCircle) return;
        }
        else if(visited[v] == 1){   //节点搜索中，说明形成了环？此处存疑
            hasCircle = true;
            return;
        }
    }
    visited[u] = 2;
    ans.push_back(u);
}
// 拓扑排序其实和判断有向无环图代码类似，只不过多加了一步保存搜索结束的节点的过程

解法2：BFS

路径规划³

最小生成树

图的生成树是一棵含有其所有的顶点的无环联通子图，一幅加权图的最小生成树（ MST ） 是它的一颗权值（树中所有边的权值之和）最小的生成树。

求加权图的最小生成树算法

假定一个图中有$N$个顶点，连接两个顶点会有一个成本cost，返回连接所有顶点的最小权值。对于加权图的最小生成树，我们可以确定的一点，最小生成树一定是无环的，因为如果有环，删掉一条边之后，权重一定会变小。

kruskal 算法

Kruskal算法的基本原理是排序+查并集，首先将所有路径进行排序，然后利用查并集连接节点，如果某条边会够成环，就跳过该边，最后对路径数目进行累加，如果路径数目为$N-1$，代表所有的节点已经连接。具体步骤如下：

将所有的边按照权重从小到大排序。
取一条权重最小的边。
使用并查集（union-find）数据结构来判断加入这条边后是否会形成环。若不会构成环，则将这条边加入最小生成树中。
检查所有的结点是否已经全部联通，这一点可以通过目前已经加入的边的数量来判断。若全部联通，则结束算法；否则返回步骤 2.

Prim算法

Prim算法本质上是一个贪心算法，其基本原理

最短路算法

Floyd 算法

考虑如下问题，在加权无向图中，给定一个阈值距离$D$，找到某个节点$i$，使该节点在阈值距离$D$内邻居节点数目最少，此类问题我们可以使用Floyd算法解决。该算法本质上是一种动态规划算法，步骤如下：

令dp[i][j]为从i到j的最短距离
$n$个节点依次作为插入节点，例如当前插入节点为$k$，若dp[i][k] + dp[k][j] < dp[i][j]，更新dp[i][j]，即dp[i][j]=min(dp[i][k]+dp[k][j], dp[i][j])。

// Floyd算法
for (int k = 0; k < n; k++) {
// n个顶点依次作为插入点
// 注意插点k是放在第一层循环
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = min(dp[i][k]+dp[k][j], dp[i][j]);
        }
    }
}

为什么k要放在第一层循环⁴

这个源自Floyd的核心思想—动态规划，代码中的二维状态转移方程D[i][j] = min(D[i,k]+D[k,j],D[i,j]);，其实是从三维简化得到的。我们不妨从最初的三维说起，思路和二维一样：

首先定义状态数组（也就是距离矩阵）D[n][n][n]，其中D[k][i][j]表示顶点i, 顶点j通过前k个顶点（0~k）得到的最短距离。

D[k][i][j]是从D[k-1][i][j]和D[k-1][i][k] + D[k-1][k][j]两者中值较小的一个转移得到的，也就是说要在前k-1个顶点已经插入，更新距离矩阵状态之后，第k个顶点才能作为插入顶点。

归纳得到状态转移方程：D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])。

其中k的作用是标志到达了第几个插入点，也就是状态数组到达了哪个状态，不用刻意记录，于是减去第一维就变成了二维。明白了Floyd的三维dp思想，根据状态转移方程在编码时就很自然的会将 k 放在第一层循环，而将k放在最后一层则是错误的编码。

图类问题解决步骤

图的表示：邻接矩阵或邻接表

图的基本要素

图的基本操作

图的DFS和BFS遍历

DFS

BFS

二分图

二分图定义1

二分图性质

二分图基本操作

判断二分图（染色法）

匈牙利算法（用于解决二分图最大匹配和最小点覆盖问题）

匈牙利算法应用

无向图

无向图的定义

无向图基本操作

保存索引

深拷贝

计算无向图中连通分量的数目

解法1：DFS

解法2：BFS

解法3：查并集

判断是否成环

解法1：DFS

解法2：BFS

解法3：查并集

例题

判断图中子图的连通性

专题：染色问题

例题

有向图

有向图的定义

有向图基本操作

判断是否成环（有向无环图）

算法流程

代码

判断是否有路径

查并集

例题

带权值有向图

使用查并集处理带权有向图问题

例题

专题：有向图的出度与入度

使用出入度的常见场景

例题

最短路径问题

拓扑排序

拓扑排序的定义

拓扑排序的性质

拓扑排序实现代码

解法1：DFS

解法2：BFS

路径规划3

最小生成树

求加权图的最小生成树算法

kruskal 算法

Prim算法

最短路算法

Floyd 算法

参考文献

二分图定义¹

路径规划³