Ch6 图

• 有向图和无向图都可以使用邻接表或邻接矩阵存储。有向图还可以使用十字链表存储，无向图还可以使用邻接多重表存储。

• BFS 解决非带权图的单源最短路径问题，广度优先算法使用队列实现。

	邻接矩阵	邻接表	十字链表	邻接多重表
空间复杂度	$O(V^2)$	无向图：$O(\Vert V\Vert +2\Vert E\Vert )$; 有向图：$O(\Vert V\Vert +\Vert E\Vert )$	$O(\Vert V\Vert +\Vert E\Vert )$	$O(\Vert V\Vert +\Vert E\Vert )$
找相邻边	遍历对应一行或一列的时间，复杂度为$O(V)$	找有向图的入度必须遍历整个邻接表	很方便	很方便
删除边或节点	删除边很方便，删除顶点需要大量移动数据	删除边或节点都不方便	很方便	很方便
适用于	稠密图	稀疏图和其他	仅有向图	仅无向图
表示方式	唯一	不唯一	不唯一	不唯一

无向图：无向图边数的两倍等于各顶点度数的总和

简单图：不存在重复边；不存在顶点到自身的边。

完全图

• 无向完全图：任意两个顶点之间都存在边。
• 有向完全图：每两个顶点之间存在方向相反的两条边。

连通图

• 无向图中讨论连通性，有向图中讨论强连通性。
• 无向图中的极大连通子图成为连通分量。
• 有向图中的极大强连通子图成为有向图的强连通分量。

生成树：包含图中全部顶点的一个极小连通子图。

最小生成树：全部生成树中边权值和最小的那棵。

有向树：一个顶点的入度为 0，其余顶点的入度均为 1 的有向图。

十字链表的表示

邻接多重表的表示

BFS 算法、Dijkstra 算法和 Floyd 算法求最短路径的总结

	BFS 算法	Dijkstra 算法	Floyd 算法
用途	求单源最短路径	求单源最短路径	求各顶点之间的最短路径
无权图	适用	适用	适用
带权图	不适用	适用	适用
带负权值的图	不适用	不适用	适用
带负权回路的图	不适用	不适用	不适用
时间复杂度	$O(\Vert V{\Vert }^2)$ 或 $O(\Vert V\Vert +\Vert E\Vert )$	$O(\Vert V{\Vert }^2)$	$O(\Vert V{\Vert }^3)$

关键路径

关键路径是_指设计中从输入到输出经过的延时最长的逻辑路径。

事件用来描述顶点，活动用来描述弧

事件 $v_k$的最早发生时间$v_e(k)$：从源点 $v_1$到顶点 $v_k$的最长路径长度。

事件 $v_k$的最迟发生时间 $v_l(k)$：指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。计算公式：$v_l(k)=Min\left\{v_l(j)-Weight(v_k,v_j)\right\}$， $v_k$为 $v_j$的任意前驱。

活动 $a_i$的最早开始时间 e(i)：活动弧的起点表示的事件的最早发生时间，$e(i)=v_e(k)$

活动 $a_i$的最迟开始时间 l(i)：活动弧的终点所表示的事件的最迟发生时间与该活动所需时间之差。$l(i)=v_l(j)-Weight(v_k,v_j)$