图的定义与基本术语
图：G=(V, E)
V: 顶点(数据元素)的有穷非空集合
E: 边的有穷集合有向图和无向图：前者边有方向，后者边无方向
 
完全图：任意两个点都有一条边相连
- 无向完全图：一张图中每条边都是无方向的；在无向完全图中；在无向完全图中：n个顶点，有n(n-1)/2条边
- 有向完全图：图中各边都有方向，且每两个顶点之间都有两条方向相反的边连接的图；在有向完全图中：n个顶点，有n(n-1)条边
稀疏图：有很少的边或弧的图 （e < nlogn）
稠密图：有较多边或弧
网：边/弧带权的图
邻接：有边/弧相连的两个顶点之间的关系 ()无向图，无先后关系；<>有向图，有先后关系
- 存在(V，V)，则称V和V互为邻接点
- 存在
关联(依附)：边/弧与顶点之间的关系。
- 存在(V，V)/
- 存在(V，V)/
顶点的度：与该顶点相关联的边的数目，记为TD(v)
在有向图中，顶点的度等于该顶点的入度与出度之和
- 入度：以当前顶点为终点的有向边的条数,记作ID(v)
- 出度：以当前顶点为始点的有向边的条数，记作OD(v)
当有向图中仅有一个顶点的入度为0，其余顶点的入度均为1(出度任意)，则该图为树形，称为有向树
路径：接续的边构成的顶点序列
路径长度：路径上边或弧的数目/权值之和 (有权值按权值算)
回路(环)：第一个顶点和最后一个顶点相同的路径
简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径
简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径
连通图(强连通图)：在无(有)向图G = (V, {E})中，若对任意两个顶点v, u都存在从v到u的路径，则称G是连通图(强连通图)。无向图称为连通图，有向图称为强连通图
权与网
- 权：图中边或弧具有的相关树称为权，表明从一个顶点到另一个顶点的距离或耗费
- 网：带权的图称为网
子图
设有两个图G = (V, {E}), G1 = (V1, {E1}), 若V1∈V，E1∈E，则称G1是G的子图 (即顶点和边都是图的子集)
连通分量 (强连通分量)
连通分量：无向图G的极大连通子图称为G的连通分量
- 极大连通子图：该子图是G的连通子图D，将G中任何一个不在D中的顶点加入，子图不再连通的，则该子图称为极大连通子图
强连通分量：有向图G的极大连通子图称为G的强连通分量
- 极大连通子图：该子图是G的连通子图D，将G中任何一个不在D中的顶点加入，子图不再连通的，则该子图称为极大连通子图
单顶点就是强连通分量
- 极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，该子图不再连通
- 生成树：包含无向图G所有顶点的极小连通子图
- 生成森林：对非连通图，由各个连通分量的生成树的集合
小世界理论
你和任何一个陌生人之间所间隔的人不会超过五个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”根据这个理论，你和世界上的任何一个人之间只隔着五个人，不管对方在哪个国家，属哪类人种，是哪种肤色。
将小世界理论的人际关系网络抽象成一个无向图G，用图G中的一个顶点表示一个人，两个人认识与否用代表这两个人的顶点之间是否有一条边来表示。从任一顶点出发用广度优先对图进行遍历，统计所有长度不超过7的顶点
图的存储结构
图的逻辑结构：多对多
邻接矩阵：借助二维数组来表示图的元素间的关系
链式存储结构：由于图中顶点多对多的特性，很难确定需要多少个指针域，因此有如下几个常用的链式存储方式：邻接表，邻接多重表，十字链表
1.邻接矩阵
1.1无向图的邻接矩阵
建立一个顶点表(记录各个顶点信息) 和一个邻接矩阵表(表示各个顶点之间的关系)
设图 A = (V, E)有 n 个顶点，则顶点表表示为：
图的邻接矩阵表是一个二维数组 A.arcs[n][n], 定义为
如果存在一条边 属于A中的边，则存在该边，记为1 (自身与自身无边)
eg：
PS: “邻接”，相邻且相接
1.特点：无向图的邻接矩阵是对称矩阵，且对角线上元素为0，因为当有一个顶点到另一个顶点存在边时，另一个顶点到该顶点也一定存在一条边
2.统计某一个顶点的度是多少只需遍历该顶点对应的数组，计算1的次数即可，即顶点 i 的度 = 第i行(列)中 1 的个数
3.特别的：无向完全图的邻接矩阵中，对角元素为0，其余均为1
1.2有向图的邻接矩阵
有向图存在方向，因此只有当存在当前顶点发出的弧时，才记为1 (和无向图的邻接矩阵一样，自身与自身无弧)
在有向图的邻接矩阵中：
- 第 i 行：表示以结点V为尾的弧(即出度边)
- 第 i 列：表示以结点V为头的弧(即入度边)
1.有向图的邻接矩阵的特点：对角线元素为0，但不一定是对称矩阵
2.对有向图的邻接矩阵而言：
- 顶点 i 的出度 = 第 i 行的元素之和
- 顶点 i 的入度 = 第 i 列的元素之和
- 顶点 i 的度 = 第 i 行元素之和 + 第 i 列元素之和
3.特别的：有向完全图的对角线元素全0，取余元素全1
1.3网的邻接矩阵
网即有权图
网的邻接矩阵定义为：
如果存在边 / 弧属于VR图，则邻接矩阵记录该条边的权值W；否则记录INF
1.3.1有向网的邻接矩阵
1.4 无向网的存储结构
两个数组 ：顶点表和邻接矩阵
//最大顶点数#define MAX_VEX_NUM 100//假的无穷大，填补邻接矩阵中没有邻接关系的点#define MAX_INT 2147483647typedef struct Graph{//顶点表顶点数据类型 vexs[MAX_VEX_NUM];//邻接矩阵表边的类型 arcs[MAX_VEX_NUM][MAX_VEN_NUM];//顶点数和边数int vexNum, arcNum;}AMGraph;
1.4.1采用邻接矩阵创建无向网
- 输入总顶点数和总边数
- 依次输入顶点的信息存入顶点表
- 初始化邻接矩阵，因为是在网当中，所以使每个权值初始化为最大值
- 构造邻接矩阵
1.4.1.1实现
构造
void creatGraph(AMGraph* graph){printf("请输入顶点数和边数：");//1.顶点数和边数scanf("%d %d", &(graph->vexNum), &(graph->arcNum));setbuf(stdin, NULL);putchar('\n');//顶点数据for (int i = 0; i < graph->vexNum; i++){printf("请输入第%d个顶点数据：", i + 1);scanf("%c", &(graph->vexs[i]));setbuf(stdin, NULL);putchar('\n');}//3.初始化边, n个顶点就有for (int i = 0; i < graph->vexNum; i++){for (int j = 0; j < graph->vexNum; j++){if(i!=j)graph->arcs[i][j] = MAX_INT;elsegraph->arcs[i][j] = 0;}}//4.构造邻接矩阵for (int i = 0; i < graph->arcNum; i++){char v1, v2;int weight;printf("请输入第%d条边依附的顶点及权值：", i+1);scanf("%c %c %d", &v1, &v2, &weight);setbuf(stdin, NULL);putchar('\n');//找到边依附的两个顶点，记录下标，就是在邻接矩阵中的位置int i = findVex(graph, v1);int j = findVex(graph, v2);//如果没查找到顶点或该顶点已经有依附的边if (i == -1 || j == -1 || graph->arcs[i][j] != MAX_INT){printf("不存在该顶点或该顶点已有依附的边\n");exit(-1);}//对称赋值graph->arcs[i][j] = weight;graph->arcs[j][i] = weight;}}
查找顶点是否存在
int findVex(AMGraph* graph, char vex){for (int i = 0; i < graph->vexNum; i++){if (vex == graph->vexs[i]){return i;}}return -1;}
1.4.2邻接矩阵创建无向图和有向网
无向图：和无向网区别就是无向图的边不存在权值，因此初始化邻接矩阵时边均为0，构造邻接矩阵时，存在的边为1
有向网：有向网的邻接矩阵不一定时对称矩阵，因此仅需为graph->arcs[i][j]赋值，而不需要在对称元素上赋值
邻接矩阵不便于增加和删除顶点；当边数较少时比较浪费空间
2.邻接表
2.1无向图的邻接表
顶点：按编号顺序将顶点存放在一维数组中，一维数组中每个元素都有指针域和数据域
边：用链表存储关联了同一顶点的所有边；每个结点有两个数据
adjvex为邻接顶点，nextarc为下一条边；eg：
代表v有两条边，分别邻接的是在顶点数组中下标为3的顶点和下标为1的顶点
当为无向网时，可以给表结点增加数据域以存放权值
无向图邻接表的特点：
- 邻接表不唯一，关联了同一顶点的边在链表中的位置可以任意
- 每一条边会在一个邻接表中出现2次，因此在无向图的邻接表当中，若有 n 个顶点，e 条边， 则其邻接表需要 n 个头结点和 2e 个表结点
- 用邻接表表示的无向图中顶点v的度为第 i 个单链表中的结点数
2.1.1实现
实现步骤：
- 输入顶点数和边数
- 建立顶点表，依次输入顶点数据，并初始化顶点表中每个顶点的指针域为NULL
创建临邻接表
- 依次输入每条边依附的两个顶点( 起点，终点 )
- 确定两个顶点的下标 i 和 j ，建立两个边结点，一个结点的head存放起点的下标，另一个存放终点的下标
- 将存放起点下标的边结点链接到对应的终点顶点上，存放终点下标的边结点链接到对应的起点顶点上
- 结构
//边结构typedef struct GraphNode{int head;struct GraphNode* nextArc;}gNode;//顶点表typedef struct Head{char data;gNode* firstArc;}head;//图的基本结构typedef struct ALGraph{head gHead[MAX_VEX];int vexNum, arcNum; //顶点数和边数}ALgraph;
- 构造
void creatGraph(ALgraph* graph){printf("请输入顶点数和边数: ");scanf("%d %d", &(graph->vexNum), &(graph->arcNum));setbuf(stdin, NULL);putchar('\n');//顶点赋值for (int i = 0; i < graph->vexNum; i++){char c;printf("请输入第%d个顶点的数据：", i+1);scanf("%c", &c);graph->gHead[i].data = c;graph->gHead[i].firstArc = NULL;setbuf(stdin, NULL);putchar('\n');}//边结点链接for (int i = 0; i < graph->arcNum; i++){char v1, v2;printf("请输入第%d条边依附的结点：", i + 1);scanf("%c %c", &v1, &v2);setbuf(stdin, NULL);int i = indexOfVex(graph, v1);int j = indexOfVex(graph, v2);//生成两个结点，因为一条边会关联两个顶点，两个顶点都会链接上这条边//只是不同顶点对应的边结点的head值不一样gNode* g = (gNode*)malloc(sizeof(gNode));g->head = j;g->nextArc = NULL;gNode* g2 = (gNode*)malloc(sizeof(gNode));g2->head = i;g2->nextArc = NULL;/*头插，在对应的关联边链表中进行插入如果用尾插法，需要记录上一次的尾结点，但上一次的尾指针所指向的边结点不一定就在当次循环中找到的顶点的边链表当中例如:1. a b a-->1 b-->0 pre-->12. b c b-->0 b由于在上次时已经有长子了而pre此时还是指向a的长子1,pre-->next = g的话，就会变成 a-->1-->2 b-->0，这显然不是我们想要的*///链接到对应顶点，存终点下标的链接到起点顶点，存起点下标的链接到终点顶点g->nextArc = graph->gHead[i].firstArc;graph->gHead[i].firstArc = g;g2->nextArc = graph->gHead[j].firstArc;graph->gHead[j].firstArc = g2;}}
2.2有向图的邻接表
有向图的邻接表创建与无向图的邻接表创建区别仅在于：在构造有向图时，由于弧是有方向的，因此只需构造一条出度边依附在出度点上即可，该边的邻接点域值head存储入度点的下标；而在无向图中每条边需要保存两次；因此邻接表表示的无向图空间复杂度记为O(n+2e)，邻接表表示的有向图空间复杂度为O(n+e)
2.2.1实现
void creatGraph(ALgraph* graph){printf("请输入顶点数和边数: ");scanf("%d %d", &(graph->vexNum), &(graph->arcNum));setbuf(stdin, NULL);putchar('\n');//顶点赋值for (int i = 0; i < graph->vexNum; i++){char c;printf("请输入第%d个顶点的数据：", i+1);scanf("%c", &c);graph->gHead[i].data = c;graph->gHead[i].firstArc = NULL;setbuf(stdin, NULL);putchar('\n');}//边结点链接for (int i = 0; i < graph->arcNum; i++){char v1, v2;printf("请输入第%d条边依附的结点：", i + 1);scanf("%c %c", &v1, &v2);setbuf(stdin, NULL);int i = indexOfVex(graph, v1); //记为出度点int j = indexOfVex(graph, v2); //记为入度点//生成两个结点，因为一条边会关联两个顶点，两个顶点都会链接上这条边//只是不同顶点对应的边结点的head值不一样gNode* g = (gNode*)malloc(sizeof(gNode));g->head = j; //存储终点顶点的下标g->nextArc = NULL;g->nextArc = graph->gHead[i].firstArc;graph->gHead[i].firstArc = g;}}
邻接表特点：
- 顶点V的出度为第 i 个单链表中的结点个数
- 顶点V的入度为整个单链表中邻接点域值为 i-1 的结点个数
根据出度和入度两个角度，我们可以得到两种邻接表
第一个邻接表根据出度建立，第二个逆邻接表根据入度建立，逆邻接表在代码上只是修改边的邻接点域值为终点下标，修改插入结点位置为入度点
逆邻接表特点：
- 顶点V的入度为第 i 个单链表中的结点个数
- 顶点V的出度为整个单链表中邻接点域值为 i-1 的结点个数
和邻接表特点刚好相反
2.3邻接表的特点
方便找任一顶点的所有邻接点
节约稀疏图的空间
- 无向图中需要N个头指针和2E个边结点(每个结点至少两个域)
- 有向图中需要N个头指针和E个边结点
度的计算
- 对于无向图，任意顶点的度都便于计算
- 对于无向图：邻接表适用于计算出度；逆邻接表适合计算入度
- 不方便检查任意一堆顶点间是否存在边
2.3.1 邻接矩阵和邻接表的关系
- 联系：邻接表中每个链表对应邻接矩阵中的一行，链表中结点个数等于一行中非零元素个数
区别
- 对于任一确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表不唯一(链接次序与顶点编号无关)
- 邻接矩阵的空间复杂度为O(N)，而邻接表的空间复杂度为O(n+e) 或 O(n+2e)
- 用途：邻接矩阵多用于稠密图；邻接表多用于稀疏图
3.十字链表
十字链表可以看成将有向图的邻接表和逆邻接表结合起来形成的一种链表
有向图中的每一条弧对应十字链表中的一个弧结点；同时有向图中的每个顶点在十字链表中对应一个结点，叫做顶点结点
邻接表存储有向图时存在求结点的度困难的缺点，十字链表可以弥补这一缺点，即每个结点不仅记录出度链表，也记录入度链表
3.1实现
//顶点表，现在每个顶点既要存储出度边，也要存储入度边typedef struct Head{char data;gNode* outPut;gNode* inPut;}head;//生成两个结点，一个对i而言是出度，对j而言是入度gNode* g = (gNode*)malloc(sizeof(gNode));g->head = i;g->nextArc = NULL;gNode* g2 = (gNode*)malloc(sizeof(gNode));g2->head = j;g2->nextArc = NULL;if (i != -1 && j != -1){//链接对j而言的入度链表g->nextArc = graph->gHead[j].inPut;graph->gHead[j].inPut = g;//链接对i而言的出度链表,i的出度边即是j的入度边g2->nextArc = graph->gHead[i].outPut;graph->gHead[i].outPut = g2;}
this 方法需要2倍空间，因此尝试下面这种方法
//边结构typedef struct GraphNode{int head; //弧头int tail; //弧尾struct GraphNode* inArc;struct GraphNode* outArc;}gNode;//顶点表typedef struct Head{char data;gNode* outPut; //出度链表gNode* inPut; //入度链表}head;//邻接表基本信息typedef struct ALGraph{head gHead[MAX_VEX];int vexNum, arcNum; //顶点数和边数}ALgraph;/*创建*/void creatGraph(ALgraph* graph){printf("请输入顶点数和边数: ");scanf("%d %d", &(graph->vexNum), &(graph->arcNum));setbuf(stdin, NULL);putchar('\n');//顶点赋值for (int i = 0; i < graph->vexNum; i++){char c;printf("请输入第%d个顶点的数据：", i + 1);scanf("%c", &c);graph->gHead[i].data = c;graph->gHead[i].outPut = NULL;graph->gHead[i].inPut = NULL;setbuf(stdin, NULL);putchar('\n');}//边结点链接for (int i = 0; i < graph->arcNum; i++){char v1, v2;printf("请输入第%d条边依附的结点：", i + 1);scanf("%c %c", &v1, &v2);setbuf(stdin, NULL);int i = indexOfVex(graph, v1);int j = indexOfVex(graph, v2);//生成两个结点，一个对i而言是出度，对j而言是入度gNode* g = (gNode*)malloc(sizeof(gNode));g->head = i;g->tail = j;g->inArc = NULL;g->outArc = NULL;if (i != -1 && j != -1){g->inArc = graph->gHead[j].inPut;graph->gHead[j].inPut = g;//i的出度边即是j的入度边，于是对于g而言只是链接的位置不同罢了g->outArc = graph->gHead[i].outPut;graph->gHead[i].outPut = g;}}}/*遍历*/void printGraph(ALgraph* graph){for (int i = 0; i < graph->vexNum; i++){printf("%c: ", graph->gHead[i].data);gNode* g = graph->gHead[i].outPut;printf("出度边：");while (g){printf("弧头：%d--> 弧尾：%d", g->head, g->tail);g = g->outArc;}putchar(' ');gNode* g2 = graph->gHead[i].inPut;printf("入度边：");while (g2){printf("弧头：%d--> 弧尾：%d", g2->head, g2->tail);g2 = g2->inArc;}putchar('\n');}}
4.邻接多重表
邻接表存储无向图的缺点是每条边都要存储两遍，因此在进行删除操作时需要找到两个结点来进行删除，邻接多重表可以解决这个问题
实现也很简单，只需要在边结点增加一个数据域指明头尾，在增加边结点时让尾顶点也指向对应边结点，以及设置访问标记，表明在第i个顶点时
4.1实现
//边结构typedef struct GraphNode{int head;int tail;struct GraphNode* tailNext;struct GraphNode* nextArc;}gNode;//顶点表typedef struct Head{char data;gNode* firstArc;}head;//邻接表基本信息typedef struct ALGraph{head gHead[MAX_VEX];int vexNum, arcNum; //顶点数和边数}ALgraph;void creatGraph(ALgraph* graph){printf("请输入顶点数和边数: ");scanf("%d %d", &(graph->vexNum), &(graph->arcNum));setbuf(stdin, NULL);putchar('\n');//顶点赋值for (int i = 0; i < graph->vexNum; i++){char c;printf("请输入第%d个顶点的数据：", i + 1);scanf("%c", &c);graph->gHead[i].data = c;graph->gHead[i].firstArc = NULL;setbuf(stdin, NULL);putchar('\n');}//边结点链接for (int i = 0; i < graph->arcNum; i++){char v1, v2;printf("请输入第%d条边依附的结点：", i + 1);scanf("%c %c", &v1, &v2);setbuf(stdin, NULL);int i = indexOfVex(graph, v1);int j = indexOfVex(graph, v2);//生成两个结点，因为一条边会关联两个顶点，两个顶点都会链接上这条边//只是不同顶点对应的边结点的head值不一样gNode* g = (gNode*)malloc(sizeof(gNode));g->head = i;g->tail = j;g->nextArc = NULL; //vig->tailNext = NULL; //vjif (i != -1 && j != -1){//让头尾顶点关联一条边结点，头尾顶点需要用边结点中不同的指针域来指向，以方便遍历g->nextArc = graph->gHead[i].firstArc;graph->gHead[i].firstArc = g;g->tailNext = graph->gHead[j].firstArc;graph->gHead[j].firstArc = g;}}}
邻接多重表的遍历
void printGraph(ALgraph* graph){for (int i = 0; i < graph->vexNum; i++){printf("%c: ", graph->gHead[i].data);gNode* g = graph->gHead[i].firstArc;while (g){/*//如果顶点i是当前结点的起点, 说明tail是当前顶点的终点，输出相邻点int index = g->head == i ? g->tail : g->head;*/printf("起点：%d--->终点：%d ", g->head, g->tail);//如果顶点i是当前结点的起点，则沿着起点链表寻找；否则就是终点的链表，转到终点链表寻找g = g->head == i ? g->nextArc : g->tailNext;}putchar('\n');}}
图的遍历
- 从已给的连通图中某一顶点出发，沿着一些边访问图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，图的遍历是图的基本运算
遍历实质：找每个顶点的邻接点的过程
图的遍历特点：图中可能存在回路，且图中的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到曾经访问过的节点
- 解决办法：设置一个辅助数组 visited[i]，用来标记每个被访问过的顶点，数组初始状态为0，顶点i被访问后，置visited[i]为1，防止多次访问
图的常用遍历方法：
- 深度优先搜索 DFS
- 广度优先搜索 BFS
1.深度优先搜索
“一条路走到黑”，每次到一个新的顶点就找没有访问过的邻接点
过程：
- 在访问图中某一起始顶点v后，由v出发，访问它的任一邻接点 w
- 再从w出发，访问与w邻接但还未被访问过的顶点w
然后从w出发，进行类似上一步的过程…直到到达所有的邻接顶点都被访问过的顶点 u 为止
如果到达所有的邻接点都是被访问过的顶点 u，则回退一步，退到前一次刚访问过的顶点，判断是否还有其它没有被访问的邻接点
- 如果有，则访问此没有访问过的邻接点，之后再从此邻接点出发，继续进行访问
- 如果没有，则再次回退，进行判断。
- 重复上述过程，直到连通图中所有顶点都被访问过为止
由此过程可以看出用递归实现较为简单
连通图的深度优先遍历类似于树的先根遍历 (即二叉树的先序遍历)
1.1 邻接矩阵的深度优先遍历
邻接矩阵表示的无向图深度遍历实现：
实现：
int visited[MAX_VEX_SIZE]; //辅助数组void DFS(AMGraph* graph, int vex){visited[vex] = 1;printf("%c--->", graph->vexs[vex]);for (int i = 0; i < graph->vexNum; i++){//!flag[i]代表没有访问过//graph->arcs[vex]是顶点所在的行，graph->arcs[vex][i] != 0代表是该行所有为1(即邻接)的边，对应//的i即是与其邻接的顶点，对其进行访问if (graph->arcs[vex][i] != 0 && !visited[i]){DFS(graph, i);}}}
1.2 邻接表的深度优先遍历
邻接表表示的无向图深度遍历实现：
- 和邻接矩阵的差不多，就是需要移动指针鹅以
int flag[MAX_VEX]; //辅助数组void DFS(ALgraph* graph, int vex){flag[vex] = 1;printf("%c-->", graph->gHead[vex].data);gNode* g = graph->gHead[vex].firstArc;while (g){int i = g->head; //取出对vex而言的邻接点if (!flag[i]){DFS(graph, i); //如果还没有被访问过}g = g->nextArc; //访问下一条边, 找其对应邻接点}}
1.3 DFS算法效率分析
用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在的行，时间复杂度为O(n) （n个顶点，一个扫描n次）
用邻接表来表示图，虽然有2e个边结点，但只需扫描e个结点就可完成遍历，加上n个头结点的，时间复杂度为O(n+e)
所以：稠密图适用于在邻接矩阵上，进行深度遍历；稀疏图适用于在邻接表上，进行深度遍历
2. 广度优先搜索
从一个顶点开始，先访问其==所有的邻接点==
过程：
- 从图的某一顶点出发
- 首先依次访问该顶点的所有邻接点Vi，Vi … Vi，
- 再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点
- 重复此过程，直到所有顶点均被访问为止
2.1 邻接表的广度优先遍历
实现：
char que[MAX_VEX];int rear, pre;void BFS(ALgraph* graph, int vex){flag[vex] = 1;printf("%c-->", graph->gHead[vex].data);//下标入队que[rear++] = vex;while (rear!=pre){int j = que[pre++]; //取出顶点下标gNode* g = graph->gHead[j].firstArc; //取得顶点的第一个边结点//遍历当前顶点的所有边结点对应的邻接点, 对应置为1并入队while (g){if (!flag[g->head]){flag[g->head] = 1;printf("%c--->", graph->gHead[g->head].data);que[rear++] = g->head;}g = g->nextArc;}}}
ps：由于使用的是头插法，所以每一段都需要反着看
2.2 邻接矩阵的广度优先遍历
实现：
char que[MAX_VEX_SIZE];int rear, pre;void BFS(AMGraph* graph, int vex){visited[vex] = 1;printf("%c--->", graph->vexs[vex]);//入队下标que[rear++] = vex;//队列非空while (rear != pre){int x = que[pre++]; //队头顶点下标出队//入队x的邻接点for (int i = 0; i < graph->vexNum; i++){//存在邻接点并没有被访问if (graph->arcs[x][i] == 1 && !visited[i]){visited[i] = 1;printf("%c--->", graph->vexs[i]);que[rear++] = i;}}}}
2.3 BFS算法效率分析
- 如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的一行即n个元素，时间复杂度为O(N)
- 邻接表表示的无向图有2e个边结点，但只需扫描e个结点即可完成遍历，加上访问n个顶点时间，时间复杂度为O(n+e)
3. DFS与BFS算法效率比较
- 空间复杂度相同，都是O(n) （DFS使用了栈，BFS使用了队列）
- 时间复杂度==只与存储结构 (邻接矩阵或邻接表) 有关==，而与搜索路径无关
图的应用
1.最小生成树
生成树：所有顶点均由边连接在一起，但不存在回路的图
一个图可以有许多棵不同的生成树
所有生成树具有以下共同特点：
- 生成树的顶点个数与图的顶点个数相同
- 生成树是图的极小连通子图，去掉一条边则非连通
- 一个有n个顶点的连通图的生成树有n-1条边 (但含有n个顶点 n-1 条边的不一定就是生成树)
- 在生成树中再加一条边必然形成回路，不再是生成树
- 生成树中任意两个顶点间的路径是唯一的
1.1生成树
利用DFS生成的树称为深度优先生成树,，由DFS过程中经过的边和点构成；利用BFS生成的树称为广度优先生成树， 由BFS过程中经过的边和点构成
1.2最小生成树
最小生成树：如果给定一个无向网，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树
最小生成树的典型应用：
根据该问题可以建立如下模型
- 顶点：表示城市，n个
- 边：表示线路，n-1条
- 边的权值：表示线路的经济成本
- 连通网：表示n个城市间的通信网
1.2.1 MST性质
MST性质：设 N=(V, E) 是一个连通网，U 是顶点集 V 的一个非空子集。若边 (v, v)是一条具有最小权值的边，其中 v∈U，v属于V-U，则必存在一棵包含边 (v, v) 的最小生成树
在生成树构造的过程中，图中 n 个顶点分属两个集合：
- 已落在生成树上的顶点集：U
- 尚未落在生成树上的顶点集：V-U
接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边
1.2.2 Prim算法
算法思想：
- 设 N=(V, E) 是连通网，TE 是 N 上最小生成树中边的集合
- 初始令 U={u}，{u∈V}，TE={ } (空集)
- 在所有 u属于U，v∈V-U的边 (u，v)∈E中，找一条权值最小的边 (u, v)
- 将(u, v)并入集合TE，同时 v并入 U
- 重复上述操作直至 U=V 为止，则 T=(U，TE) 为 N的最小生成树
实现
void MST_Prim(AMGraph* graph){int min, j, k;int adjVex[MAX_VEX_SIZE]; //保存相关顶点下标int lowcost[MAX_VEX_SIZE]; //保存相关顶点间边的权值，已并入相关顶点的权值就是0lowcost[0] = 0; //初始化第一个权值为0，即v0加入生成树//lowcost[x]=0,代表x下标的顶点加入生成树adjVex[0] = 0; //第一个顶点v0加入,即假定从v0开始构造最小生成树//循环除下标为0外的全部顶点for (int i = 1; i < graph->vexNum; i++){lowcost[i] = graph->arcs[0][i]; //将v0顶点与之有边的权值存入数组，lowcost中的i //就对应了邻接点的下标，代表与Vi有边adjVex[i] = 0;}for (int i = 1; i < graph->vexNum; i++){min = 65535;j = 1;k = 0;while (j < graph->vexNum) //循环全部顶点{//如果权值不为0且小于minif (lowcost[j] && lowcost[j] < min){min = lowcost[j]; //让当前权值成为最小值k = j; //保存相邻且边cost为最小值的顶点的下标}j++;}printf("(%c %c)", graph->vexs[adjVex[k]], graph->vexs[k]); //输出当前顶点边中权值最小的边及其下标lowcost[k] = 0; //将当前顶点的权值设置为0，表示此顶点加入生成树for (int j = 1; j < graph->vexNum; j++){//若下标为k对应的顶点的各边权值小于此前这些顶点未被加入生成树的权值if(lowcost[j] && graph->arcs[k][j] < lowcost[j]){//保存权值，<=k的顶点都已经被并入了，所以能进来的一定是存在k+1位置//意义在于，前k个元素一定是访问了的！妙lowcost[j] = graph->arcs[k][j];//保存并入的顶点的下标adjVex[j] = k;}}}}
步骤解析：
创建两个一维数组 lowcost 和 adjVex， 长度都为最大顶点个数
adjVex[0] = 0的意思是我们从顶点V开始 (最小生成树从哪个顶点开始都可以，这里假定从V开始)；
lowcost[0] = 0 表示V并入最小生成树中，之后只要lowcost中的值被置为 0 就表示此下标的顶点被并入最小生成树第一个for循环的作用是：遍历邻接矩阵中的第一行数据 （即V的行），并将数值赋值给 lowcast，将adjVex全部初始化为0。初始化完成，下面开始生成
第二个for循环即构造最小生成树的操作
min设置为一个极大值，用来找到最小权值。j是用来做顶点遍历的。k用来保存最小权值的顶点的下标
while循环：lowcost[j]为0代表已经并入生成树，在循环中不断修改 min 的值为 lowcost 中的最小值，并用 k 保存此最小值的顶点的下标
在while循环结束后，k 表示与 adjVex[k] 邻接的顶点的下标，且两个顶点间权值为该行中最小的；并将 k 并入lowcost，表示已经加入生成树
第三个for循环：遍历第 k 行，查找各个权值，与 lowcost 中进行比较，若更小则修改 lowcost 的值，并将顶点下标 k 存入adjVex中
循环4-8，直到遍历完所有顶点
1.2.3 Kruskal算法
算法思想：
- 设连通网 N=(V，E)，令最小生成树初始状态为只有 n 个顶点而无边的非连通图 T=(V，{})，每个顶点自成一个连通分量
- 将权值进行排序，从最小的权值开始进行选取，若选取出来的边所依附的顶点落在 T 中不同的连通分量上 (即不能成环)，则将此边加入到 T 中；否则，舍去此边，选取下一条权值最小的边
- 重复2的选取(不用再进行排序)，直至 T 中所有顶点都在同一连通分量上为止
Kruskal算法所构造出来的最小生成树可能不唯一
实现
//边集合typedef struct Edge{int begin;int end;int weight;}edge;//权值排序void sort(edge* edges, AMGraph* graph){for (int i = 0; i < graph->arcNum; i++){for (int j = 0; j < graph->arcNum; j++){//交换权值 以及头和尾if (edges[i].weight < edges[j].weight){int temp;temp = edges[i].begin;edges[i].begin = edges[j].begin;edges[j].begin = temp;temp = edges[i].end;edges[i].end = edges[j].end;edges[j].end = temp;temp = edges[i].weight;edges[i].weight = edges[j].weight;edges[j].weight = temp;}}}printf("权排序之后的为:\n");for (int i = 0; i < graph->arcNum; i++){printf("(%c, %c) %d\n", graph->vexs[edges[i].begin], graph->vexs[edges[i].end], edges[i].weight);}}//arcVex是传入的边集合中的边的关联顶点int find(int* parent, int arcVex){//如果这个关联顶点>0, 说明已经存在于生成树中while (parent[arcVex] > 0){front = parent[arcVex];}return arcVex;}void MTS_Kruskal(AMGraph* graph){int n, m;int k = 0;edge edges[MAX_EDGE_SIZE]; //边集数组int parent[MAX_VEX_SIZE]; //定义数组用于判断是否形成环路//构建边集数组并排序for (int i = 0; i < graph->vexNum - 1; i++){for (int j = i + 1; j < graph->vexNum; j++){if (graph->arcs[i][j] < MAX_INT){edges[k].begin = i;edges[k].end = j;edges[k].weight = graph->arcs[i][j];k++;}}}sort(edges, graph);for (int i = 0; i < graph->vexNum; i++){parent[i] = 0; //初始化数组}printf("打印最小生成树");//遍历所有边for (int i = 0; i < graph->arcNum; i++){//获取边的关联顶点n = find(parent, edges[i].begin); //当前权值最小的边的头顶点m = find(parent, edges[i].end); //当前权值最小的边的尾顶点if (n != m) //如果n不等于m，说明没有产生回路{//妙！！！！parent[n] = m; //在parent中当前边的头顶点的下标处存入尾顶点的值，表示头顶点并入生成树集合//这样在下次find时对头顶点的查询就会返回尾顶点的值给n//如果头顶点有多条边邻接多个顶点，则会依次替换成对应尾顶点下标处存储//eg： edges[0] begin: 4 end:7 {0,0,0,0,7,0,0,0,0,0,0,0}// edges[1] begin: 4 end:8 这里就会根据4，返回内容7，在下标7处存储8// 成为: {0,0,0,0,7,0,0,8,0,0,0,0}//如果还有以4位头顶点的边，以此类推，有点类似于链表，只不过这里是 "下标指针" :)//parent[n] = m 表示Vn与Vm在同一个边集合中printf("(%c %c)", graph->vexs[edges[i].begin], graph->vexs[edges[i].end]);}}}
1.2.4算法对比
算法思想：
- Prim选择顶点
- Kruskal选择边
时间复杂度：
- Prim：O(n) n为顶点数
- Kruskal：O(eloge) e为边数
适用范围：
- Prim适用于稠密图 (边多，但复杂度与边无关)
- Kruskal适用于稀疏图
2.最短路径
典型应用：甲地到乙地是否有公路连通？如果有多条通路，哪一条最短？
公路网用有向网表示：
- 顶点：表示地点
- 弧：表示两个地点有路连通
- 权值：两地距离，交通费或图中所花费的时间
最短路径解决如何使一个地点到另一个地点的运输时间最短或运费最省的问题
最短路径问题的抽象：在有向网中 A点(源点) 到达 B 点(终点) 的多条路径中，寻找一条各边权值之和最小的路径，该路径即为最短路径
最短路径的两类问题：
- 两点间最短路径： 源点（起点）固定，任意终点，一般使用 Dijkstra 算法
- 单源点最短路径 ： 图中任意两点间的最短路径，一般使用 Floyd 算法
2.1 Dijkstra算法
Dijsktra算法并不是一下子求出源点到终点的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到结果
过程：
- 初始化：先找出从源点V到各终点V的直达路径(V，V)，即通过一条弧即可到达的其它顶点的路径
- 选择：从这些路径中找出一条长度最短的路径 (V，U)
- 更新：对其余各条路径进行调整—> 若图中存在弧(U，V)，且 (V，U) + (U，V) < (V，V)，则以路径 (V，U，V) 代替 (V， V)
Dijkstra：按照路径长度递增次序产生最短路径
步骤：
初始时令S = {V}，T = {其余顶点}
T中顶点对应的距离值用辅助数组 D 存放
D[i]初值：若存在
从 T 中选取一个其距离值最小的顶点V，加入S。对 T 中顶点的距离值进行修改：若加进 V 作中间顶点，从 V到 V 的距离值比不加 V 要长，则修改此距离值为要经过V的距离值
重复上述步骤，直到 S = V
实现
int pathArc[MAX_VEX_SIZE] = {-100}; //存储V0到各点的最短路径中每个顶点的下标int shortPathTable[MAX_VEX_SIZE] = {-100}; //存储V0到各点最短路径的权值和void Dijkstra(AMGraph* graph, int v0){int k, min;int finaly[MAX_VEX_SIZE]; // finaly[k] = 1，表示求得顶点V0到Vk的最短路径for (int i = 0; i < graph->vexNum; i++){finaly[i] = 0;shortPathTable[i] = graph->arcs[v0][i]; //初始化与V0有连线的顶点的权值pathArc[i] = -1; //初始化路径为-1}shortPathTable[v0] = 0; //v0至v0的路径为0finaly[v0] = 1; //v0到v0即是最短路径for (int i = 1; i < graph->vexNum; i++){min = MAX_INT; //初始化min为INFfor (int j = 0; j < graph->vexNum; j++) //寻找离V0最近的顶点{if (!finaly[j] && shortPathTable[j] < min){k = j;min = shortPathTable[j]; //j顶点离V0更近}}finaly[k] = 1; //将目前找到的V0最近的顶点置为1for (int i = 0; i < graph->vexNum; i++){//核心代码//如果经过中间顶点到达Vi比直接从V0到Vi更短，则更新if (!finaly[i] && (min + graph->arcs[k][i] < shortPathTable[i])){shortPathTable[i] = min + graph->arcs[k][i]; //修改最短路径长度为走中间顶点的这个pathArc[i] = k; // 下标i对应的顶点即是 k 的最短邻接点}}}}
2.2 Floyd算法
算法思想：
- 逐个顶点试探
- 从V到V的所有可能存在的路径中，选出一条最短的路径
步骤：
- 初始设置一个 n 阶矩阵 (n为顶点个数)，令其对角线元素为0，若存在弧
- 逐步尝试在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改；否则维持原值。所有顶点试探完毕后算法结束
可以总结为一个公式：
- D[V][W] = min{ D[V][W]，D[V][0]+D[0][W]}
D为试探顶点后的矩阵
实现
int pathMatirx[MAX_VEX_SIZE][MAX_VEX_SIZE]; //pathMatirx[V][W] 代表顶点V到W的中间顶点下标int shortPathTable[MAX_VEX_SIZE][MAX_VEX_SIZE]; //顶点间最短路径权值和void Floyd(AMGraph* graph){//初始化矩阵for (int vx = 0; vx < graph->vexNum; vx++){for (int vy = 0; vy < graph->vexNum; vy++){shortPathTable[vx][vy] = graph->arcs[vx][vy]; //shortPathTable[vx][vy]存储对应顶点间的权值pathMatirx[vx][vy] = vy; //初始化路径为邻接点下标}}//代表所有顶点经过Vk中转，再来看这个中转顶点是否可以构造更短路径for (int k = 0; k < graph->vexNum; k++){for (int vx = 0; vx < graph->vexNum; vx++){for (int vy = 0; vy < graph->vexNum; vy++){//D^0[V][W] = min{ D^-1[V][W]，D^-1[V][0] + D^-1[0][W]}//如果经过下标为k的顶点的路径更短，则更新最小值//每次循环内的每个顶点都通过vk中转，逐个尝试if (shortPathTable[vx][vy] > shortPathTable[vx][k] + shortPathTable[k][vy]){shortPathTable[vx][vy] = shortPathTable[vx][k] + shortPathTable[k][vy];//妙啊！！储存中转顶点的下标pathMatirx[vx][vy] = pathMatirx[vx][k]; //路径设置为经过下标为k的顶点，即经过中间顶点k有更短路径}}}}}int main(void){AMGraph* graph = (AMGraph*)malloc(sizeof(AMGraph));creatGraph(graph);//printGraph(graph);Floyd(graph);int k;printf("各顶点间最短路径如下:\n");for (int v = 0; v < graph->vexNum; ++v){//v+1 下一个顶点for (int w = v + 1; w < graph->vexNum; w++){//pathMatirx[v][w] == k，说明从v到w需要走一个中间顶点，下标为kprintf("%c-%c weight: %d ", graph->vexs[v], graph->vexs[w], shortPathTable[v][w]);k = pathMatirx[v][w]; // 获得第一个路径顶点下标printf(" path: %d", v); // 打印源点while (k != w) // 如果路径顶点下标不是终点{printf(" -> %d", graph->vexs[k]); // 打印路径顶点下标k = pathMatirx[k][w]; // 获得下一个路径顶点下标}printf(" -> %d\n", w); // 打印终点}printf("\n");}printf("到达各点的最短路径值：\n");for (int i = 0; i < graph->vexNum; i++){for (int j = 0; j < graph->vexNum; j++){printf("%c - %c : %d ", graph->vexs[i], graph->vexs[j], shortPathTable[i][j]);}putchar('\n');}printf("到达各点的路径：\n");for (int i = 0; i < graph->vexNum; i++){for (int j = 0; j < graph->vexNum; j++){printf("%d ", pathMatirx[i][j]);}putchar('\n');}system("pause");return 0;}
3.拓扑排序和关键路径
有向无环图：无环的有向图，简称DAG图
DAG图常用来描述一个工厂或系统的进行过程
一个工程可以分为若干个子工程，完成子工程(活动)就可以完成整个工程
表示子工程的方法：
- AOV网：以顶点表示活动，弧表示活动之间的优先制约关系，又称为顶点表示活动的网 拓扑排序
- AOE网：以==弧表示活动==，以顶点表示活动的开始或结束事件，又称为边表示活动的网 关键路径
3.1拓扑排序
AOV网的特点：
- 若从 i 到 j 有一条有向路径，则 i 是 j 的前驱；j 是 i 的后继
- 若
- AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，这显然不成立
Q：如何判断 AOV 网中是否存在回路？
A：使用拓扑排序
拓扑排序：在AOV网没有回路的前提下，将全部活动排列成一个线性序列。使得若 AOV 网中有弧
拓扑排序方法：
- 在有向图中选一个没有前驱的顶点输出，存在多个没有前驱的顶点时，选取一个即可
- 从图中删除该顶点和所有以它为弧尾的弧
- 重复上述两步，直到所有顶点均被输出；或当图中不存在无前驱的顶点为止
AOV网的拓扑序列不是唯一的
对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环
3.2 关键路径
把工程计划表示为用边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动，弧的权表示持续时间
每个事件可以表示在它之前的活动结束，也可以表示在它之后的活动开始
栗子：
设一个工厂有11项活动，9个事件。
- 事件V1 —— 表示整个工程开始 (源点：入度为0的顶点)
- 事件V9 —— 表示整个工程结束 (汇点：出度为0的顶点)
两个问题：
- 完成整项工程至少需要多少时间？
- 哪些活动是影响工程进度的关键？
解决：关键路径 —— 路径长度最长的路径
关键路径就是最长路径，一刻也耽搁不得，不然必然影响工程进度；其他路径长度均小于关键路径，可以酌情摸会儿鱼。
以上图为例，确定关键路径，需要定义4个描述量：
Ve(vj) —— 表示事件 vj 的最早发生时间
eg：Ve(v1) = 0 Ve(v2) = 30Vl(vj) —— 表示事件 vj 的最晚发生时间
eg：Vl(v4) = 165E(i) —— 表示活动 a 的最早开始时间
eg：E(a3) = 30L(i) —— 表示活动 a 的最晚开始时间
eg：L(a) = 120L(i) - E(i) —— 表示完成活动 a 的时间余量
eg：L(3) - E(3) = 90关键活动：关键路径上的活动，即 L(i) - E(i) == 0
如何计算 Ve(j) 和 Vl(j)：
从 Ve(1) = 0 开始向前推进
从 Vl(n) = Ve(n) 开始向后递推
一些举例：
最早发生时间：
必须等这4条活动都结束了，才能开始 V 的，因此取决于最长的那条活动，即88
最晚发生时间：
最晚表示的是：如果在10天内必须结束，则 V 最晚在第3天就必须开始，这样才能完成 4 个活动，所以选取的是最小值
V(j) = 3 , 从图上可以看若想继续下一项活动，必须完成V 到这四个的活动，只有从第3天开始才能保证完成 4 项活动，因此 V(j) = 3
求解关键路径步骤：
- 求Ve( i )，Vl( j )
- 求E( i )，求 L( i )
- 计算 L( i ) - E( i )
EG：
表 (1)
设上面的AOE网存在上述关系：则有：
E(i) = Ve(j) 即每个活动的最早发生时间就是弧尾的最早发生时间
L(i) = Vl(k) - W，即每个活动的最晚发生时间是弧头的最晚发生时间减去活动所需时间 a
结合表1，可得出下表：
差值为0的就是关键活动，连线后如下
若有收获，就点个赞吧
0 人点赞
