求用简单语言讲一下数据结构中的关键路径和强连通分量。急！！！！

Question

如题所述

Answer 1

关键路径

在学习关键路径前，先了解一个AOV网和AOE网的概念：

用顶点表示活动，用弧表示活动间的优先关系的有向图：

称为顶点表示活动的网（Activity On Vertex Network），简称为AOV网。

与AOV网对应的是AOE（Activity On Edge）网即边表示活动的网。

AOE网是一个带权的有向无环图。

网中只有一个入度为零的点（称为源点）和一个出度为零的点（称为汇点）。

其中，顶点表示事件（Event），弧表示活动，权表示活动持续的时间。

通常，AOE网可用来估算工程的完成时间。

假如汽车生产工厂要制造一辆汽车，制造过程的大概事件和活动时间如上图AOE网：

我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。

//----------分隔线-----------------

有向图强连通分量：

在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通（strongly connected）。

如果有向图G的每两个顶点都强连通，则称G是一个强连通图。

非强连通图有向图的极大强连通子图，成为强连通分量（strongly connected components）。

下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达，{5}，{6}也分别是两个强连通分量。