厦门 网站建设常州网络公司网站

一、有向图中的排序与调度

1、深度优先搜索的排序

使用深度优先搜索对图中顶点进行排序，根据数据结构性质与递归保存顺序，有以下三种排列顺序

（1） 前序：在递归调用之前将顶点加入队列。
（2）后序：在递归调用之后将顶点加入队列。
（3）逆后序：在递归调用之后将顶点压入栈。

几个结论：

（1）一幅有向无环图的拓扑顺序即为所有顶点的逆后序排列

（2）使用深度优先搜索对有向无环图进行拓扑排序所需的时间和 V+E 成正比。

（3）在有向图中，深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的所有顶点的出度之和成正比。

2、拓扑排序与任务调度

解决任务调度类应用通常需要以下 3 步：
（1）指明任务和优先级条件；
（2）不断检测并去除有向图中的所有环，以确保存在可行方案的；
（3）使用拓扑排序解决调度问题。

调度方案的任何变动之后都需要再次检查是否存在环，然后再计算新的调度安排。

二、有向图中的连通性与可达性

1、问题描述

强连通性问题：给定一幅有向图，回答“给定的两个顶点是强连通的吗？这幅有向图中含有多少个强连通分量？ ”等类似问题。

顶点对的可达性问题 给定一幅有向图，回答“是否存在一条从一个给定的顶点 v 到另一个给定的顶点 w 的路径？ ”等类似问题。

2、Kosaraju 算法

Kosaraju 算法是一种在有向图中高效计算强连通分量的算法。

Kosaraju 算法使用深度优先搜索查找给定有向图 G 的反向图 GR，根据由此得到的所有顶点的逆后序再次用深度优先搜索处理有向图 G，其构造函数中的每一次递归调用所标记的顶点都在同一个强连通分量之中。

3、步骤

（1）在给定的一幅有向图 G 中，使用 DepthFirstOrder （深度优先）来计算它的反向图 GR 的逆后序排列。
（2）在 G 中进行标准的深度优先搜索，但是要按照刚才计算得到的顺序而非标准的顺序来访问
所有未被标记的顶点。

（3）所有在同一个递归 dfs() 调用中被访问到的顶点都在同一个强连通分量中，将它们识别出来。