数据结构 图的基本概念和算法
彩笔离散数学学的很烂，刚好数据结构学到了，这边顺便梳理一下。
工具:draw.io(开启数学排版，输入latex公式时不能换行)，visual studio 2022.
1. 点
结点(顶点)
邻接点：假若顶点v 和顶点w 之间存在一条边， 则称顶点v 和w 互为邻接点。
终点(Destination)：路径的最后一个顶点。
源点(Source)：一般指带权有向无环图中入度为0的点。
汇点：一般指带权有向无环图中出度为0的点。
2. 边
边：一般指无向的边。
弧：指有向的边，弧头(箭头),弧尾(箭头尾部)。
w_{k,i}是<v_{k},v_{i}>的弧值，其中v_{i}是弧头，v_{k}是弧尾。
弦：无向图中，连接一个环非相邻两个顶点的边。
平行边：两点间有多条同始同终的边。
重数：平行边的条数。
出度：从某点出的边数。
入度：从某点入的边数。
节点度：和该节点相关联的边的条数，又称关联度。
1.无向图中所有顶点的度之和等于边数的2倍。
2.有向图中所有顶点的入度之和等于所有顶点的出度之和。
3. 次数为奇数的结点(奇点)必为偶数个。
点的度数(次数)：该点的入度+出度。
回路(环)：第一个顶点和最后一个顶点相同的路径。
路径：由顶点和相邻顶点序偶构成的边所形成的序列。
简单路径：路径上的各顶点均不重复。
简单回路：起点终点重合，其余经过的顶点不重复出现的回路叫简单回路。
基本路径：不包含任何重复边和重复顶点的路径。
基本回路：起点终点重合，其余经过的点和边没有重复的回路。
可达：点1到点2存在一条路径，则1到2可达。
3. 图
G=<V,E>。G表示个图，V是图G中顶点的集合，E是图G中边的集合。
有向图：每条边都有方向
无向图：每条边都无方向
多重图：有平行边。
线图：无平行边。
简单图：既不含平行边也不含自环的图。
平凡图：仅一个结点。
稠密图：接近完全图。
稀疏图：边数很少的图。
无向完全图：每对顶点之间都恰连有一条边的无向图。
有向完全图：各边都有方向，且每两个顶点之间都有两条方向相反的边连接的图。
连通：无向图中，任意两点都有路径相连。有向图中，任意两点都有路径相连，且路径的每一条边同向。
连通图：任意两点连通(没有孤立点)（相互可达）。
连通分图：子图A连通，没有比A更大的子图是连通的->图A是原图的连通分图。
连通分量：无向图G的极大连通子图称为G的连通分量。
点连通度：为使图G不连通或成为平凡图，至少需要从G中删除的顶点数量称作G的点连通度，k。
边连通度：为使图G不连通或成为平凡图，至少需要从G中删除的边的数量称作G的边连通度，l。
最小度：无向图G中度数最小顶点的度数，d。k<=l<=d
单向连通图：有向图D中任意两点vi,vj，都有一条vi到vj的路径或者vj到vi的路径（单向可达）。
弱连通图：有向图D的底图是无向连通图。
强连通图：有向图D任意两个结点彼此可达。
网图或网：边(或弧)上标识有权的图。自己和自己为0，非邻接顶点为∞，权为权值。
子图：节点集和边集分别是某一图的节点集的子集和边集的子集的图。
生成子图：设G=<V,E>，G1=<V1,E1>.当V1=V,E1
E时，G1是G的生成子图。
导出子图：设
以V2作为结点集，以两个端点都在V2中的边的全体为边集的G的子图，称为V2导出的G的子图，简称V2的导出子图。
或者说点集合V2是原图点集合V的非空子集，然后再在原图的边集合E中找到两个端点均在点集合V2中的边元素，并将这些边元素称成一个新的边集合E2，得到的这个边集合就是导出子图的边集合。
补图：设G=<V,E>为简单图,G2=<V,E1>为完全图，则称G1=<V,E1-E>为G的补图，记为
。
补图就是从完全图中删除图G中的边。
4. 树相关
生成树：设G为无向连通图，T是G的生成子图且为树，则T是G的生成树。若G中顶点数为n,则T含有n-1条边。G在T中的边称为树枝，不在的边称为弦。
有向树：是只有一个顶点的入度为0，其余顶点的入度均为1的有向图。
生成森林：在非连通图中，多个连通分量对应的多棵生成树就构成了整个非连通图的生成森林。
余树：一个连通无向图的生成树中被删去任一条边后形成的树。
最小生成树：带权图中权值最小的生成树。
5. 图的存储
邻接矩阵：对于有向图vij表示顶点i到j是否有弧(有1无0)，当弧带权重时，vij表示顶点i到j弧的权重(没有弧则∞)。对于无向图vij表示顶点i到j是否有边(有1无0)，当边带权重时，vij表示顶点i到j边的权重(没有边则∞)。
正邻接表：最左侧格子为起始点。在有向图中，为图中每个顶点vi建立一个出边表。
逆邻接表：最左侧格子为终点。在有向图中，为图中每个顶点vi建立一个入边表。
顶点表：左侧为编号，右侧为结点名。
边表：前两列为构成边的节点，第三列为该边的权重。
1. 设一有向图G=(V,E)，其中V={a,b,c,d,e} ， E={<a,b>, <a,d>, <b,a>, <c,b>, <c,d>, <d,e>,<e,a>, <e,b>, <e,c>}，画正邻接表，逆邻接表。
2. 参照下面带权无向图，画邻接矩阵，顶点表，边表。
6. 图相关算法
1. DFS与BFS
深度优先搜索(DFS)(Depth First Search)：从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底...，不断递归重复此过程，直到所有的顶点都遍历完成。
如上图，先取v1，然后遍历v1邻接点v2，v2所有邻接点都被访问，回退查找v1未被访问的邻接点v4，然后遍历v4邻接点v3,遍历v3邻接点v5。
上述深度优先遍历序列：v1 v2 v4 v3 v5。
广度优先搜索(BFS)(Breadth First Search)：先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问到；由近到远访问，依次访问和v有路径长度为1、2、3..的顶点。图中尚有顶点未访问到，则另选图中一个未曾被访问的顶点做起点，重复上述过程，直至所有顶点被访问完为止。
如上图：先取v1,然后取v1邻接点v2,v4,然后取v4邻接点v3，然后取v3邻接点v5。
上述广度优先遍历序列：V1 V2 V4 V3 V5。
2. Prim与Kruskal 求最小生成树
普利姆算法(prim)：设图G=<V,E>，从V中取一点放入V1集合中，查找一个起始点在V1集合中，终点在(V-V1)集合中的最小权值的边，将终点放入V1集合中，重复上述操作，直到V1包含G所有顶点。
如图6-27，若从顶点2出发，此时2在V1中且边(2,4)权值最小，取顶点4，此时4在V1中且边(4,3)权值最小，取顶点3，然后以此类推取顶点1，6，5。
克鲁斯卡尔算法(Kruskal)：设图G=<V,E>,依次从E中取权值最小的边(或弧)并不构成回路，直到构成加权连通图的最小生成树。(适用于稀疏图)
如图6-27，先取此时权值最小的边(4,3)，然后依次取(4,1),(5,6),(3,6),(4,2)。
3. Dijkstra
迪杰斯特拉算法(dijkstra)：图中某一个顶点，到其它顶点之间的最短路径．时间复杂度为O(n^2)。 1. 假设S为最短路径已确定的顶点集，V-S是最短路径尚未确定的顶点集。D[v]为u到v的最短路径长度，初始时，将源点u放入S中 2. 初始D[v]，v∈ V-S，D[v]=w<u,v> 3. 选取点k使D[k]=min{D[v]： v∈ V-S} 4. 将k添入S 5. 若V-S不空，重新计算D[v]值，其中v∈ V-S 6. If (D[v]> D[k]+w<k,v>){D[v]= D[k]+w<k,v>; 并修改源点到v的路径上的点为源点到k的路径加上点v} 7. 若V-S为空，则结束，否则重复步骤第三 如下图，以v4为源点，写出迪杰斯特拉算法过程。
//伪代码分析过程
设G=<V,E,W>,源点v4
V={v1, v2, v3, v4, v5, v6}
S={v4}
dist[4]=0
dist[2]=20, dist[6]=15,
dist[1]=dist[3]=dist[5]=∞
S={v4,v6}
dist[4]=0,dist[6]=15,
dist[2]=20,
dist[1]=dist[3]=dist[5]=∞
S={v4,v6,v2}
dist[4]=0,dist[6]=15,dist[2]=20,
dist[1]=30,dist[5]=50,//v2与v5，v2与v1相邻，需重新计算v4到v5,v1的路径长度
dist[3]=∞
S={v4,v6,v2,v1}
dist[4]=0,dist[6]=15,dist[2]=20,dist[1]=30,
dist[3]=45,dist[5]=50//v1与v3相邻，重新计算了v4到v3的路径长度
S={v4,v6,v2,v1,v3}
dist[4]=0,dist[6]=15,dist[2]=20,dist[1]=30,dist[3]=45,
dist[5]=50
S={v4,v6,v2,v1,v3,v5}
dist[4]=0,dist[6]=15,dist[2]=20,dist[1]=30,dist[3]=45,dist[5]=50 
4. Floyd
弗洛伊德算法(Floyd)：图中每一个顶点，到其它顶点之间的最短路径．时间复杂度为O(n^3)。
要求的解是一个矩阵Ｓ[N][N]，其中S[i][j]表示结点i到j的最短路径
Floyd算法过程描述如下： １、 首先Ｓ以边集Ｍ初始化，得到所有的直接连通代价； ２、 依次考虑第k 个结点，对于Ｓ中的每一个Ｓ [ i ][j]，判断是否满足： S[ i ][j]>S[ i ][k]+S[k][j] ，如果满足则用 S[ i ][k]+S[k][j] 代替Ｓ [ i ][j] ，此为第 k步； ３、 k循环取遍所有结点，算法结束时，Ｓ为最终解。
求下图每个顶点到其他顶点的最短路径。
上图加入中间顶点a后，路径多了e->a->b和e->a->c。
ace替换abe
bfea替换 bea ，bfeac替换beac，bfeacd替换beacd。
5. AOV-网与拓扑排序
有向无环图(Directed Acycline Graph)：简称DAG图。
AOV-网(Activity On Vertex Network)：顶点表示活动的图。有向图顶点表示活动，弧表示活动间的优先关系。
拓扑排序：将AOV-网中所有顶点排成一个线性序列，该序列满足：若在AOV-网中由顶点vi到vj有一条路径，则再该线性序列中的顶点vi必定再vj之前。
拓扑排序的过程
(1)在有向图中选一个无前驱的顶点且输出它。
(2)从图中删除该顶点和所有以它为尾的弧。
(3)重复(1)和(2)，直至不存在无前驱的顶点。
(4)若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在环，否则输出的顶点序列即为一个拓扑序列。
6. AOE-网与关键路径
AOE-网(Activity On Edge)：以边表示活动的网。带权有向无环图中，顶点表示事件，弧表示活动，权表示活动持续的时间。
由于整个工程只有一个开始点和一个完成点，故在正常的情况(无环有向带权图)下，网中只有一个入度为零的点，称作源点，也只有一个出度为零的点，称作汇点。
带权路径长度：在AOE网中，一条路径各弧上的权值之和称为该路径的带权路径长度(后面简称路径长度)。
关键路径(Critical Path)：要估算整项工程完成的最短时间，就是要找一条从源点到汇点的带权路径长度最长的路径。
关键活动：关键路径上的活动叫做关键活动(时间余量为0)。
某些(注意不是任一)关键活动提前完成，整个工程将会提前完成。（有点类似木桶效应吧）
Ve(i)：事件vi最早发生时间。Ve(i)是从源点到Vi的最长路径长度。
Vl(i)：事件vi最晚发生时间。
e：活动最早开始时间。弧尾顶点最早开始时间。
l：活动最晚开始时间。弧头顶点最迟时间-权值。
时间余量(期限余量)：l(i)-e(i)，在此范围内的适度延误不会影响整个工程的工期。
求解下图关键路径和关键活动。
拓扑排序：V0V1V2V3V4V5V6V7V8V9
逆拓扑排序：V9V8V7V6V5V4V3V2V1V0
综上，关键路径为：(V0,V2,V3,V6,V8,V9)，关键活动为：(a2,a4,a8,a12,a14)。
解题过程详解：
- 写出拓扑排序和逆拓扑排序。
- 画表格，根据拓扑排序的顺序写Ve行，V0到V0距离为0，V0到V1距离为5，...，V1和V2到V3有弧，Ve(V3)=Max{Ve(V1)+3,Ve(V2)+12}=Max{8,18}=8,...。
- 最后的V9先照着上面的30写下来，根据逆拓扑排序的顺序写Vl行，V8可以到V9，路径为2，故vl(V8)=30-2=28,...,V4可以到V6和V7，vl(V4)=Min{Vl(V6)-1,Vl(V7)-4}=22,...。
- 然后求e,a1弧尾V0最早开始时间0，a2弧尾V0最早开始时间0，...，a14弧尾V8最早开始时间28。
- 然后求l，a1弧头V1最晚开始时间15，减去a1权值5后为10，...，l(a14)=30-2=28。
- 最后算时间余量，写关键路径和关键活动。
上面内容有问题麻烦指正！
业精于勤荒于嬉，行成于思毁于随。--韩愈
7. 一些性质
1. 对于一个具有n个顶点的有向图的边数最多有n*(n-1)。
部分参考资料
《数据结构》严蔚敏 李冬梅 吴伟民
