问题标签 [graph-traversal]

我正在构建一个词库，使用 aHashMap <String,ArrayList<String>>来保存单词及其同义词（需要此数据结构）。

为了分配的目的，同义关系被认为是传递的。（我们可以把词库想象成一个图表）。我想要完成的是在一个文本文件中打印这个图，每行都有一个连接的组件。换句话说，所有可以合并为同义词的单词都应该放在一行中。

这就是我想象它发生的方式：

打印一个单词及其每个同义词，然后从数据结构中删除这些同义词，这样我们就没有重复的行。

问题当然是我在迭代哈希图的内容时无法删除任何内容。

我缺少任何替代方法吗？

PS我一直保留“图表”的隐喻只是因为我需要标题雄辩而简洁。我知道这个比喻的用处有限。

抽象问题：我有一个大约 250,000 个节点的图表，平均连接性约为 10。找到一个节点的连接是一个漫长的过程（比如说 10 秒）。将节点保存到数据库也需要大约 10 秒。我可以非常快速地检查数据库中是否已经存在节点。允许并发，但一次不超过 10 个长请求，您将如何遍历图表以最快地获得最高覆盖率。

具体问题：我正在尝试抓取网站用户页面。为了发现新用户，我从已知用户那里获取好友列表。我已经导入了大约 10% 的图表，但我一直卡在循环中或使用太多内存来记住太多节点。

我目前的实现：

当前实施的问题：

• 卡在我已经导入的派系中，从而浪费时间并且导入线程处于空闲状态。
• 当他们被指出时会添加更多。

因此，欢迎进行边际改进以及完全重写。谢谢！

首先是的，这是我的 Perl 课程的家庭作业项目。我不是在寻找答案（尽管那会很甜蜜）。据我了解，我需要使用 BFS 和正则表达式来组织我的数据以供使用。我需要一些指导。如何使用 BFS？我是否使用大量堆栈并遍历堆栈中的每个项目？我应该使用一个巨大的哈希表吗？有没有人解决这个问题？你是怎么做的？我只需要一些方向就可以了。这类似于 BST 吗？如果不使用图形模块，这可能吗？这可能使用哈希值吗？

我很好奇是否有一个特定的图算法通过选择一个起始节点然后通过 DFS 来遍历一个未加权的无环有向图。如果遇到具有未搜索前任的节点，则它应该回溯传入路径，直到已经探索了所有要开始的路径。

我找到了一个用于图形算法的维基百科类别，但这里有一小部分算法，我对其中的大多数都不熟悉。

编辑：示例：给定图 {AB, EB, BC, BD}，遍历为：{A,B,E,B,C,D} 或唯一顺序为 {A,B,E,C,D}。请注意，与 BFS 或 DFS 不同，此算法不需要在第一个起始节点的所有路径都用尽的情况下从新的起始节点重新开始。

这可能是一个可能没有最佳解决方案的问题。假设我有一个有向图，不知道它是否有任何循环（循环检测将是这个问题的一个方面）。给定一组顶点（可能是数百万个顶点），我需要计算给定图的所有唯一对之间的所有不同路径（没有重复顶点的路径）。我将如何处理这种情况？

让我们看一个蛮力的方法来做到这一点：

• 从图中计算所有可能的对。

• 对于每对图，使用 DFS 获取从 Source 到 Destination 的所有路径。

• 假设这些对在哈希表中表示，将路径计数作为该对的值。
• 对其余的对重复此操作。

人们能指出哪些事情可能会出错吗？让我们以这种方式思考这个问题，找到地球上所有城市之间的所有不同路径的计算挑战是什么？如果甚至尝试解决这个问题，应该从哪里开始？

编辑：提出的一些算法在 O(n!) 阶乘时间内产生结果。对于资源有限的单台机器来说，这是一个令人生畏的计算。有谁知道 map-reduce 技术可以将图遍历的问题分解成更小的块？

我知道标题有点乱，但我不知道如何更好地解释它。

我正在尝试做的事情：

使用在文本文件中找到的图，找到并打印从顶点 A 到顶点 B 的最短路径（最少顶点数）。

注意：使用广度优先搜索，而不是 Dijkstra 的。

我有什么：

一种在图上应用 BFS 的工作算法，但没有实际打印出最短路径的好方法。

我很难将最短路径中的顶点与仅通过算法运行但不在最短路径中的顶点区分开来。

例如：找到0和4之间的最短路径。0连接到1,2和3。1连接到4。我的路径结果是[0,1,2,3,4]而不是[0,1， 4]。

我还没有找到任何提出相同问题的线程，或者任何包含此问题的 BFS 演练，所以我不确定我是否让这变得比现在更难？

编辑：那些可能感兴趣的人的代码（完全不确定我是否要避免圈子？）

编辑 2：更改了将路径存储到堆栈的方式。

变量和方法的一些解释：

v = 原点

w = 目标顶点

g = 图表

vi = 迭代 v 的邻居的普通迭代器

谢谢阅读！

我正在尝试找出一种遍历 Scala 样式的简洁方法，最好使用 vals 和不可变数据类型。

给定下图，

我希望输出是从给定节点开始的深度优先遍历。例如，从 1 开始，应该 yield 例如1 2 3 0 4。

如果没有可变集合或变量，我似乎无法找到一种很好的方法。任何帮助，将不胜感激。

假设我有一个基于信号流的“程序”图（例如类似于 Simulink 的东西）。即我有一个有向图，有几个起始节点和几个结束节点以及中间的许多节点（希望没有循环关系）

是否有一个好的和/或众所周知的算法（甚至可以作为 Python 库使用）来遍历该图并给我计算顺序？

示例（方向未显示，假设显而易见）：

这应该导致说明/顺序：

谢谢！

我正在设计一个应用程序，它执行一系列插件。插件的执行可能/可能不依赖于另一个/其他插件的执行。即一些（不是全部）插件期望其他插件在它开始执行之前被执行。

我需要导出正确的执行顺序，以便在它所依赖的插件之前不执行任何插件。

我相信图论可以用来解决这个问题（插件作为顶点，依赖作为边，并使用某种遍历导出执行顺序）。

我计划使用 JGraphT，因为该应用程序是用 Java 开发的。

解决此案的任何帮助或指示？？？我并不期待整个 java 代码，任何关于图论（使用算法）的指针都会同样有帮助....

谢谢 ！！！

[解决方案：] @Artium 导致解决方案，这个链接显示了一个非常相似的实现。

我正在寻找一种方法来创建列表或检测密码中的键盘运行。

我可以用密码标准来限制我的问题，例如长度和所需特殊字符的数量。

一个简单的键运行示例可以是“6yhn^YHN”或“zse4ZSE$”。

更复杂的键运行可能有不同的形状，例如“V”或“X”（例如“mko0mju7MKO）MJU&”）

最初的想法是对大型密码转储进行统计分析，并查看仅运行密钥密码的普遍性，但我认为它可以在密码强度强制工具中具有积极的应用。