拓扑排序与最短路径：从DAG到ACM算法详解

本资源是一份关于拓扑排序和最短路径的讲解文档，由赵予唯针对ACM俱乐部2018级的学生进行分享。拓扑排序主要涉及有向无环图（DAG）的概念，它是判断图是否存在有序遍历的一种方法。在DAG中，如果存在拓扑序，意味着从任意一个顶点出发，沿着箭头方向，每个节点都有后继节点，且没有循环。例如，对于给定的图，可能存在多个不同的拓扑序，如023145或012345，其中后者是唯一的。 拓扑排序的算法步骤包括： 1. 初始化入度数组，统计每个节点的入度。 2. 创建一个队列，将所有入度为0的节点放入。 3. 当队列非空时，取出队首节点P，遍历其相邻节点Q，将Q的入度减一。 4. 如果Q的入度变为0，将其加入队列。 5. 出列的顺序即为拓扑序。若队列为空而未遍历完所有节点，说明不存在拓扑序。 此外，文档还介绍了如何利用拓扑排序求解最短路径问题。通过模仿广度优先搜索（BFS），设置dis数组记录每个节点到起点的距离，初始值设为正无穷，起点距离为0。在拓扑排序过程中，每次更新距离时，根据公式dis[to]=min(dis[to],dis[from]+value)进行计算。完成后，dis数组中的值即为最短路径长度。 然而，在实际应用BFS时，例如在示例图中，由于BFS的特性（即访问过的节点不会再次加入队列），可能导致部分节点的最短路径计算错误。例如，节点2的最短路径被错误地认为是从1到4，而不是1到2。修正方法是忽略vis数组，确保在距离更新时重新加入队列，以确保完整且准确地计算最短路径。 总结来说，这份文档涵盖了拓扑排序的基本概念、算法实现以及其在求解最短路径问题中的应用，特别强调了在处理无权图时，BFS策略的局限性和修正方法。通过学习和理解这些内容，可以帮助读者掌握这两个关键的图论概念及其在实际问题中的运用。