图论算法：最短路径与最小生成树

素颜马尾好姑娘i 2022-10-29 09:24 155阅读 0赞

# 图论算法 #

对于很多图论问题，并不是说必须构建一个符合 graph 规则的邻接矩阵

*  因为说到底邻接矩阵是为了表示两个节点是否可达，对于邻接表来说，每个节点就是 0、1、2…，所以如果使用邻接表来表示图，那么还需要建立对象和 0、1、2… 这些数字的对应关系
 *  多数情况下，图论问题的节点就是题目中给出的对象，两个节点间的直接连通关系是根据题目给的条件得到，而任意两个节点（或者说对象）间的连通关系，是根据状态转移方程得到的。所以绝大多数题目中并不是根据规则先构建个邻接表，然后再使用图论算法。

## 最短路径 ##

### DFS ###

实现：递归（代码略）

适用：无环图

**对于：状态转移有环，但是并非求最短路径的题目**

*  使用 DFS + path 数组即可
 *  **如果状态转移出现重叠子问题（即每个节点被多次使用），并且满足最优子结构（即一个节点不管其下面有多少种路径，但返回值只有一个）**，那么就可以转为动态规划问题，然后便可使用**记忆化搜索**

### BFS ###

实现：队列

*  如果有环，则再加个 visited 数组

适用：任何无权图

例题：[【LeetCode】队列与 BFS ][LeetCode_ BFS]

### Floyd 算法 ###

适用：所有图（即有权与无权均可）

#### 实现 ####

是一种动态规划算法

*  每个状态有的决定因素有两个，起始节点和终止节点（即 dp 数组是二维的）
 *  状态转移方程
    
    `fun(i , j) = max([i , j] , max([i , k] + [k , j]))`

typedef struct          {         
        char vertex[VertexNum];                                //顶点表 
        int edges[VertexNum][VertexNum];                       //邻接矩阵（对于两个边不可达的是无穷） 
        int n,e;                                               //图中当前的顶点数和边数 
    }MGraph; 
    
    void Floyd(MGraph g){ 
        int A[MAXV][MAXV]; // dp 数组
        int path[MAXV][MAXV]; // 路径（跟 dp 数组对应的，每个节点的下一步）
        int i,j,k,n=g.n;
        
        // 初始化 dp 数组（对于 dp 问题大多数都要初始化，或者多开辟一行）。
        for(i=0;i<n;i++){ 
            for(j=0;j<n;j++){  　　
                A[i][j]=g.edges[i][j];
                path[i][j]=-1;
            }
        }
        
        // 常规动态规划的模板
        // 至于这个 k 为什么放最外层，根据状态方程 dij(k) = min(dij(k-1) , dik(k-1) + dkj(k-1)), k-1 代表不包含k时的值，
        // 可以理解为 k 是每次增加一个（即中间节点每次加一个），把 i 和 j 看成一个整体（代表 i 到 j）的长度。
        // 对于常规的，在状态转移方程里有 3 个变量，但是状态的决定属性只有两个，那么把状态多的那个属性放在最外层，把里面的二维看作一个整体，每次外层增加一个然后选择最优。
        // 跟背包问题其实很像，对于 k 都是只能选一次，因为一旦选了 k 作中转，后面如果再选 k 作中转，那么会形成环，是肯定不可达 i 或者 j 的，所以问题就变成了每个节点只可以选一次，那么只有选不选这两种情况，所以就还是背包问题。
        for(k=0;k<n;k++){  
            for(i=0;i<n;i++){ 
                for(j=0;j<n;j++){ 
                    if(A[i][j]>(A[i][k]+A[k][j])){                    　　
                        A[i][j]=A[i][k]+A[k][j];
                        path[i][j]=k;
                    } 
                }
            } 
        } 
        
    }

## 最小生成树 ##

### Prim 算法 ###

*  **核心：基于贪心算法**
 *  状态转移：i -> j
    
     *  条件：j 没有被选中，并且权重最小。
     *  其中：i 是所有选中节点的集合

Prim算法基于贪心算法设计，其从一个顶点出发，选择这个顶点发出的边中权重最小的一条加入最小生成树中，然后又从当前的树中的所有顶点发出的边中选出权重最小的一条加入树中，以此类推，直到所有顶点都在树中，算法结束。

下面举一个例子来说明。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70][]

*  上图是一个无向图，假设我们从顶点a出发使用Prim算法计算最小生成树，其算法运行过程如下。
 *  ① 顶点a发出的边包括<a,b>和<a,d>和<a,f>，其中权重最小的边为<a,f>，于是我们将边<a,f>加入到最小生成树中，此时最小生成树包括下图中的阴影边和灰色顶点。
    
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1][]
 *  ② 接下来我们继续从当前最小生成树中的顶点发出的所有边中寻找权重最小的一条，即边<a,b>、<a,d>、<f,c>中的边<a,d>，于是我们将边<a,d>加入到树中，如下图所示。
    
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2][]
 *  ③ 继续上述步骤，从顶点a、f、d发出的边中选出权重最小的一条，即边<a,b>，并将它加入树中，如下图所示。
    
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3][]
 *  重复上述步骤，最后得到图的最小生成树如下图所示。
    
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 4][]

[LeetCode_ BFS]: https://editor.csdn.net/md/?articleId=113786544
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221024/2615dde750664538a4e5939402fff1c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]: /images/20221024/626b22b347df42e2bfc3250c8e7574c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2]: /images/20221024/63e1e28dac72449890c71dae421ef8d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3]: /images/20221024/658fb2bf466e43529427320cc265e4b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 4]: /images/20221024/128baf04e7a6433a9b7698c4b408ded4.png