数据结构——图
数据结构——图
一、图的性质
•图的路径的定义是边序列，也可是点边序列（正规定义）：以下默认路径是简单路径（点边序列中边不重合的路径）。
•一个图有n个结点，若边数大于n-1条，则一定有环（首尾结点相同的路径）（记住即可）。
•生成子图是一个包含原图所有结点的子图。
•无向图的连通：
两结点连通，即两结点之间有路径。
一个图是连通图，即任意两个结点有路径。
连通分量 = 极大连通子图 = 包含尽可能多的结点与边的连通子图。
无向图成为连通图所需边最少：构成一条线或一个生成树——n-1条。
无向图成为连通图所需边最多：成为完全图——n(n-1)/2条。
•有向图的强连通：
两结点强连通，即两结点可相互到达。
一个图是强连通图，即任意两个结点可以相互到达。
强连通分量 = 极大强连通子图 = 包含尽可能多的顶点与边的强连通子图。
有向图成为强连通图所需边最少：构成一个环——n条。
有向图成为强连通图所需边最多：成为完全图——n(n-1)条。
•对于连通图，有生成树，该生成树是包含其所有结点的极小连通子图（极小是边极少但仍保持连通）。非连通图有生成森林。
•连通分量只能少结点，生成树只能少边。而“极大”、“极小”是描述边的，因此极大连通子图指连通分量，包含全部顶点的极小连通子图指生成树。
二、图的存储
图的存储分为四种方法。
1.邻接矩阵存储
•矩阵元素为边，要么为1或0，要么为无穷（也可以为0）或一个数。
•矩阵元素（i,j)为1则表明结点i与结点j之间有边（无向图）或从结点i到结点j有弧（有向图）：
因此一个顶点的入度（有向图）为j作为其自身而固定，i从1到|V|的元素中1或非0常数的个数——逐行求和。
因此一个顶点的出度（有向图）为i作为其自身而固定，j从1到|V|的元素中1或非0常数的个数——逐列求和。
因此一个顶点的度（有向/无向图）为上述相加——十字求和。
总结：入行出列。
•存储的空间复杂度为O(n)。
2.邻接表存储及其改进存储方式
•一个图通过邻接表等所有涉及链表的存储方式进行存储的结果都不唯一——链表次序可不同（不用深究矩阵等顺序表为什么不能改变顺序）
•无向图的邻接表存储的边冗余了一倍——导致边链表结点的总数必定是偶数。
•任何需要遍历整个图的邻接表的操作（删除结点、建立表、有向图记录结点入度）的时间复杂度为O(|V|+2|E|)（无向图）或O(|V|+|E|)（有向图）即结点的个数，包括数组结点与链表节点。
•十字链表与邻接多重表是邻接表的变体。十字链表用于有向图，邻接多重表用于无向图。
十字链表解决入度难寻的问题：从结点结构firstout域出发的边链表为其出度链表（一行）；从结点结构firstin域出发的链表为其入度链表（一列）。
邻接多重表解决冗余问题：从结构结构的firstedge出发，每一个边结点都会告诉你下一个下一个边结点的位置，但你需要判断该往ilink走还是该往jlink走。
三、图的遍历
•两种方式——BFS、DFS。
1.BFS：Breadth-First-Search。外层函数使用循环从visted数组首结点开始调用BFS主体函数，循环条件是数组项为0（未访问）。BFS主体函数将传入该函数的结点入队，每次出队一个所有其未访问的邻接结点（需要visited数组支持）。入队时访问或出队时访问均可，访问后将结点对应visited项置1。
•采用邻接表进行BFS遍历，所有的操作无非就是对图的所有结点与所有边操作一次。时间复杂度为O(|V|+|E|)。
•采用邻接矩阵进行BFS遍历，所有的操作无非就是对图的所有结点入队的同时搜索其邻接结点。时间复杂度为O(|V|*|V|)。
2.DFS：Depth-First-Search。外层函数使用循环从visted数组首结点开始调用DFS主体函数，循环条件是数组项为0（未访问）。DFS主体函数先访问该结点，置该结点的visited项为1。然后对其每个visited为0的邻接结点递归调用该DFS主体函数。
•不需要visited数组的条件很苛刻。无向图不可能不需要。有向图只有树形才不需要。
•深度优先搜索可以判断一个图有没有环。这需要维护一个全局parent数组。考虑一个结点访问完后对其邻居判断是否已被访问，若未访问则访问。现在新增：若已访问，则看该邻接结点是否为其双亲结点（其直接遍历前驱），若不是，那么有环。
•BFS生成树的树高为图的两个结点距离的最大值。DFS生成树的树高至少为图的两个结点的最大值。
四、最小（代价）生成树算法
•适用：无向连通图
•应用：连通各点的道路最短修筑距离
1.prim算法：选一个结点加入树开始，维护各个结点加入树的最小代价数组lowCost与是否已经加入树的状态数组isJoin。对剩下每一个结点，调用两个循环。一个循环用于找到加入树代价最小的结点，然后将该结点加入树，将该结点对应的isJoin表项置1。第二个循环用于更新lowCost数组，具体操作是只要比较每个不在树中的结点到刚刚加入树的结点的距离是否小于现有值，小于就改。因此对于|V|-1个结点，每个结点消耗O(|V|+|V|)，总的时间复杂度就是O(|V|^2)。不依赖边。
2.kruskal算法：先将所有边抹除导致每个结点自成一个集合。每次选一条权值最小的边并将边关联的两个集合合并，且边的两个关联节点调用并查集的查操作证明不属于同一个集合，重复操作直到所有结点都在一个集合中。因此总计外层循环次数与边数|E|正相关，每个外层循环内部需调用并查集的查操作，其循环次数与树高log|E|正相关，故总的时间复杂度为O(|E|log|E|)。
•两个算法每次都不保证每次循环一定会选最短的未选边，prim要求新选结点在树之外，kruskal要求新选边的两边不同属一个集合。
五、最短路径算法
•适用：BFS算法适用无权图，Dijkstra算法适用正权图（多为有向图，但可以是无向），Floyd算法适用没有总权值为负的回路的图（多为有向图，但可以是无向）。
•应用：BFS与Dijkstra算法用于求单源最短路径；Floyd算法直接给出任意两点的最短路径。
1.BFS算法：只需修改BFS主体函数。函数一开始就初始化路径长度数组dist除了源为0其余为无穷，每个结点i出队后将其所有邻接结点j入队时将每个邻接结点j的路径长度设置为该出队结点i的路径长度+1（dist[j] = dist[i] + 1）。
2.Dijkstra算法：基于贪心算法。使用final数组表明各结点是否已找到最短路径=是否已经走过，使用dist数组存储各结点到源点的最短路径，使用path数组记录每个结点到源点路径的第一前驱。
a.首先初始化dist为各结点到源点的边的权值，没有边则为∞。若各结点与源点有边，path为源点所在数组下标，否则为-1。
b.然后，挑没走过的（final为0）且距离最短(dist最小)的路走，走完后所处的点到源点的最短路径就定了（不可能绕到其他点再回来会比此路径更短）。将目前所处的点的final置1。
c.最后看看从这个点出发到没有走过的邻接点（final为0）是否会更近，更近则更新dist数组与path数组中该临界点所在的项。
d.重复bc直到走完全部结点或final值都为1。
•时间复杂度分析：总共要走|V|-1个结点，每走到一个结点处，要使用循环遍历其射出的弧修改dist数组与path数组，循环次数取决于该结点的射出的弧数|E|（邻接表）或总结点数|V|（邻接矩阵）。接下来还要一个循环遍历dist数组找到没走过的最小项。因此时间复杂度为O((|V|-1)x(|V|+|E|))或O((|V|-1)x(|V|+|V|))，但化简后都是O(|V|x|V|)。
3.Floyd算法：基于动态规划。采用一个方阵A，逐步以各顶点作为中转迭代A。
a.首先初始化一个nxn的矩阵，每个矩阵元素A(i)(j)为结点i到结点j的距离。
b.以k号结点作为中转(k=0,1,2...n-1)，遍历矩阵，若结点i到结点k再到结点j的距离较原A(i)(j)小(A(i)(k)+A(k)(j) < A(i)(j))，则将A(i)(j)置为A(i)(k)+A(k)(j)。
•时间复杂度分析：显而易见，O(|V|x|V|x|V|)。
六、AOV网扩扑排序、AOE网关键路径算法
•适用：有向无环图。AOV网=有向无环图，AOE网还要求只有一个源点，只有一个汇点。
1.AOV网拓扑排序——标准法：假设已经准备好indegree数组存储每个结点的度
a.初始化一个栈或队列，将原所有度为0的结点如栈，初始化已经输出的结点数count为0，初始化print数组记录先后。
b.开始循环，循环条件为栈非空。每次循环出栈一个结点并将该结点存储进print数组最前面没被存储的位置。将该结点所有射出的弧指向的结点的度-1，遍历该结点所有射出的弧指向的结点，若发现度为0的结点，压入栈中。
c.最后发现count小于图的结点数，则说明有回路（回路导致没有结点度为0），输出失败信息，则输出成功信息。
•排序算法若给的是outdegree则得到是逆拓扑序列。
•若求一个AOV网的全部拓扑序列，则需要注意的是存储空间（队列或栈或别的）中有多个结点，那么出队的顺序是任意的。做题时牢牢根据算法，每个步骤写成“X出XXX...入”，或“X出”（没有入的）。每次出的时候脑海中把相应边抹除。参考王道课后题p244 16题，慢下心来。
•选择题问谁是给定图的拓扑序列直接从选项入手，列出所有扩扑序列需要耗费大量时间。从前至后，删除每个结点与其边，若有个结点删除时发现其前驱没有被删，就错。
•一个有向图有拓扑序列与该有向图没有环与该有向图可以作为AOV网三者等价。
•有向图有有序扩扑序列可以推出有向图的邻接矩阵为三角阵（因为有序拓扑序列任两个结点排在前面必定编号小，而扩扑序列只有排在前面的指向排在后面的弧，没有排在后面的指向排在前面的弧，则所有弧都是小编号结点指向大编号结点，则该图的邻接矩阵为三角阵）。有向图的邻接矩阵是个三角阵，可以推出该有向图必定无环，拓扑序列必定存在。
2.AOV网拓扑排序——DFS法：假设已经给出一个度为0的点
从该度为0的结点开始，调用DFS函数。函数主体先递归访问其所有未被访问的邻接，然后再将其自身添加进一个数组前面。如此，得到的数组的顺序就是先最后的工程，最后才是一开始先完成的工程。最后将数组倒置即为扩扑序列。
•若最后不倒置则得到的是逆扩扑序列。
3.AOE网关键路径
（结点代表的）事件的最早发生时间：当每个活动能做就做时所有前面发生的最晚结束的活动结束的时候。（不能再早了，不然就抢先了）。
（结点代表的）事件的最迟发生时间：当每个活动能拖就拖时所有后面发生的最早开始的活动开始的时候。（不能再晚了，不然就来不及了）。
（弧代表的）活动的最早开始事件=弧的源头结点的最早发生时间。
（弧代表的）活动的最晚开始事件=弧的指向结点的最晚发生时间-该活动耗时。
•关键路径上各个结点发生时间固定。最早发生时间=最晚发生时间。
•关键路径算法：
1.先对图进行扩扑排序与逆拓扑排序。
2.利用扩扑序列，从源点开始，求得每个结点的最早发生时间。
3.利用逆拓扑序列，从汇点开始，求得每个结点的最晚发生时间。
4.最早与最晚发生时间相等的结点构成关键路径（可能多条）。
•AOE网关键路径算法能判断图是否有回路全依赖扩扑排序的count。
•选择题求一个AOV网关键路径时用瞪眼法。
