一些图形操作最简单的算法建议

Question

一些图形操作最简单的算法建议

calgorithmgraphdijkstra

8

这个项目的最后期限即将到来，我没有太多时间处理剩下的事情。所以，我不是在寻找最好（也可能更复杂/耗时）的算法，而是在寻找最简单的算法来实现一个图结构上的几个操作。

我需要执行以下操作：

- 给定距离X，列出图网络中的所有用户。 - 给定距离X和关系类型，列出图网络中的所有用户。 - 给定关系类型，计算图网络上两个用户之间的最短路径。 - 计算图网络上两个用户之间的最大距离。 - 计算图网络上最远的连接用户。

关于我的图实现，有一些注意事项：

- 边节点有两个属性，一个是char类型，另一个是int类型。它们分别表示关系类型和权重。 - 图使用链表实现，对于顶点和边都是如此。我的意思是，每个顶点指向下一个顶点，并且每个顶点还指向另一个链表的头部，该链表存储该特定顶点的边。

关于我需要做什么的了解：

- 对于两个用户之间的最短路径，我不知道是否像我上面说的那样最容易，但我相信Dijkstra算法似乎经常被人们推荐，所以我想选择它。

- 我一直在搜索，但很难实现这个算法，有人知道任何易于理解的教程或东西，可以让我自己实现这个算法吗？如果可能的话，用C源代码示例会很有帮助。我看到了很多数学符号的例子，但那只会让我更加困惑。 - 你认为如果我将图“转换”为邻接矩阵来表示链接权重和关系类型，是否会有帮助？是否在列表上执行该算法比邻接矩阵更容易？当需要时，我可以轻松地实现执行该转换的函数。我之所以这么说，是因为在阅读几页有关此主题的文章后，我有一种感觉，那就是使用邻接矩阵会更容易，但我可能错了。

除了以上操作外，我对其他4个操作没有任何想法，你有什么建议吗？

- rfgamaral

3个回答

5

这假设 O(E log V) 是一个可接受的运行时间，如果您正在进行在线操作，则可能不是这样，并且需要一些更高级的机器。

- 列出距离 X 的图网络中的所有用户 Djikstra's算法对此很好，只用一次。您可以保存结果以备将来使用，通过线性扫描所有顶点（或更好的是，排序和二进制搜索）。

- 列出距离X和关系类型的图网络中的所有用户

几乎与上面相同--只需使用某个函数，其中如果不是正确关系则权重将为无穷大。

- 计算给定关系类型的图网络上2个用户之间的最短路径

本质上与上述相同，只需尽早确定是否匹配两个用户即可。（或者，您可以“在中间见面”，并且如果您找到两个最短路径跨度树上的人，则可以提前终止）

- 计算图网络上2个用户之间的最大距离最长路径是一个NP完全问题。

- 计算图网络上最远的连接用户

这是图的直径，您可以在Math World上了解相关信息。

至于邻接表与邻接矩阵的问题，这取决于您的图有多密集。此外，如果要缓存结果，则矩阵可能是更好的选择。

- Larry

提供的数据样本中有大约18000个顶点和520000个链接。 - rfgamaral

在这种情况下，O（E log V）应该足够好了，你可以将矩阵排序存储（也许可以，但有点多）~ 18000 ^ 2 = ~ 3.24亿，它将使事物更快地收敛，但是对于像Floyd-Warshall这样的算法来说，18000 ^ 3就太大了。 - Larry

1

计算两个节点之间最短路径的最简单算法是Floyd-Warshall。它只是三重嵌套循环；就这样。

它以O(N^3)的时间计算所有对最短路径，因此可能会做比必要更多的工作，并且如果N很大，将需要一段时间。

- polygenelubricants

我不希望那么简单哈哈。这可能需要很多时间，而且我认为教练也不会喜欢。 - rfgamaral

是的，我刚看到了18000个顶点；那肯定行不通。 - polygenelubricants

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

列出距离为X的所有用户在图网络中，需要指定关系类型。从哪里开始距离X？是从起始节点还是它们之间的距离X？你能给一个例子吗？这可能不像简单地执行BF搜索或运行Dijkstra算法那样简单。

假设您从某个节点开始，并且想要列出所有与起始节点距离为X的节点，请从起始节点运行BFS。当您要插入新节点到队列中时，请检查从起始节点到要插入新节点的节点的边权重+从要插入新节点的节点到新节点的边权重是否<= X。如果严格低于，则插入新节点，如果相等，则仅打印新节点（并且仅在您也可以将0作为边权重时才插入它）。

见上文。只需将关系类型考虑到 BFS 中：如果父节点的类型与您要插入队列的节点类型不同，则不要插入。

计算给定关系类型下图网络上2个用户之间的最短路径。

该算法取决于多种因素：

- 您需要多频繁地计算此项操作？ - 您有多少节点？

由于您希望简便易行，因此最简单的方法是 Roy-Floyd 和 Dijkstra 算法。

- 使用 Roy-Floyd 对节点数量来说是立方级别的，效率低下。只有在您可以每次运行一次并在 O(1) 时间内回答每个查询时才使用此选项。如果您可以将邻接矩阵保留在内存中，请使用此选项。 - 如果您想保持简单，Dijkstra 是对节点数量来说二次方级别的，但每次计算两个节点之间的距离时都必须运行它。如果您想使用Dijkstra，请使用邻接表。

这里有C语言实现：Roy-Floyd 和 Dijkstra_1, Dijkstra_2。你可以在谷歌上搜索"<algorithm name> c implementation"来找到更多内容。 编辑： Roy-Floyd算法和邻接矩阵对于18000个节点是不可行的，因为构建时间太长，占用内存太多。你最好使用Dijkstra算法解决每个查询，但最好使用堆来实现Dijkstra - 在我提供的链接中，使用堆查找最小值。如果你在每个查询上运行经典的Dijkstra算法，这也可能需要很长时间。

另一个选择是对每个查询使用 Bellman-Ford 算法，这将为每个查询提供 O(Nodes*Edges) 的运行时间。然而，如果你不像维基百科上所说的那样实现它，这将会是一个很大的高估。相反，使用类似于BFS中使用的队列。每当一个节点更新其到源的距离时，将该节点重新插入队列。这在实践中非常快，并且也适用于负权重。我建议您使用这种方法或带有堆的Dijkstra算法，因为经典的Dijkstra算法可能需要很长时间才能处理18000个节点。

计算图网络上两个用户之间的最大距离

最简单的方法是使用回溯：尝试所有可能性并保留找到的最长路径。这是NP完全问题, 因此不存在多项式解决方案。

如果您有18,000个节点，这将非常糟糕，我不知道任何算法（无论是简单还是复杂）能够在如此多的节点上快速运行。考虑使用贪婪算法进行近似处理。或者也许您的图形具有某些属性，您可以利用它们。例如，它是DAG（有向无环图）吗？

计算图网络中最远连接的用户，意味着要找到图的直径。最简单的方法是找到每两个节点之间的距离（所有对最短路径 - 在每两个节点之间运行Roy-Floyd或Dijkstra，并选择最大距离的两个节点）。

同样，使用您的节点和边缘数量，这很难快速完成。恐怕您在最后两个问题上没有好运，除非您的图具有可以利用的特殊属性。

如果我将图转换为邻接矩阵以表示链接权重和关系类型，您认为这会有帮助吗？在邻接列表上执行操作与在矩阵上执行操作相比，哪一个更容易？当需要时，我可以轻松实现执行此转换的功能。我之所以这么说是因为在阅读了几页有关此主题的信息后，我有一种感觉，认为这样做会更容易，但我可能会错。

除非你的应用程序针对超级计算机，否则邻接矩阵和Roy-Floyd算法都不是一个好主意。