0

我的英语不是很好，但我会尽力在这里解释我的问题。我正在开发一个必须在其中创建图形的应用程序。现在我正在使用GraphStream.

我的图表的要求非常复杂，即：

我有一个名为CDR(Call Data Record)的表，其中有 2 列ANUMBER 和 BNUMBER。表的结构非常清晰，显示了Anumber叫Bnumber，还有一列DATETIME，显示调用的日期和时间。但我这里只需要两列。

假设我们这里有 4 个数字：123, 456 ,789,000，表结构是这样的

Anumber    Bnumber
-------    -------
123        456
123        789
456        789
789        000
456        000

我的表在这里清楚地显示 123 没有调用 000 但 123 调用了 456 和 789 这两个数字称为 000 所以我必须显示 123 和 000 之间的有向图，它可能显示123->456->000如下132->789->000

所以问题是我不知道如何在 123 和 000 之间找到这条路径。可能有超过 2 个数字，比如 5 个或 6 个数字，我必须在所有给定的 5 个或 6 个数字之间找到隐藏的数字以上场景456和789是132到000之间的隐藏数字。

还有一件事，我的表包含超过 2000 万行，将来显然行数会随着用户相互调用而增长得非常快。

到目前为止我做了什么：

我在这个问题上做了一些研发，但找不到任何好的库或任何解决方案。到目前为止，我认为Dijkstra's Algorithm最适合我的场景，因为幸运的是这里GraphStream提供了这个算法。

我想从你们那里得到什么，给我一个想法，这个算法是否会给我所需的结果，或者我必须找到最适合我的问题的任何其他算法或图形库。我不擅长 ALGO，这就是为什么我在这里寻求任何帮助或指导，如果你们可以给我的话。谢谢

4

1 回答 1

0

您根本不需要 Dijkstra 算法，因为您没有边缘成本。你需要简单的BFS算法。这是简单的实现，但您应该添加“标签”数组来标记访问过的节点。因此，在 BFS 之后，您可以恢复从每个节点到源节点的传递（在您的情况下为 123），或者说无法从给定节点访问该节点（如果该节点的标签保持为 0）。您应该通过以下方式添加标签：

所有标签在开始时都等于 0

当您访问新节点时，您将其标签设置为 current_node_label+1

但是，如果您将每个边的成本设置为 1，Dijkstra 可以为您提供帮助。这不是解决问题的有效方法。

于 2017-07-20T12:53:44.723 回答