-
1 votesanswersviews
单根有向无环图循环检测
该图只有一个根 . 它以以下格式保存： 0 -> 1, 0 -> 2, 1 -> 3, 1 -> 4, 2 -> 4, 2 -> 5, 4 -> 5, 5 -> 2 (This is the cycle) 使用Java检测图中是否存在至少一个循环的最有效方法是什么？谢谢！ -
0 votesanswersviews
C中DAG的拓扑分类;用于存储排序列表的数据结构？
我在C中实现了有向无环图的拓扑排序，输出了拓扑排序列表 . 我看到一些实现，其中排序列表存储在 std::stack 中，一些存储在 std::vector 中 . 我不确定哪种或其他数据结构最适合我的情况 . 基本上，我只需循环遍历此排序列表，并提取从上到下存储的元素 . 在提取过程中不会修改列表 . 使用 std::vector 似乎是浪费时间复杂度，因为每次将新元素添加到列表时我都会重新分配... -
20 votesanswersviews
OCaml中的拓扑排序
我正在尝试用ocaml编写拓扑排序，但我是初学者（在OCaml和图算法中），我不能自己做 . 我更容易考虑拓扑排序，例如C（并且在互联网上有很多拓扑排序的例子），但我想学习一些新东西 . 此外，我发现了一些用OCaml编写的拓扑排序的例子，坦白说我不明白它们 . 假设我有一个列表 (int * int list) list ，例如： myList = [(1, [2]); (5, [6; 7]);... -
3 votesanswersviews
针对傻瓜的迭代/动态拓扑排序
我目前正在C中实现动态DAG图 - 将通过UI向用户显示，并且节点/边的插入/移除将是常见操作 . 图表的大小可能从真正的小规模到大规模 - 我的目标是支持数百万个节点 . 因此，我正在寻找一种最佳的数据结构，它不会在内存中占用太多空间，而且还可以通过拓扑排序的节点进行快速插入/删除以及快速多线程迭代（因此需要多个节点）可以并行执行） . 我没有做过任何剖析，看看每次进行修改时重新计算完整图形的拓... -
0 votesanswersviews
算法 - 图深度优先搜索
我正在学习图形和DFS，并试图做一些类似于ANT如何解决依赖关系的事情 . 我对某些事感到困惑，我读到的所有文章似乎都假设每个人都知道这一点 . 我正在考虑使用Map> with key = file，以及value =密钥所依赖的文件集 . DFS算法显示我必须更改节点的颜色（如果它已经被访问过），这意味着对于同一个文件节点的引用必须在密钥中的一个和Set <>中的那个之间相同... -
1 votesanswersviews
解析输入文件以创建有向图C.
所以我正在开始一个关于有向图和拓扑排序的项目 . 我正在寻找解析表单中的课程输入文件的最有效方法： COURSE_1 COURSE_2 其中COURSE_1是COURSE_2的先决条件 NONE COURSE_3 其中COURSE_3没有先决条件 . 显然，所有顶点标签都是字符串 . 我创建了一个带有数据成员的 Graph 类来存储顶点，边和顶点标签 . 稍后，我将添加拓扑排序方法... -
2 votesanswersviews
如何从固定节点开始获取DAG中最长的路径？
我想知道如何从节点0（最小节点）开始在DAG中获取最长路径 我搜索了wiki并得到了以下算法： algorithm dag-longest-path is input: Directed acyclic graph G output: Length of the longest path length_to = array with |V(G)| elements of ... -
0 votesanswersviews
拓扑排序不符合预期
这是我在Python中的图形实现 . 这是一个有向图 . class DiGraph: def __init__(self): self.all_vertices = [] self.vertex_map = {} self.size = 0 def add(self, a, b): if a in self.ve... -
1 votesanswersviews
在算法中正确使用拓扑排序
给定具有N个单词的外来语言的排序字典和标准字典的k个起始字母表，任务是完成返回表示该语言中字符顺序的字符串的函数 . Input: Dict[] = { "baa", "abcd", "abca", "cab", "cad" }, k = 4 Output: Function returns &q... -
0 votesanswersviews
DFS是否可以在图形上进行拓扑排序*和*检测图形是否同时具有循环？
我在关于调度课程的leetcode上做了一个问题（https://leetcode.com/problems/course-schedule/description/#=） 但出于某种原因，我似乎真的很困惑自己 . 我相信这个问题等同于确定它作为图形的表示是否具有拓扑排序 . 但是只有有向非循环图才能进行拓扑排序 - 所以我们要么必须事先检查它是否有一个循环，要么在搜索它并执行拓扑排序时检查它是否... -
4 votesanswersviews
拓扑排序变量算法
我有一组数据，我需要执行拓扑排序，有一些假设和约束，我想知道是否有人知道一个适合于此的现有的，有效的算法 . 已知数据关系形成DAG（因此无需担心周期） . 从A到B的边表示A依赖于B，因此B必须在拓扑排序中出现在A之前 . 图表未必连接;也就是说，对于任何两个节点N和M，可能无法通过跟随边缘从N到M（即使忽略边缘方向） . 数据关系是单独链接的 . 这意味着当存在从A到B的边缘时... -
6 votesanswersviews
拓扑排序是否尝试对顶点或边进行排序？
大家都快乐 . 我目前正在学习拓扑排序，并对拓扑排序尝试排序的问题提出疑问 . Algorithm Design Manual以这种方式描述拓扑排序： 拓扑排序是有向无环图（DAG）上最重要的操作 . 它在一条线上对顶点进行排序，使得所有有向边从左向右 . 这个大胆的部分让我困惑 . 拓扑排序排序顶点或所有有向边也是如此？ 让我们举一个也在书中的例子 . 因此对于上述DAG，我们可以得到拓扑... -
7 votesanswersviews
如果拓扑排序使用DFS，它如何在断开连接的图上成功？
那里's a gap in my knowledge but I'我不确定究竟在哪里 . 可以使用深度优先搜索来完成拓扑排序，如wikipedia explains . 但是我只看到了为树实现的深度优先搜索，其中拓扑排序是针对DAG的 . 是树的一种特殊情况，其中边的隐含方向来自根节点 是用于拓扑排序的算法，而不是真正做DFS，只有很多类似的东西？ 例如，拓扑排序可以处理断开连接的图形... -
1 votesanswersviews
Dijkstra的拓扑排序算法
我在教科书中看到了这段经文： “如果图形是非循环的，我们可以改进Dijkstra算法 . 顶点可以按拓扑顺序选择，因为当选择顶点时，它的距离不能再降低，因为没有来自未知节点的入射边缘 . ” 我理解拓扑排序和Dijkstra的算法，但不理解拓扑顺序如何帮助加速Dijkstra，特别是当订单并不总是唯一时 . （除非它指的是没有意义的空间复杂性） 有人能解释一下如何改进它并举个例子吗？ -
0 votesanswersviews
试图在c中进行拓扑排序的图形？
我正在为图形拓扑排序程序编写代码 . 我已经通过对图形进行深度优先搜索，将每个顶点值放入堆栈，然后从堆栈中弹出值并将其打印出来来实现算法 . 这应该是一个拓扑排序，但到目前为止，我总是得到一个比我输入的顶点数少一个值，并且没有一个数字与我输入的数字相匹配 . status topological_search(graph G, vertex vertex_number, bool visited[... -
14 votesanswersviews
具有目标函数的拓扑排序
我有一个带有N个节点的DAG，即 1, 2, ..., N ，每个节点都有一个权重（我们可以称之为时间） x_1, x_2, ..., x_N . 我想进行拓扑排序，但难点在于排序时我有一个目标函数 . 我的目标函数是最小化几对节点之间的总时间 . 例如，我有一个包含6个节点的DAG，我想要一个特定的拓扑排序，使 (1,3) + (2,4) 最小化，其中 (A,B) 表示两个节点A和B之间的时间... -
3 votesanswersviews
查找字典中字符的优先级
**给定字符串字典[字符串按排序顺序]，您必须根据字典查找字符的优先级 . 吃bxy 根据字典，e排在b之上！** 我尝试用拓扑排序解决这个问题，并编写了下面的代码，它给了我一个e-b-x-y-a-t的输出 . 我无法确定我的解决方案，有什么建议吗？ （这个问题在Google采访中被问到） public static ArrayList<Vertex> topologicalSor... -
4 votesanswersviews
如何调用DAG拓扑重组？
我很长时间对直接无环图（DAG）感兴趣，在阅读维基百科的拓扑排序之后，我没有发现任何涉及 layers numbering 的方法的特别提及（尽管图中广泛提到了绘图） . 使用这种方法，图形在技术上不是拓扑排序的，但是知道每个节点包含层（级别）的正确数字，我们总是可以判断特定节点"bigger"是否在拓扑上 . 另一方面，只要我们没有有序列表，我们就无法在拓扑上枚举节点（尽管这... -
6 votesanswersviews
为什么使用DFS在无向图中查找周期和拓扑排序以在有向图中查找周期？
对于无向图，如果我们需要找到一个循环，我们使用深度优先搜索，如in this older question所述，这是一种众所周知的方法，也是最优的 . 但对于有向图，this other question建议使用拓扑排序 . 我的问题是，为什么我们不能使用我们用于无向图的相同技术来检查有向图中的周期？我已经想到了各种情况，算法似乎总是同意 . 任何人都可以提出一些示例有向图，其中DFS无法找到一个... -
2 votesanswersviews
在我的图形实现中查找边数并执行拓扑排序
我过去几天一直致力于图表实施 . 所有这一切对我来说都是新的，我被困在我实施的两个部分 . 我正在从输入文件中实现课程的图表 . 从文件中，我可以确定哪些课程是其他课程的先决条件 . 然后我创建了一个以图表为节点的图表，以及连接作为先决条件的边缘的边缘 . 我还想找到节点和边的总数，并在图上执行拓扑排序（我稍后将向边添加权重） . 这是我的实施 . Digraph.h class vertex{ ... -
1 votesanswersviews
c＃使用邻接列表的DFS拓扑排序有向图
我试图在下图中完成拓扑排序（摘自Steven Skiena的算法设计手册） .Graph to be Sorted根据book的答案是H，A，B，D，E，G，I，J，C，F但我一直得到A，B，D，E，C，F，H，G，I，J . 我不明白当拓扑排序意味着具有到目标节点的有向边的起始节点应该首先出现时，H如何能够前进到前面 . 书中给出的答案是否可以实现甚至是正确的？这种图形是否可以进行拓扑排序（因...