图论 算法
2007/06/11
2
主要内容
- 最短路径
- AOV网
- 拓扑排序
- 关键路径
3
作业： 第一题 判断有向图回路
- 问题分析：如果图中存在回路，则必包含一个子图为回路。即该子图中所有顶点入度不为0且至少有边指向另外的顶点。
- 算法：
- 步骤1：按邻接表方式存储图。遍历与每个节点关联的边并统计每个节点的入度。需要O(n+m)次的运算。
- 步骤2：删除所有入度为零的顶点及其相发出的边。并将被删除边所指向的顶点的入度减1。
- 重复步骤二 直到：
case1: 所有顶点被删除（则没有回路） 或
case2: 还有顶顶点但没有入度为零的顶点可删除（则存在回路）。
算法复杂度分析：
由于步骤二中的删除边的操作运算复杂度为O(m),删除节点的操作为O(n) 判断节点入度是否为0需要O(n+m)次运算。其中O(n)次为初始入度为零的节点,O(m)次为删除边后导致的入度为零的节点。 于是整个算法复杂度为O(m+n)。
4
作业： 第二题 判断无向图是否有回路
如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。
- 算法：
第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。
第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。
如果最后还有未删除顶点，则存在环，否则没有环。
- 算法分析：
由于有m条边，n个顶点。如果m>=n，则根据图论知识可直接判断存在环路。