Chapter 4 图

2024-10-07 23:32:01

Chapter 4 图

.

1- 图的存储结构

无向图：对称

有向图：……

2- 图的遍历

1 深度优先搜索（DFS）

类似于二叉树的先序遍历

2 广度优先搜索（BFS）

类似于二叉树的层序遍历

3- 最小（代价）生成树（针对无向图）MST

1 Prim算法 O(|V²|)

只与顶点数有关，与边无关

2 Kruskal算法 O(|E|log|E|)

只与边数有关，与顶点数无关

//什么样的图最小生成树唯一？图中所有权值不相等。

4- 最短路径

1 Dijkstra O(|V²|)

单源最短路径

l 要找出所有节点的最短路径，需要对每一个结点用Dijkstra O(|V³|)

l 边上有负权值，不适用

2 Floyd O(|V³|)

求解任意一对顶点间的最短距离

l 允许带有负权值的边，但不允许有负权值边组成的回路

5- 拓扑排序 O(|V|+|E|)

1 AOV网

以顶点表示活动，以边表示活动的先后次序，且没有回路的有向图

2 对有向无环图的拓扑排序

可能不唯一：如果有多个入度为0的顶点，可任选一个输出

6- 关键路径

1 AOE网

活动在边上的网，与AOV网相比

相同点：都是有向无环图

不同点：AOE网边表示活动、有权值，表示活动持续时间。顶点表示事件，事件是图中新活动开始旧活动结束的标志。

AOV网边表示活动之间的相互关系，无权值，顶点表示活动。

l 只存在一个入度为0的点称为源点

求关键路径的步骤：

1 拓扑排序

2 事件Vk的最早发生时间Ve(k)

V1->Vi max

3 时间Vk的最迟发生时间Vl(k)

从后向前算 min = 后-max

4 活动ai的最早开始时间e(i)

边上首结点的Ve(k)

5 活动ai的最迟开始时间l(i)

边上尾结点的Vl(k)-ai

6 d = l(i) - e(i)

//可以通过加快那些在所有关键路径上的关键活动来缩短工期

//关键路径不唯一

注：

1- 邻接矩阵的空间复杂度O(|V²|)

2- 邻接表—方便找出所有邻边（不唯一）

邻接矩阵—给定的两个顶点是否存在边

3- 十字链表—有向图的链式存储

容易求得顶点的入度和出度

图的十字链表表示不唯一，但一个十字链表可以唯一确定一个图。

4- 邻接多重表是无向图的另一种链式存储结构

5- BFS借助一个辅助队列，空间复杂度是O(|V|)

邻接表O(|V|+|E|)，邻接矩阵O(|V²|)

6- DFS借助一个栈，空间复杂度是O(|V|)

邻接表O(|V|+|E|)，邻接矩阵O(|V²|)

7- 当各边权值相等时，广度优先算法可以解决单源最短路径问题。

8- Prim O(|V²|)

Kruskal O(|E|log|E|)

Dijkstra O(|V²|)

Floyd O(|V³|)

拓扑 O(|V|+|E|)

9- 最短路径一定是简单路径

10- 可以判断有向图是否有环：深度优先搜索，拓扑排序

最新文章

热门文章