[[算法/数据结构/实验/图|图]] 实验

易混点

1. 无向图的堆成存储存的是图的下半部分
2. 即使是有向图其邻接矩阵也不一定不对称，当每个节点的出度和入度相同的时候，结果是对称的。

连通图、连通分量

1. 原图的子图
2. 连通分量本身连通
3. 极大顶点数
4. 极大边数：包含极大顶点所包含的所有边

存储

最基础的是邻接矩阵和邻接表法，不再赘述。

链式前向星

https://www.bilibili.com/video/BV1Mi4y1s7Yi 由 head 中引出指针指向其一个邻接点，然后通过链表存储其余邻接点（以及对应边的权重），最终指向数组的开头，这样便存储了一个节点及其周围的邻接点。

表示

1. 图的邻接矩阵类型封装 教材中的多重 typedef 定义

   typedef struct GNode *PtrToNode;
   struct GNode{
       int nv;
       int ne;
       int G[100][100];
   };
   typedef PtrToNode MGraph;

   实质上是把图的存储结构封装在结构体中，用一个 PtrToNode 的指针指向这个存储结构，并将指针定义为 Mgraph 类型。 本质上是为了通过指针去访问图结构。
2. 边的类型定义 类型区分
3. 初始化

typedef int Vertex; /* 用顶点下标表示顶点,为整型 */
MGraph CreateGraph(int VertexNum)
{
    Vertex V, W;
    MGraph Graph;
    Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    /* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
    for (V = 0; V < Graph->Nv; V++)
        for (W = 0; W < Graph->Nv; W++)
            Graph->G[V][W] = 0; /* 或INFINITY */
    return Graph;
}

无权单源最短路

通过 dist，path 分别记录整个图中每个节点到 源点 S的距离，以及最短路径在该节点之前的那个节点。 每次访问节点后，更新距离为之前节点距离+1，并标记前一个节点。 算法正确性 该算法本质上还是一个广搜，所以是进行的层序遍历，因此每次访问到的节点就是最短的，并且限制了对节点的重复访问，故算法正确。 时间复杂度 每个节点都被入队、出队一次，每条边访问了一次（for 循环找每个邻接点），故时间复杂度为 $T=\mathbf{O}(|V|+|E|)$

有权单源最短路

负值圈

Dijkstra 和 Floyd 都不允许出现负值圈，否则会重复降路径代价越降越低。

Dijkstra 算法

顶点集合，其中的顶点的最短路径都已经确认：

$$S=\{\mathrm{源}\mathrm{点}s+\mathrm{已}\mathrm{经}\mathrm{确}\mathrm{定}\mathrm{了}\mathrm{的}\mathrm{最}\mathrm{短}\mathrm{路}\mathrm{径}{V}_i\}$$

对未收录的顶点 $v$，其最短路径只能经过 $S$ 中的顶点，即 $\{s\to ({\mathbf{v}}_{\mathrm{i}}\in \mathbf{S})\to \mathbf{v}\}$ 的最小长度。 过程

1. 初始化所有点的 dist 和 path 信息，设定源点 path 为 0，在初始化过程中更新源点邻接点的 dist 和 path 信息
2. 在未标记节点中寻找距离最短的节点，收录这个点
3. 更新其邻接点的距离 注意这个所谓寻找最短节点是指距离源点 $s$ 距离最短的节点，因为一开始所有的节点（除源点）这个距离都被标记为 $\mathrm{\infty }$，所以每次找到的最短点之前的向前的邻接点之前必然被标记过（因为这些非 $\mathrm{\infty }$ 点本身就是由之前的点扩展来的），所以每次新增的点必然与之前标记过的节点连通。

具体实现+优化 [[Dijkstra]]

有权多源最短路

Floyd 算法

初始状态 $D^{-1}$ 和 $P^{-1}$，角标代表每次检查时选取的中间点 $v$ ，每次检查除去编号为 $v$ 的行和列以及对角线后剩下的点经过 $v$ 是否满足：

$$A_{i,j}>A_{i,v}+A_{v,j}$$

若满足，则更新当前点的最短路径长度及前向节点，得到演变后的矩阵 $D^v$ 和 $P^v$（事实上不需要做特殊处理，因为被排除的点不满足该条件其实是不会被更新的，因此不能取等于）。 最后会得到最终的 $D$ 和 $P$ 矩阵。 其中 $P$ 矩阵中值为 $-1$ 则代表最短路径就是两点间之间相连的边，否则就要经过前向点并递归向前查找才能找到两点间的最短路。

#include <bits/stdc++.h>
using namespace std;
#define NODE_NUM 3
#define M 1000

struct Mgraph{
    int nv;
    int ne;
    int G[NODE_NUM][NODE_NUM];
};

void out(int a[NODE_NUM][NODE_NUM]){
    //output
    for(int i = 0;i<NODE_NUM;i++){
        for(int j = 0;j<NODE_NUM;j++){
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
}

bool Floyd(Mgraph g){
    int D[NODE_NUM][NODE_NUM];
    int path[NODE_NUM][NODE_NUM];

    //init
    for(int i = 0;i<g.nv;i++){
        for(int j = 0;j<g.nv;j++){
            D[i][j] = g.G[i][j];
            path[i][j] = -1;
        }
    }

    for(int k = 0;k<g.nv;k++){//矩阵角标(中间点)
        for(int i = 0;i<g.nv;i++){
            for(int j = 0;j<g.nv;j++){
                if(D[i][j] > D[i][k] + D[k][j]){//i->j
                    D[i][j] = D[i][k] + D[k][j];
                    if(i == j && D[i][j] < 0){
                        return false;
                    }
                    path[i][j] = k;
                }
            }
        }
    }
    out(D);
    cout << endl;
    out(path);
    return true;
}

int main(int argc, char const *argv[])
{
    Mgraph g;
    g.nv = 3;
    g.ne = 5;
    int gr[NODE_NUM][NODE_NUM] = 
    {
        {0,4,11},
        {6,0,2},
        {3,M,0}
    };
    memcpy(g.G, gr, sizeof(gr));
    Floyd(g);
    return 0;
}

最小生成树

强连通图

图中任意一对顶点 $V_i$ 和 $V_j$ 均既有从 $V_i$ 到 $V_j$ 的路径，也有 $V_j$ 到 $V_i$ 的路径（来回双向路径），称为强连通图。

强连通分量

在图的连通分量基础上要求这个图是强连通的。

生成树

图 $G$ 包含全部 $n$ 个顶点的极小连通子图，必定且仅包含 $G$ 的 $n-1$ 条边。生成树可能不唯一。生成树没有回路。（因为包含的 $n-1$ 条边是串联那几个点的最少边数，再往上加显然会出现回路）

有向树

根节点入度为 0，其余父节点入度为 1。

生成森林

对应各个连通分量的各课生成树。

---

最小生成树就是从生成森林中寻找各边权重和最小的生成树。各算法实质是贪心，需要满足约束条件：

Prim 算法