算法与数据结构之拓扑排序

拓扑排序是对有向无环图DAG中顶点按依赖关系进行的线性排序保证若存在边 u→v则u 必在v之前出现。排序方法拓扑排序的方法非常简单如下从DAG图中选择一个没有前驱入度为0的顶点并输出从图中删除该顶点和所有以它为起点的有向边重复上述两个步骤直到DAG图为空注意当排序过程中有多个入度为0的顶点时可以任意选择故拓扑排序的结果不唯一。例题考点1.若有向图的拓扑排序序列为1则图中每个点的入度和出度最多为1。2.“拓扑序列唯一” ≠ “原图唯一”。3.用领接矩阵存储具有有序拓扑序列的有向图则其领接矩阵必是三角矩阵若不是三角矩阵则图中可能存在环。4.在拓扑排序序列中若顶点在之前则有可能是:G中有一条到的弧G中没有弧但是有一条到的路径比如