基本概念
假设ABCDEFG是7个电话，它们之间的连线表示修有通信线路
电话就是图的顶点 vi∈V，通信线路是边 ei∈E，G = {V, E}就是一个图
只要两个电话间有线路，就可以相互通话 => 无向图
电话(顶点)连接的线路(边)数量：度
ABCDE和GF之间消息无法传递：不连通
ABCDE和GF是两个连通分量
加权图
进来某数据的数量：入度
从某数据出去的数量：出度
在一个无向图中，所有顶点的度数之和为边数量的2倍
在一个有向图中，所有顶点的出度之和 == 所有顶点的入度之和
图的储存结构
邻接矩阵
设|V| = n, 图可用一个 n * n 方阵表示
• 即一个二维数组 AdjMat[n][n]
• AdjMat[i][j] 表示 vi 到 vj 的邻接情况
邻接表
每个顶点用一个链表存下自己的邻居
图DFS和BFS的遍历
DFS：深度优先遍历
主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点看是否有得走，有的话就再从另一条路开始走到底，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
蓝色数字就是遍历的顺序
BFS：广度优先遍历
先把当前结点的邻居都遍历完，再按先来后到遍历邻居的邻居们，逐层向外扩张
优先进入先访问的邻居的邻居 => 队列
生成树
无向连通图
对于含n个结点的一个无向连通图，其边数最多为 n(n-1)/2 条，最少为 n-1 条
保持连通性的情况下，选 n-1 条边出来，剔除其他边，它就变成了一颗树
加权图
在加权图中选出 n-1 条边来构成其生成树，且这些边的权值之和最小
MST 不一定唯一（如权值全相同）
上图的生成树
最小生成树 用Prim算法
prim算法是“加点法”
每次在连接已完成结点和未完成结点的边中，选一条权值最小的，重复n-1遍
算法利用了贪心思想：选择局部最优
迪杰斯特拉算法
划重点，迪杰斯特拉最最朴素的思想就是按长度递增的次序产生最短路径。即每次对所有可见点的路径长度进行排序后，选择一条最短的路径，这条路径就是对应顶点到源点的最短路径。
就是每一步循环都能找到 到某一点的最小值，然后保留它，最后的Dist 里就留的是像上图那样，A到各点的最小值
拓扑排序(AOV)
你看（b)步骤以后，假设你（c)步骤是输出b,是不是c就会莫名指了个寂寞，就差不多这个意思。
网络求解关键路径（AOE）
考试会给一个AOE网络，求关键活动和关键路径
方法：求每个结点的最早/最晚发生时间 vE 和vL ，以及每个活动的最早/最晚开始时间 eE 和 eL
用最朴素的语言讲这个图
状态图里，状态1的最早发生时间要等s做完3秒后才开始到它，所以Ve为3，VL最晚发生时间为9，是因为状态3是需要上图两条线
一起都完成了才能开始做，而S23这条线需要13秒，1到3需要4秒，所以同步开始的话，最起码1要开始做 最迟应该从13-4=9秒
活动图里，a1这个3秒的流程，可以最开始就做，所以eE是0秒动手，要知道状态3是需要两条路线一起完成了才能开始做，而S23这条线
需要13秒，所以a1的活动最迟是从6秒开始，这样它做了个3秒，又接着4秒，刚好能赶上S23线一起到状态3.
京公网安备 11010502036488号