当前课程知识点：算法设计与分析 > 3 Graph > 3.5 DAG and Topological Ordering > DAG and Topological Ordering
接下来 我们介绍有向无圈图和拓扑排序
我们先给出有向无圈图的相关概念
一个有向无圈图指的是
不包含有向圈的有向图
边上的方向可以表示优先级约束
比如边(v_i, v_j)可以表示v_i必须先于v_j
有向图G=(V, E)的一个拓扑排序指的是
它的节点可以被标记为v_1, v_2, …, v_n的顺序
使得对于每条边(v_i, v_j) 都有i 下图给出了一个有向无圈图 和它的拓扑排序 有这样的引理 如果G有一个拓扑排序 则G是一个有向无圈图 通过反证法证明如下 设G有一个拓扑排序v_1, …, v_n 并且G有一个有向圈C 我们看会发生什么 可以借助下图来帮助理解 令v_i为C中标号最小的节点 并且令v_j为C中在vi之前的节点 由我们对i的选择 我们可以得到i 另一方面 因为(v_j, v_i)是一条边 并且v_1, …, v_n是一个拓扑排序 所以一定有j 从而产生矛盾 关于有向无圈图 还有这样的引理 如果G是一个有向无圈图 那么G中一定存在没有入边的节点 通过反证法证明如下 设G是一个有向无圈图 并且每一个节点都至少有一条入边 我们看会发生什么 也可以借助下图来帮助理解 任取节点v 并且从v开始沿着边往回走 因为v至少有一条入边(u, v) 我们可以往回走到u 接着 因为u至少有一条入边(x, u) 我们可以往回走到x 重复上述过程 因为节点数目有限 我们会遇到了一个节点两次 不妨设其为w 令C表示对w连续访问之间 所遇到的节点的序列 则C是一个圈 产生矛盾 我们还有引理 如果G是一个有向无圈图 则G有一个拓扑排序 对n进行归纳证明如下 基本情形 当n=1时 显然正确 给定含n>1个节点的有向无圈图 则有节点v 其没有入边 因为删掉v不会产生圈 所以G-{v}是一个有向无圈图 根据归纳假设 G-{v}有一个拓扑排序 把v放在拓扑排序的第一个位置 然后以拓扑排序添加G-{v}中的节点 因为v没有入边 所以这样做是有效的 得到拓扑排序的算法过程如下 1 找到没有入边的节点v 并且将其排在第一个 从G中删掉v 递归计算G-{v}的一个拓扑排序 并且把这个排序添加到v之后 我们给出拓扑排序算法的一个例子 对于该有向图 找到没有入边的节点v_1 将v_1排在第一位 去掉v_1及从它出发的边 得到新的图 在新的图中找到没有入边的节点v_2 将v_2加入到拓扑排序当中 去掉v_2及从它发出的边 得到新的图 在新的图中找到没有入边的节点v_3 将v_3加入到拓扑排序中 去掉v_3及从它发出的边 得到新的图 在新的图中找到没有入边的节点v_4 将v_4加入到拓扑排序中 去掉v_4 以及从它发出的边 得到新的图 在新的图又找到没有入边的节点v_5 将v_5加入到拓扑排序中 去掉v_5 以及从它发出的边 得到新的图 在新的图中找到没有入边的节点v_6 将v6加入到拓扑排序中 去掉v_6及从它出发的边 得到新的图 在新的图中找到没有入边的节点v_7 将v_7加入到拓扑排序中 这样就完成了拓扑排序 左图是我们原来看到的图 右图是把节点按照拓扑排序排列之后 表示出来的图 最后我们来讨论拓扑排序算法的运行时间 算法在O(m+n)的时间找到一个拓扑排序 证明 算法过程中保持如下信息 count[w]为节点w当前入边的数目 S为没有入边的节点的集合 初始需要O(m+n)的时间 对图进行一次扫描 对于更新的过程 从S中去掉v 针对所有从v到w的边 相应的count[w]-1 并且如果count[w]达到0的话 把w加入到S中 这个过程每条边需要花时间O(1) 所以整个的运行时间是O(m+n)
-1.1 Introduction
-1.2 A First Problem: Stable Matching
--A First Problem: Stable Matching
-1.3 Gale-Shapley Algorithm
-1.4 Understanding Gale-Shapley Algorithm
--Understanding Gale-Shapley Algorithm
-Homework1
-Lecture note 1
--Lecture note 1 Introduction of Algorithm
-2.1 Computational Tractability
-2.2 Asymptotic Order of Growth
-2.3 A Survey of Common Running Times
--A Survey of Common Running Times
-Homework2
-Lecture note 2
--Lecture note 2 Basics of Algorithm Analysis
-3.1 Basic Definitions and Applications
--Basic Definitions and Applications
-3.2 Graph Traversal
-3.3 Testing Bipartiteness
-3.4 Connectivity in Directed Graphs
--Connectivity in Directed Graphs
-3.5 DAG and Topological Ordering
--DAG and Topological Ordering
-Homework3
-Lecture note 3
-4.1 Coin Changing
-4.2 Interval Scheduling
-4.3 Interval Partitioning
-4.4 Scheduling to Minimize Lateness
--Scheduling to Minimize Lateness
-4.5 Optimal Caching
-4.6 Shortest Paths in a Graph
-4.7 Minimum Spanning Tree
-4.8 Correctness of Algorithms
-4.9 Clustering
-Homework4
-Lecture note 4
--Lecture note 4 Greedy Algorithms
-5.1 Mergesort
-5.2 Counting Inversions
-5.3 Closest Pair of Points
-5.4 Integer Multiplication
-5.5 Matrix Multiplication
--Video
-5.6 Convolution and FFT
-5.7 FFT
--FFT
-5.8 Inverse DFT
-Homework5
-Lecture note 5
--Lecture note 5 Divide and Conquer
-6.1 Weighted Interval Scheduling
--Weighted Interval Scheduling
-6.2 Segmented Least Squares
-6.3 Knapsack Problem
-6.4 RNA Secondary Structure
-6.5 Sequence Alignment
-6.6 Shortest Paths
-Homework6
-Lecture note 6
--Lecture note 6 Dynamic Programming
-7.1 Flows and Cuts
-7.2 Minimum Cut and Maximum Flow
--Minimum Cut and Maximum Flow
-7.3 Ford-Fulkerson Algorithm
-7.4 Choosing Good Augmenting Paths
--Choosing Good Augmenting Paths
-7.5 Bipartite Matching
-Homework7
-Lecture note 7
-8.1 Polynomial-Time Reductions
-8.2 Basic Reduction Strategies I
--Basic Reduction Strategies I
-8.3 Basic Reduction Strategies II
--Basic Reduction Strategies II
-8.4 Definition of NP
-8.5 Problems in NP
-8.6 NP-Completeness
-8.7 Sequencing Problems
-8.8 Numerical Problems
-8.9 co-NP and the Asymmetry of NP
--co-NP and the Asymmetry of NP
-Homework8
-Lecture note 8
--Lecture note 8 NP and Computational Intractability
-9.1 Load Balancing
-9.2 Center Selection
-9.3 The Pricing Method: Vertex Cover
--The Pricing Method: Vertex Cover
-9.4 LP Rounding: Vertex Cover
-9.5 Knapsack Problem
-Homework9
-Lecture note 9
--Lecture note 9 Approximation Algorithms
-10.1 Landscape of an Optimization Problem
--Landscape of an Optimization Problem
-10.2 Maximum Cut
-10.3 Nash Equilibria
-10.4 Price of Stability
-Homework10
-Lecture note 10
--Lecture note 10 Local Search
-11.1 Contention Resolution
-11.2 Linearity of Expectation
-11.3 MAX 3-SAT
-11.4 Chernoff Bounds
-Homework11
-Lecture note 11
--Lecture note 11 Randomized Algorithms
-Exam
