如何修复有向图，使最顶层的父级始终是第一级？

修复有向图，使最顶层的父级始终是第一级的方法是通过拓扑排序算法。

拓扑排序是一种对有向无环图（DAG）进行排序的算法，它可以确定图中节点的线性顺序，使得对于任意的有向边 (u, v)，节点 u 在排序结果中都出现在节点 v 的前面。

以下是修复有向图的步骤：

首先，需要遍历整个有向图，统计每个节点的入度（即指向该节点的边的数量）。可以使用一个字典或数组来保存每个节点的入度信息。
接下来，将入度为 0 的节点加入一个队列中，作为拓扑排序的起始节点。
从队列中取出一个节点，并将其加入结果列表中。然后，遍历该节点的所有邻居节点，将其入度减 1。
如果某个邻居节点的入度减为 0，则将其加入队列中。
重复步骤 3 和步骤 4，直到队列为空。
最后，检查结果列表中的节点数量是否等于有向图中的节点数量。如果不相等，则说明有向图中存在环路，无法进行拓扑排序。

修复有向图后，最顶层的父级始终是第一级。

以下是拓扑排序的应用场景：

任务调度：根据任务之间的依赖关系，确定任务的执行顺序。
编译顺序：根据源代码文件之间的依赖关系，确定编译的顺序。
课程安排：根据课程之间的先修关系，确定学习的顺序。

腾讯云相关产品和产品介绍链接地址：

腾讯云无服务器云函数（SCF）：https://cloud.tencent.com/product/scf
腾讯云容器服务（TKE）：https://cloud.tencent.com/product/tke
腾讯云数据库 MySQL 版（TencentDB for MySQL）：https://cloud.tencent.com/product/cdb-for-mysql
腾讯云云服务器（CVM）：https://cloud.tencent.com/product/cvm
腾讯云人工智能（AI）：https://cloud.tencent.com/product/ai
腾讯云物联网（IoT）：https://cloud.tencent.com/product/iotexplorer
腾讯云移动开发（移动推送、移动分析、移动测试等）：https://cloud.tencent.com/product/mobile
腾讯云对象存储（COS）：https://cloud.tencent.com/product/cos
腾讯云区块链服务（BCS）：https://cloud.tencent.com/product/bcs
腾讯云虚拟专用网络（VPC）：https://cloud.tencent.com/product/vpc
腾讯云安全产品（云防火墙、DDoS 高防等）：https://cloud.tencent.com/product/safety
腾讯云音视频处理（云直播、云点播等）：https://cloud.tencent.com/product/vod

页面内容是否对你有帮助？

有帮助

没帮助

用于有向图中的循环检测的多线程算法

multithreading、algorithm、graph、graph-algorithm

我正在寻找一种并发算法，它可以帮助我在有向图中检测循环。我知道顺序算法使用带着色的dfs，但是我认为它在多线程环境中会失败。有向图的一个例子来说明它： A->(B，C)，B-> (D)，D-> (E)，C-> (E)，E-> (F) A / \ B C | | D | \

浏览 2提问于2012-05-22得票数 11

2回答

使用BFS在有向图中找到圈？

java、graph、cycle

我想标记我访问过的所有节点。当我找到一些设置了标志的节点时，它就会循环。但是这是行不通的，因为一个节点可以有多个父节点和多个子节点。我怎么做才能找到循环呢？ PS:我知道for need更适合DFS，但我需要用BFS来做。

浏览 3提问于2013-09-26得票数 1

1回答

如何将无向图转化为无圈有向图(有向无圈图)

algorithm、graph、language-agnostic、graph-algorithm

我有一个无向图，我想把它转换成有向图。我将没有什么限制，比如已经有了一些有指导的关系。

浏览 2提问于2017-08-18得票数 0

4回答

为什么有向无圈图中的最长路径需要拓扑排序？

graph、topological-sort、longest-path

问题:给定一个加权有向无圈图(DAG)和其中的一个源顶点，求出从s到给定图中所有其他顶点的最长距离。请找到参考图：为什么我们需要拓扑排序？我们不能简单地从源顶点使用修改后的BFS吗？为什么我们这么关心线性排序。如果这是重复，那么请将我转到相关的答案。谢谢

浏览 3提问于2014-12-23得票数 12

回答已采纳

1回答

具有拓扑排序的Dijkstra算法

algorithm、dijkstra、shortest-path、topological-sort

我在一本教科书里看到了这段话：如果图是无圈的，我们可以改进Dijkstra的算法。顶点可以按拓扑顺序选择，因为当选择顶点时，它的距离不能再降低，因为没有来自未知节点的传入边。我理解拓扑排序和Dijkstra的算法，但不知道拓扑顺序如何帮助加快Dijkstra的速度，特别是当顺序并不总是唯一的时候。(除非它指的是空间的复杂性，这也是毫无意义的) 有人能解释一下它是如何改进的吗?举一个例子。

浏览 3提问于2017-01-07得票数 1

回答已采纳

1回答

如何在有向无环图中找到“5”条最重要的路径？

algorithm、directed-acyclic-graphs

我有一个有向无环图(DAG)，每个节点都有一个相关的权重。我想找出前'n‘个(例如5个)权重最大的路径，其中路径的权重定义为其节点的所有权重的总和。我如何才能做到这一点呢？准确性是可取的，但可以牺牲性能。潜在地，图可以具有10,000+节点和/或边。编辑:权重将是大于或等于零的数字。

浏览 0提问于2012-11-06得票数 2

回答已采纳

1回答

将无向循环图投影到坐标平面上

algorithm、graph、path、shortest-path、undirected-graph

我有一个集合的房间，每个房间是连接到一个或多个其他房间通过主要方向(北，南，东，西)。这些房间是以这样的方式连接起来的，如果A在B的西边，那么B就在A的东边；因此没有向图。现在我需要把这些房间收集起来，并在坐标平面上绘制它们的图形。所有的边必须平行于X或Y轴。我尝试过一些不同的方法，但我认为迄今为止最有效的方法如下：找到“中心”并指定它(0,0) (每个房间最短路径的长度之和最小)。我不知道这是否真的有必要，但它使输出的中心更容易。走出中心C，对遇到的每一个房间，指定一个坐标(X，Y)，其中P是连接C=>R的路径，在坐标平面上产生最大的位移，X是沿P的净水平移动，Y是沿P的

浏览 4提问于2017-01-12得票数 1

3回答

使用BFS进行拓扑排序

algorithm、breadth-first-search

广度优先搜索可以用于寻找图中顶点和强连通分支的拓扑排序吗？如果是，该怎么做呢？如果不是，为什么不呢？我们通常在这些问题中使用深度优先搜索，但如果我尝试使用BFS实现，会出现什么问题？像这样的代码可以工作吗？ def top_bfs(start_node): queue = [start_node] stack = [] while not queue.empty(): node = queue.dequeue() if not node.visited: node.visited = True

浏览 4提问于2014-08-10得票数 16

回答已采纳

1回答

为什么要使用DFS来查找无向图中的圈，使用拓扑排序来查找有向图中的圈？

algorithm、graph、depth-first-search、topological-sort

对于无向图，如果我们需要找到一个圈，我们使用深度优先搜索，如所述，这是一种众所周知的方法，也是最优的。但对于有向图，建议使用拓扑排序。我的问题是，为什么我们不能使用我们用于无向图的相同技术，来检查有向图中的圈？我考虑过各种情况，算法似乎总是一致的。有没有人能想出一些有向图的例子，其中DFS找不到圈，但拓扑排序找到了？

浏览 3提问于2013-05-28得票数 6

回答已采纳

1回答

如何为一个大型的、完整的欧几里得加权图生成一个排序的边列表？

algorithm、graph

我有一个完整的欧几里德图(即，边权重由节点之间的欧几里德距离确定，节点位于2D空间中)，它太大(~100k个节点)，无法在内存中存储完整的边列表。有没有办法让我按照边权重的顺序生成边？如果我可以将边列表放入内存中，我只需要创建一个边长度列表，然后进行排序(总时间= O(V^2 * edge ))。否则，除了在一些未知的算法中使用KDTree之外，我不知道该如何做。

浏览 1提问于2014-03-20得票数 0

1回答

拓扑排序基本类比

graph-algorithm、topological-sort

我最近经历了CRLS的拓扑排序和DFS。他们有一个进入/退出时间的概念，通过这个概念，我们可以将图的边分类为树边前向边后沿交叉边因此，问题是-使用DFS的拓扑排序是否尝试从树中删除前向边缘，只保留树的边缘以得到排序的结果？

浏览 5提问于2021-10-22得票数 0

4回答

有向图线性算法

dynamic-programming、graph-algorithm、directed-acyclic-graphs

我想知道用动态规划在线性时间内计算顶点s和图中每一个其他顶点之间最短路径长度的最佳方法。该图是加权的DAG。

浏览 1提问于2016-03-03得票数 0

2回答

如何在拓扑排序中忽略循环？

javascript、algorithm、sorting、graph

我正在使用对JS中的图执行拓扑排序。问题是，在极少数情况下，图中会包含圈。这些都是结构的次要部分，因此丢弃一些边缘不会对最终结果产生太大影响。然而，当它们出现时，算法就会中断。更新它的最有效方法是什么，这样如果有一两个周期，它就不会崩溃？

浏览 3提问于2013-08-17得票数 1

1回答

指派问题:求作业序列的最小数目

algorithm、assignment-problem

我有N不同的工作。有些工作是可以连续完成的。需要排列连续的作业以形成作业序列，使得作业序列M的数量最小。问题在于最大基数匹配的形式。但是，确定当最大基数匹配时，作业序列的数量是最小的吗？我正在寻找一种算法来解决这个问题。示例 N=6 可以执行以下工作：然后，作业1可以转到作业2、5。然后，作业2可以转到作业3。然后，作业4可以转到作业2、5。然后，作业5可以转到作业6。执行作业分配，我们得到以下两个作业序列： 1-2-3 4-5-6 然后是M=2。这可以看作是寻找进行所有飞行(工作)的最小机组人员数量的问题。

浏览 2提问于2021-09-04得票数 0

3回答

检查拓扑排序的有效性

graph、topological-sort

给定以下有向图：我将拓扑排序确定为0, 1, 2, 3, 7, 6, 5, 4，每个节点的值为： d[0] = 1 f[0] = 16 d[1] = 2 f[1] = 15 d[2] = 3 f[2] = 14 d[3] = 4 f[3] = 13 d[4] = 7 f[4] = 8 d[5] = 6 f[5] = 9 d[6] = 5 f[6] = 10 d[7] = 11 f[7] = 12 其中d是发现时间，f是完成时间。如何检查拓扑排序是否有效？

浏览 0提问于2019-01-14得票数 1

6回答

如何在不创建循环的情况下向有向无圈图添加边

java、algorithm、graph、directed-acyclic-graphs

我有一个有向边和无向边的图，现在我想用有向边代替这些无向边(每个无向边变成一个有向边)。对于每个无向边缘有两种可能性(用一个方向或另一个方向的有向边替换它)。如何确定无向边的方向，使我的图保持无圈？我的方法：创建一个只有有向边的图，并在后面添加1×1(作为有向边)的无向边。现在我有了一个，我的问题是将有向边添加到图中，同时保持DAG属性(只有有向边，没有循环)。如何向DAG添加边，并确保生成的图形也是DAG？

浏览 16提问于2017-05-14得票数 3

回答已采纳

1回答

拓扑排序中的输入和输出帮助

java、algorithm、graph、topological-sort

public class Problem3 { public static void main (String [] args){ Scanner sc= new Scanner (System.in); System.out.println("Enter no. of Islands"); int n= sc.nextInt(); Graph g = new Graph (n); System.out.println("Enter no. of one-way bridges

浏览 4提问于2020-06-15得票数 0

6回答

如何在O(n+m)中找到有向图的母点？

algorithm、graph-theory

有向图G= (V，E)中的母点是一个顶点v，使得从v到G的一条有向路可以到达所有其它顶点。给出了一个O(n+m)算法来检验图G是否包含母点。 (c)来自Skiena手册仅找到O(n(n+m))方式

浏览 0提问于2010-11-30得票数 7

1回答

一种基于成对关系的队列一致性检测算法

algorithm、graph、queue、consistency、pairwise

我们有n个项目进入和离开一个队列，他们可以在任何时候进入和离开。我们所拥有的信息是，对于每一对(a，b)，我们知道1) a在b进入队列之前离开队列，反之亦然；2)在某个时刻，a和b同时在队列中。或者3)完全没有信息。假设我们得到了所有(n选择2)对的成对信息列表，找到一个O(n^2)算法来确定信息中是否存在任何不一致。例如，a在b进入之前离开(为了简单起见，将其记为a>b)，b>c和c=a是不一致的，因为没有a、b、c进入和离开队列的可能时间线，这使得所有三个语句都为真。我想把这个问题变成一个图的遍历问题，每一项都是一个顶点，成对关系是一个边，如果是a>b或b<a，那

浏览 6提问于2021-03-19得票数 1

7回答