敦案 第七章图 程序设计—数据结构 图的遍历算法及其应用 1)算法1：利用入度 ·增加一个存放顶点入度的数组(indegree),初始反映顶点的实际的入度： ·选择一数据结构（栈或队列）保存入度为0的顶点位置（序号）： ·引入输出顶点的计数器，初始为0 ·循环处理： ·从栈（或队列）中取得一个入度为0的顶点： ·输出该顶点，将输出顶点的计数器加1 ·将该顶点的出边关联的各顶点的入度减1，当入度为0则保存至栈（或队列）： ·图中的所有顶点没有全部输出，则说明有环 2)算法2：DFS 前提条件：有向无环图 算法：在DFS基础上变形，访问完起点的各邻接点后再输出该点。 结果逆拓扑排序。 文档编号 完成时间 完成人张昱 修改时间20026-6 第13页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 13 页 1) 算法 1：利用入度 ·增加一个存放顶点入度的数组( indegree)，初始反映顶点的实际的入度； ·选择一数据结构(栈或队列)保存入度为 0 的顶点位置(序号)； ·引入输出顶点的计数器，初始为 0 ·循环处理： ·从栈(或队列)中取得一个入度为 0 的顶点； ·输出该顶点，将输出顶点的计数器加 1 ·将该顶点的出边关联的各顶点的入度减 1，当入度为 0 则保存至栈(或队列)； ·图中的所有顶点没有全部输出，则说明有环 2) 算法 2：DFS 前提条件：有向无环图 算法：在 DFS 基础上变形，访问完起点的各邻接点后再输出该点。 结果：逆拓扑排序