2019-10-24图论基础

图的2种表示手段：邻接矩阵和邻接表
邻接矩阵用一个数组存储所有结点的信息，用一个矩阵来代表边，适合稠密图
邻接矩阵用链表来代表顶点和边的关系。
也是用一个数组来存储所有顶点，顶点里含有指向邻边顶点的指针，抽象出的关系是顶点（顶点信息，弧指向邻边），弧（边信息，邻接顶点）

遍历算法：
dfs（递归的运用，注意需要一个数组来记录访问状态）
bfs（队列的运用，存储邻边，注意的是队列每次是入多出1，因此在入队时进行标记和访问，可以避免结点的重复多次入队）

最小生成树：
普利姆算法：
从某个具体顶点出发，每次选出距离当前顶点最近的顶点，并入树，最后全部并入，即是一棵最小生成树，复杂度为n方，n为顶点个数，因此适合稠密图（边不影响算法复杂度，所以边越多，普里姆的优势越大）
辅助的工具（顶点的访问状态，当前到各个点的最短距离）
操作（找到最近的点，访问，根据最新的最近点去更新距离，注意只需要更新和查找未被访问过的点，因为每次圈入一个点，所以需要循环n-1次）

克鲁斯卡尔：

最短路径：
迪杰斯特拉算法：
类似普利姆算法，只是在更新的时候要还是算上初始点到新的最近点的距离，另外就是多维护了一个path表（一维数组，记录路径，记住初始化和更新的时候进行更新）
记住如何打印最短路径

弗洛伊德算法：
以中间点为核心，逐个遍历（3重循环，1个用来选择中间点，1个用来选起始点，1个用来选终点，然后比较）
维护了一个path（用的二维矩阵，存的点代表行到列经过了某个结点）
打印最短路径的话其实相当于一个二分算法，找到mid结点后，还要继续在left到mid，和mid到right中继续找

拓扑排序：
AOV网：活动在顶点上的图，即图的顶点代表活动
AOV网代表了1种依赖关系，i指向j代表j依赖于i，这样要想实现j需要先实现i，那么就需要考虑入度
实现思路：
以邻接表举例（因为很好找邻边）
辅助数据：1个计数器来计数已经访问过几个，1个栈或者队列用来保存入度为0的结点
算法实现：
先遍历一遍素有结点，把入度为0的结点放入栈或队列
开始循环，只要栈或队列不为空，弹出元素，访问操作，计数器+1，遍历所有邻接结点，把邻接结点的入度-1，若之后为0，入队
最后容器为空后，判断计数器是否等于顶点个数，等于，说明实现了拓扑排序，原aov是有向无环图；不等，说明不能拓扑排序，原aov存在环。

逆拓扑排序：
前提：有向无环，优先输出出度为0的结点
实现思路：采用图的dfs遍历（不过是先递归，再输出），这样可以保证每次输出的都是出度为0的结点

关键路径：
AOE网：图的边代表活动，有权值，代表活动时间；图的顶点代表事件，有向无环；只有1个入度为0的点，代表整个工程的开始，成为源点；只有1个出度为0的点，代表整个工程的结束，称为汇点；顶点之间代表了跟AOV一样的依赖关系；同时，所有事件可以同时进行。
那么什么是关键路径呢？关键路径就是指必须立刻执行的事件所构成的路径。从源点到汇点最长的路径就是关键路径。类似木桶理论，因为这条路径最长，所以别的事件完成的再早也给等待，这样别的事件就有了宽裕的空间，而关键路径上的事件没有宽裕时间，因为它本身就是瓶颈点，再延后就会更加耽误工期了。
那么怎么找出关键路径呢？只要计算出每个事件的最早发生事件和最晚发生事件即可。
实现方法：
1.拓扑排序，得到各个事件发生的先后顺序
2.求各个事件的最早发生时间，对于相邻的事件 i,j ve(j)=max(ve(i)+<i,j>) ，i是j的前驱结点，可能有多个
3.全部求出最早事件后，通过汇点ve(k)=vl(k),开始倒推之前的结点的最晚发生时间vl(i),i,j相邻，vl(i)=min(vl(j)-<i,j>)，j是i的后继结点，可能有多个.
4.找出vl(i)=ve(i)的结点，这些结点组成的路径就是关键路径

补充知识：
并查集：
作用：
1.快速的把2个集合合并为1个
2.快速判断2个元素是否在同1个集合中
实现：
最简单的方式是用1个数组，下标代表元素，内容代表父亲结点；
若2个元素的根结点是1个，就代表在1个集合中（实现作用2，根节点就是自己的父亲结点是自己）；把a的根结点改为b的根结点，相当于把a所在的集合和b所在的集合合并成了1个集合（实现了作用1 ）