algorithm - 这个DAG拓扑重组怎么调用呢？-6ren

algorithm - 这个DAG拓扑重组怎么调用呢？

转载作者：塔克拉玛干更新时间：2023-11-03 02:58:48

25

4

我对有向无环图 (DAG) 很感兴趣，在阅读维基百科上的拓扑排序后，我没有发现任何特别提及涉及层编号的方法(尽管层是在绘图中被广泛提及)。使用这种方法，图形在技术上不是拓扑排序的，但知道每个节点都包含正确的层数(级别)，我们总是可以判断一个特定节点是否比另一个拓扑“更大”。另一方面，只要我们没有有序列表，就无法在拓扑上枚举节点(尽管这可以通过比较节点级别的最终常规排序来完成)。

这种方法允许实现任意连接，同时保持级别信息的正确性。步骤可以是:

对于任何新添加的节点(没有任何连接)应用的级别是 1。
如果请求两个节点之间的连接(从 m 到 n)并且 n.level > m.level 那么它们只是简单地连接起来，不需要为其他节点修复级别。
如果对于请求的连接(从 m 到 n)n.level<=m.level 那么我们将 n.level 更改为 (m.level + 1) 并递归检查 n 的任何依赖项是否有类似的级别增加(或不增加)如果递归步骤上的级别兼容)。
如果我们保留递归输入的节点列表，那么我们可以检测到循环尝试并实现某种撤消操作(将所有受影响节点的级别返回到以前的值)

对于任何一组已知节点和它们之间的连接，我们只需添加所有应用 level=1 的节点，并尝试在它们之间应用所有已知连接(忽略和撤消 cicles)。

最终级别的信息不仅允许在拓扑上比较节点，还包含其他有用的信息。例如:

level = 1 的每个节点都没有传入连接(每条路径都从其中一个开始)。所以任何 DAG 枚举都可以从它们开始。
最长路径(边数)不能长于(最大层数+1)

我想对于一些人工数据(n 个节点，每个 Node(n) 连接到 Node(n + 1))这个算法可能会非常慢。但是对于真实世界的数据，我尝试了它(维基百科类别 - 800,000 个节点 - 2,000,000 个连接)时间不错(5-10 分钟)并且级别和循环尝试的数量很低(369 个级别，1000 次循环尝试)

那么这种方法是新的还是众所周知的，只是没有广泛出现在维基百科和其他资源中？既然不是排序(技术上)，是不是应该叫数据重组？

最佳答案

有一些论文是关于逐步维护图中节点的拓扑顺序的，其中对您描述的算法进行了修改。

如果图形有 n 个节点和 m 条边，则每次插入一条边都会花费 O(m + n) 时间。论文问插入k条边需要多少时间？简单地说，O(k * (n + m))。但事实上，对于足够大的 k，您可以显示更好的上限 - 例如 O(k * sqrt(m + n))。

http://arxiv.org/abs/0802.1059

http://www.siam.org/proceedings/soda/2009/SODA09_120_benderm.pdf

关于algorithm - 这个DAG拓扑重组怎么调用呢？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10152476/

25

4

0

文章推荐： c# - 生成贝尔数算法

文章推荐： java - 如何在小程序中设置Http Proxy

文章推荐： java - 停止 JADE 系统(Java 代理)

文章推荐： algorithm - 最小化颜色 : a variation of the knapsack algorithm?

Javascript AJAX 调用 Jquery 调用
为了让我的代码几乎完全用 Jquery 编写，我想用 Jquery 重写 AJAX 调用。这是从网页到 Tomcat servlet 的调用。我目前情况的类似代码: var http = new
Java 调用 C 调用 Java
我想使用 JNI 从 Java 调用 C 函数。在 C 函数中，我想创建一个 JVM 并调用一些 Java 对象。当我尝试创建 JVM 时，JNI_CreateJavaVM 返回 -1。所以，我想知
javascript - 调用 javascript 函数以从无法按预期工作的表单进行 AJAX 调用
环顾四周，我发现从 HTML 调用 Javascript 函数的最佳方法是将函数本身放在 HTML 中，而不是外部 Javascript 文件。所以我一直在网上四处寻找，找到了一些简短的教程，我可以根
ajax - 为什么我不能从 Angular 调用 ajax 调用
我有这个组件: import {Component} from 'angular2/core'; import {UserServices} from '../services/UserService
openssl - 如果客户端使用 BIO_* 调用，是否需要服务器上的 BIO_* 调用？
我正在尝试用 C 实现一个简单的 OpenSSL 客户端/服务器模型，并且对 BIO_* 调用的使用感到好奇，与原始 SSL_* 调用相比，它允许一些不错的功能。我对此比较陌生，所以我可能会完全错误
javascript - 根据先前的 Ajax 调用，根据用户确认执行 Ajax 调用
我正在处理有关异步调用的难题: 一个 JQuery 函数在用户点击时执行，然后调用一个 php 文件来检查用户输入是否与数据库中已有的信息重叠。如果是这样，则应提示用户确认是否要继续或取消，如果他单击
java - 验证私有(private)构造函数未使用 JMockit 调用/调用
我有以下类(class)。 public Task { public static Task getInstance(String taskName) { return new
c++ - 调用 QSound 调用，它们之间有延迟 Qt C++
嘿，我正在构建一个小游戏，我正在通过制作一个数字 vector 来创建关卡，该数字 vector 通过枚举与 1-4 种颜色相关联。问题是循环(在 Simon::loadChallenge 中)我将颜
Java 异步 api 调用 - 即发即忘 http 调用
我有一个java spring boot api(数据接收器)，客户端调用它来保存一些数据。一旦我完成了数据的持久化，我想进行另一个 api 调用(应该处理持久化的数据 - 数据聚合器)，它应该自行异
c# - 如何从 Paypal 调用 DoDirectPayment API 调用
首先，这涉及桌面应用程序而不是 ASP .Net 应用程序。我已经为我的项目添加了一个 Web 引用，并构建了各种数据对象，例如 PayerInfo、Address 和 CreditCard。但问题
f# - 如何从 FAKE 调用/调用 F# 编译器 fsc？
我如何告诉 FAKE 编译 .fs文件使用 fsc ? 解释如何传递参数的奖励积分，如 -a和 -target:dll . 编辑:我应该澄清一下，我正在尝试在没有 MSBuild/xbuild/.sl
javascript - render 没有被一个 api 调用，而是被另一个 api 调用
我使用下划线模板配置了一个简单的主干模型和 View 。两个单独的 API 使用完全相同的配置。 API 1 按预期工作。要重现该问题，请注释掉 API 1 的 URL，并取消注释 API 2 的
php - OOP 或 MySQL 调用。生成对象还是直接从 MySQL 调用？
我不确定什么是更好的做法或更现实的做法。我希望从头开始创建目录系统，但不确定最佳方法是什么。我想我在需要显示信息时使用对象，例如 info.php?id=100。有这样的代码用于显示 Game.cl
python - child 调用 parent ， parent 调用 child ......或不
from datetime import timedelta class A: def __abs__(self): return -self class B1(A):
java - 调用/调用 void 方法(Java 作业 - 生命游戏示例)
我在操作此生命游戏示例代码中的数组时遇到问题。情况: “生命游戏”是约翰·康威发明的一种细胞自动化技术。它由一个细胞网格组成，这些细胞可以根据数学规则生存/死亡/繁殖。该网格中的活细胞和死细胞通过
调用 read() 返回 0 但缓冲区已更改，调用 fread() 读取相同偏移量时不会发生
如果我像这样调用 read() 来读取文件: unsigned char buf[512]; memset(buf, 0, sizeof(unsigned char) * 512); int fd;
调用 "start"启动程序，调用 "stop"关闭 C 中的当前实例
我用 C 编写了一个简单的服务器，并希望调用它的功能与调用其他 C 守护程序的功能相同(例如使用 ./ftpd start 调用它并使用 ./ftpd stop 关闭该实例)。显然我遇到的问题是我不知
powershell - 可以从 cmd 调用 headless，但不能从 powershell 调用 headless
在 dos 中，当我粘贴此命令时它会起作用: "C:\Program Files (x86)\Google\Chrome\Application\chrome.exe" https://google.
powershell - 可以从 cmd 调用 headless，但不能从 powershell 调用 headless
在 dos 中，当我粘贴此命令时它会起作用: "C:\Program Files (x86)\Google\Chrome\Application\chrome.exe" https://google.
python - 调用 python3 显示错误，调用 python 启动 python2.7
我希望能够从 cmd 在我的 Windows 10 计算机上调用 python3。我已重新安装 Python3.7 以确保选择“添加到路径”选项，但仍无法调用 python3 并使 CMD 启动 P

首页

博学

6Ren·AI

商城

algorithm - 这个DAG拓扑重组怎么调用呢？