网状结构，逻辑关系是多对多

1 图的基本概念和术语

图G有集合V和E组成，记作$G=(V,E)$，图中的结点称为顶点，$V(G)$是顶点的非空有穷集，相关的顶点偶对称为边，$E(G)$是边的有穷集

顶点表示数据元素，边表示数据元素之间的逻辑关系，分为有向边(顶点的有序对)，和无向边(顶点的无序对)，根据图的边的性质，图分为有向图和无向图

• 有向图：边是顶点的有序对，$<v,w>$，v为弧尾，w为弧头
• 无向图：边是顶点的无序对

这就是一个有向图

这是无向图

网是边带有权值的图，无向图称为无向网，有向图称为有向网，这个权值在不同的问题上可能代表不同的含义，比如在交通网中，权值可能是两个地点之间的距离、时间、交通工具费用等

如果一个图的结点集合和边的集合都是另一个图对应集合的子集，则称这个图是另一个图的子图

n个结点的含有$\frac{n(n-1)}{2}$个边(每两个结点之间必有一条边相连)的无向图称为完全图，n个结点，含有$e=n(n-1)$条弧的有向图称为有向完全图

若边或者弧的个数$e<n\log n$则称作稀疏图，否则称作稠密图

若两个顶点之间存在一条边，则称这两个顶点互为邻接点，这条边和这两个点相关联

无向图中和顶点v关联的边的数目，即v连接的边的数量，定义为v的度，记为$TD(v)$，有向图的顶点的度分为入度和出度，入度记为$ID(v)$，出度记为$OD(v)$，它的度为$TD(v)=ID(v)+OD(v)$

若图从一个结点到另一个结点能存在一条经过其他节点和边的通路，则称这两个结点之间存在一条路径，在有向图中就叫从一个顶点到另一个顶点的一条有向路径，路径经过的边的数目称作路径长度，路径序列中顶点不重复出现的路径就叫做简单路径，第一个顶点和最后一个相同的路径叫做回路

若无向图G中任意两个顶点之间都有路径相联通，则称这个图是连通图，若一个无向图是非连通图，则这个图的各个极大联通子图称为这个图的联通分量(离散也学过的，就是把图切成几份，让子图集合里的子图都联通到不能再联通)

若有向图中任意两个顶点之间都存在一条有向路径，则称这个有向图为强连通图，否则其各个极大强联通子图称作它的强联通分量

假设一个连通图有n个顶点和e条边，其中$n-1$个边和$n$个顶点构成一个极小联通子图，称这个极小连通子图为这个连通图的生成树

对于非连通图，则称由各个连通分量的生成树的集合为这个非连通图的生成森林

如果一个有向图恰好和树差不多，只有一个顶点的入度为0，其他顶点的入度为1，则称该图为一个有向树，对于非强连通图的强联通分量，包含它的全部顶点，$n-1$个弧，且只有一个顶点入度为0，其余入度为1的子图称为这个连通分量的有向生成树，所有强联通分量的有向生成树构成这个有向图的生成森林

2 图的存储结构

2.1 邻接矩阵存储

n个顶点的图用两个数组存放，一个二维数组($n\times n$)存放顶点之间的逻辑关系(边和弧)，边和弧没有权值的情况下，如果顶点之间有连接就为1，没有连接就为0，如果有权值，则0或者$\infty$表示没有连接，有其他数字就表示有连接，同时存储数据信息和逻辑信息，一维数组存放顶点信息(结点内数据元素的值)

对于二维数组A，A[i][j]就表示结点$v_{i}$和$v_{j}$之间是否存在边

显然无向图的邻接矩阵是个对称阵，我们可以采用对称阵的压缩存储方法存储

#define MAXSIZE 100
typedef struct{
    VertexType vexs[MAXSIZE]; // 一维数组，用于存顶点信息
    int arcs[MAXSIZE][MAXSIZE]; // 邻接矩阵
    int vexnum,arcnum; // 顶点和边的数量
    int kind; // 图是个有向图还是无向图
}MGraph;

2.2 邻接表存储

对图中每个顶点建立一个单链表，存储与顶点关联的边或者弧，用一个一维数组存储每个顶点的信息和相应单链表的头指针

对于无向图来说，每个结点的单链表内只需要存储与这个结点有关的边对应的另一个点在数组中的数组下标，即每个边会在两个顶点里共存储两次

对于有向图来说，在单链表里存储的是从该结点流出的弧流向的顶点，即单链表的长度就是这个顶点的出度，如果有便捷的求入度的需求，可以建立逆邻接表

typedef struct ArcNode{
    int vex; // 这个弧或者边指向的顶点的位置
    struct ArcNode *link; // 链表下一个元素即本顶点引出/关联的下一个弧/边的地址
    InfoTypr *info; // 边/弧相关信息的指针，比如权值等
}ArcNode;
typedef struct VNode{
    VertexType data; // 顶点的信息
    ArcNode *firstarc; // 指向第一条弧/边的指针
}VNode;
typedef struct{
    VNode arc[MAXSIZE]; // 存所有顶点
    int vexnum , arcnum; // 顶点数和边数
    int kind; // 表示图是有向图还是无向图
}Graph

2.3 有向图的十字链表存储表示

和邻接表大致的思路一样，不同之处在于对每个顶点建两个单链表，流出去的一个，流入的一个，但是其结构如下：

// 弧结构
typedef struct ArcBox{
    int tailvex,headvex; // 弧尾顶点和弧头顶点的数组下标
    InfoType *info; // 边上的信息，如权值
    struct ArcBox *hlink,*tlink;// 指向弧头相同的下一个弧、弧尾相同的下一个弧
}ArcBox;
// 顶点结构
typedef struct VexNode{
    VertexType data; // 顶点包含的信息
    ArcBox *firstin,*firstout; // 指向流出链表、流入链表
}VexNode;

这样就实现了弧虽然在firstin和firstout两个单链表里，但是却存了一次

可以结合着图理解一下

2.4 无向图的邻接多重表存储表示

每个顶点建一个单链表，与该顶点关联的边建一个单链表

typedef strust Ebox{
    int mark; // 边权值
    int ivex , jvex; //这个边关联的两个顶点
    struct EBox *ilink,*jlink; // 分别表示结点i、j关联的下一个边 
}EBox;

一维数组保存每个顶点的信息和相应单链表的头指针

结合图理解

3 图的遍历

3.1 深搜(DFS)

基本思想：

• 初始时标记所有顶点都没有访问
• 从某个没有被访问的顶点v出发，访问这个顶点，然后依次从v的所有没有被访问的邻接点出发递归深度优先搜索遍历图，直到图中所有和v有路径相通的顶点都被访问
• 如果还存在没有被访问的顶点，则从中选择一点作为出发点，重复以上过程，直至所有的顶点都被访问到

有点类似树的先序遍历，用通俗一些的语言说就是：一直往下走，走不通回头，换条路再走，直到无路可走

访问时经过的顶点和边构成的子图叫做深度优先搜索生成树，若用了多个出发点做深搜，则会产生多棵深度优先搜索生成树，构成一个深度优先搜索的生成森林

深搜可以用于判断无向图是否连通，若从无向图中任意一点出发能访问到图中的所有顶点，则它为连通图

可以用于判断有向图是否强连通，若从有向图每个点出发能访问到图中的所有顶点，则强联通

这是DFS的框图，可以用图理解一下

3.2 广搜(BFS)

• 初始时图中所有顶点均为未被访问
• 从图中的某个未访问顶点$v_{0}$出发，并在访问此顶点之后依次访问$v_{0}$的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的未访问过的邻接点，直至图中所有和$v_{0}$有路径相通的顶点都被访问到
• 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止

广搜有点类似树的层次遍历

广搜同样拥有广度优先搜索生成树和广度优先搜索生成森林

---

深搜一般用栈实现(递归其实是系统里有隐式的栈)，广搜一般用队列实现

4 图的连通性问题

若从无向图中任一点出发采用深搜或者广搜能访问到图中所有顶点，则该图为连通图，否则为非连通图，对连通图：深搜或广搜访问过的顶点和边构成的子图称为深度优先搜索生成树或者广度优先搜索生成树，对非连通图就是上面说过的深度优先搜索生成森林和广度的

4.1 生成树

假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称这个极小连通子图是这个连通图的生成树，对于非连通图，各个连通分量的生成树构成的集合是这个非连通图的生成森林

生成树不唯一，若为带权图，带权图的生成树上的各边权的和是这棵树的代价，最小代价的生成树是各边权值的总和最小的生成树，即最小生成树，当然它也是不唯一的

最小生成树的用处，比如建立一个铁路网把十个城市连接在一起，边的权值是这一段铁路造价，那么如果想让总的造价最低，实际上就是寻找这个网络的最小生成树，使得这个它代价最小而且还是连通的

构建最小生成树的算法：

• Prim 普里姆算法
• Kruskal 克鲁斯卡尔算法

4.1.1 Prim算法

给一个连通网$G=(V,E)$，它的生成树是$T(U,TE)$，TE是边的集合

操作步骤：

1. 令$U=\left\{ u_{0}|u_{0}\in V \right\},TE=\left\{ \right\}$
2. 在所有$u\in U,v\in V-U$的边$(u,v)\in E$里选一条权值最小的边并入集合$TE$,$v_{0}$并入U
3. 重复上一步，直到所有的点被添加完毕

此时T为G的最小生成树

#define MAX 100
#define MAXEDGE 1000000
typedef struct{
    int arcs[MAX][MAX]; // 邻接矩阵
    int vexnum,arcnum; // 顶点数和边数
}AGraphs;
typedef struct{
    int adjvex; // 最低权值的边来自的顶点
    int lowcost; // 权值
}EdgeType;
// 找出未加入最小生成树的顶点中距离最小生成树最近的哪个
int minclosedge(EdgeType closedge[]){
    int min,j,k;
    min = MAXEDGE; // 赋值一个类似INF的大值用于比较
    k = -1; // 找出的顶点的下标
    for(j = 0;j < G.vexnum;j++){
        if(closedge[j].lowcost != 0 && closedge[j].lowcost < min){
            // 如果j没有加入最小生成树，且其距离最小生成树距离比min小
            min = closedge[j].lowcost; // min替换为j的距离
            k = j; // 下标替换
        }
    }
    return k; // 最后返回找到的最近的顶点
}
void prim(AGraphs G, int u){ // G是待生成最小生成树的图，u是最小生成树第一个顶点
    int i,j,k; // 循环变量
    EdgeType closedge[MAX]; // 维护当前未加入最小生成树的顶点距离最小生成树最近的边
    for(j = 0;j < G.vexnum;j++){
        closedge[j].adjvex = u; // 初始最小生成树只有一个点所以最短边来源绝对是u
        closedge[j].lowcost = G.arcs[u][j]; // 最短权值就是和u之间的边，没有就是无穷
    }
    closedgep[u].lowcost = 0; // u已经加入最小生成树，最小权值标记为0
    for(i = 1;i < G.vexnum;i++){
        k = minclosedge(closedge) // 找出最近顶点
        closedge[k].lowcost = 0; // k加入最小生成树，lowcost设为0
        for(j = 0;j < G.venum;j++){
            if(G.arcs[k][j] < closedge[j].lowcost){
                // 如果新加入最小生成树的点距离j比之前的最小还要小
                closedge[j].lowcost = G.arcs[k][k]; // 更新最小权值边
                closedge[j].adjvex = k;
            }
        }
    }
}

它的时间复杂度是$O(n^{2})$，适合用于稠密图

4.1.2 克鲁斯卡尔算法

设$G=(V,E)$，T为G的最小生成树，初态$T=(V,\left\{ \right\})$

步骤：

按照边的权值从小到大的顺序，考察G的边集中的各条边，若被考察的边的两个顶点属于T的两个不同的连通分量，则把这个边作为最小生成树的边加入到T中，同时把两个连通分量连接为同一个连通分量，若被考察的边的两个顶点属于一个连通分量，则舍去这个边，如此下去当T的连通分量个数为1的时候，这个连通分量就是最小生成树

克鲁斯卡尔算法适合稀疏图，时间复杂度为$O(e\log e)$，e为图的边数，因为这个算法要对边按照权值排序，如果使用堆、快速、归并排序算法，则平均时间复杂度就是$O(e\log e)$

5 有向无环图及其应用

5.1 AOV网

AOV网可以代表一项工程，工程划分为若干个活动(顶点)，每个活动用一个顶点表示，活动之间的先后顺序通过弧表示，我们需要干的事是：

• 要测试一个网是否包含回路，即是不是个AOV网
• 要进行拓扑排序，安排活动的进行顺序

测试网是否具有回路的方法，就是在网的偏序集合下构造一个线性序列，有如下性质

• 若顶点i优先于j，则在线性序列中i仍然优先于j
• 对于网中原来没有优先关系的顶点i和顶点j，在线性序列中也建立一个先后关系，要么i优先j，要么j优先i

满足上述性质的线性序列称为拓扑有序序列，构造这样的序列的过程称为拓扑排序

5.1.1 拓扑排序

步骤：

1. 在网中选择一个入度为0的顶点，输出到序列中
2. 删除这个顶点和由它出发的所有边
3. 重复1和2，直到所有顶点输出或者不存在其他入度为0的顶点
4. 如果最终图中有剩余顶点未被删除，说明图中有回路，不是一个AOV网

时间复杂度为$O(n+e)$

5.2 AOE网

AOE网可以表示一项工程，顶点表示事件，弧表示活动，弧上的权值表示完成这项活动需要的时间，只有在某个顶点代表的事件发生之后，从这个顶点发出去的弧代表的各个活动才能开始，只有进入某个顶点的每个弧都已经结束，这个顶点代表的事件才能发生
需要研究的问题：

• 完成整个工程至少需要多少时间
• 哪些活动是影响工程进度的关键

某些活动可以并行进行，完成的最短时间就是从开始顶点到完成顶点的最长路径长度，路径长度最长的路径叫做关键路径，关键路径上所有的活动都叫做关键活动

6 最短路

给定n个城市和这些城市之间的公路的距离，能否找到城市A到城市B之间一条最近的通路，有两种形式：

• 单源最短路：已知起始顶点，求它到其他顶点的最短路，例如Dijkstra(迪杰斯特拉) 算法
• 确定终点的最短路：已知终结结点，求其他结点到这个结点的最短路径，在无向图中这个问题和单源最短路一模一样，在有向图中相当于把所有弧的方向反向之后求单源最短路
• 确定起点和终点的最短路径
• 全局最短路径：求图中所有的最短路径，比如Floyd-Warshall算法

6.1 迪杰斯特拉算法

按路径长度递增的顺序产生最短路径(是的贪心又来了)

设图$G=(V,E),V=\left\{ v_{0},v_{1},\dots,v_{n-1} \right\}$，设源点为$v_{0}$，求其到其余各个点的最短路径

基本思想：设集合S中存放已找到最短路径的顶点，集合$T=V-S$存放当前还未找到最短路径的顶点

1. 初态是S中只包含源点$v_{0}$，$v_{0}$到其余各点的弧为各点当前各点的最短路径，如果没有弧就是无穷
2. 从T中选取当前各点的”最短”路径长度中最短的顶点u加入到S中
3. 加入新的顶点u之后，考察顶点$v_{0}$到T中的剩余顶点的最短路径长度是否可以优化更新
4. 重复2，3直到顶点全部加入S中，或者源点到剩余顶点路径都是无穷为止

只适用于静态网络，不能有负边权

void ShortestPath(AGraphs G,int k,int P[][],int D[]){
    // G是对应的图，k是源点下标，P[i][j]是j在不在源点到i的最短路上，D[i]存储最短路长度
    int i,w,j,min,final[MAXNUM]; // final标记第i个顶点是否被求过了最短路径
    for(i = 0;i < G.vexnum;i++){
        final[i] = 0; // 初始化所有结点都未求最短路
        D[i]=G.arcs[k][i]; // 初始的最短路就是源点到各点的距离
        for(w = 0;w < G.vexnum;w++){
            P[i][w] = 0; // 初始化所有结点都不在源点到i的最短路上
        }
        if(D[i]<INFINITY){ // 如果源点到i有弧
            P[i][k] = 1; // 源点当然在源点到i的最短路上
            P[i][i] = 1; // i自己当然在源点到i的最短路上
        }
    }
    D[k] = 0; // 源点到自己的最短路为0
    final[k] = 1 // 源点自己当然被求过最短路径
    for(i = 1;i < G.vexnum;i++){// 除了源点，需要遍历n-1次
        min = INFINITY;
        for(w = 0;i < G.vexnum;w++){// 遍历所有顶点
            if(!final[w] && D[w] < min){ // 如果w没有被求过最短路而且它现在存储的最短路径小于min
                j=w;
                min=D[w];// 替换
            }
        }
        if(min == INFINITY)
            return; // 没有被求过最短路的顶点，全部都没有连接了，结束
        final[j] = 1; // 标记j被求过最短路
        // 开始根据新的加入被求过最短路的点，更新D
        for(w = 0;w < G.vexnum;w++){// 遍历所有点
            if(!final[w] && (min+G.arcs[j][w] < D[w])){
                // 如果w没被求过，而且通过从源点到j再到w的方式比原来w的最短路还短
                D[w] = min + G.arcs[j][w]; // 更新
                P[w] = P[j]; // 原来在源点到j的最短路的结点现在肯定也在源点到w上
                P[w][w] = 1; // 自己在源点到自己的最短路上
            }
        }
    }
}

时间复杂度为$O(n^{2})$

6.2 弗洛伊德算法

求每一对顶点之间的最短路

弗洛伊德算法定义了两个二维矩阵：

1. 矩阵D记录顶点间的最小路径
   例如D[0][3]= 10，说明顶点0到 3的最短路径为10
2. 矩阵P记录顶点间最小路径中的中转点
   例如P[0][3]= 1 说明，0 到 3的最短路径轨迹为：0 -> 1 -> 3。

它通过3重循环，k为中转点，v为起点，w为终点，循环比较D[v][w] 和 D[v][k] + D[k][w]的最小值，如果D[v][k] + D[k][w] 为更小值，则把D[v][k] + D[k][w] 覆盖保存在D[v][w]中

void floyd(int D[][],int p[][],AGraph G){
    int i,j,k;
    for(i = 0;i < G.vexnum;i++){
        for(j = 0;j < G.vexnum;j++){
            D[i][j] = G.arcs[i][j]; // 初始时最小路径就是两顶点之间弧，无弧则无穷
            p[i][j] = j; // 初始化i到j经过j点
        }
    }
    //中间点 -> 外层必须是中间点，因为是对于每个中间点，更新起始点和终止点的距离 
    for(k = 0 ; k < G.vexnum ; k++){
        //起始点
        for(i = 0 ; i < G.vexnum ; i++){
            if(D[i][k] == INFINITY) continue; // 起始点不可达中间点，跳过
            //终止点
            for(j = 0 ; j < G.vexnum ; j++){
                if(D[i][j] > (D[i][k] + D[k][j])){
                    // 经过中间点之后比之前的路径更优
                    D[i][j] = D[i][k] + D[k][j]; // 替换
                    p[i][j] = p[i][k]
                }
            }
        }
    }
}

该算法本质是动态规划的思想，递推的一步一步推出最优解