c/c++语言开发共享对某些Graph操作的最简单算法的建议

在给定距离X的情况下列出图形网络中的所有用户

从什么距离X ？ 从起始节点或它们之间的距离X ？ 你能给我举个例子吗？ 这可能或可能不像进行BF搜索或运行Dijkstra那么简单。

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

给定距离X和关系类型，列出图形网络中的所有用户

往上看。 只考虑与BFS的关系类型：如果父类型与您尝试插入队列的节点的类型不同，请不要插入它。

在给定一种关系的情况下，计算图形网络上2个用户之间的最短路径

该算法取决于许多因素：

既然你想要轻松，最简单的是Roy-Floyd和Dijkstra’s。

以下是C实现： Roy-Floyd和Dijkstra_1 ， Dijkstra_2 。 你可以在google上找到很多" c implementation" 。

编辑：对于18000个节点，Roy-Floyd是不可能的，因为它是一个邻接矩阵。 构建和占用太多内存需要花费太多时间。 您最好的选择是为每个查询使用Dijkstra算法，但最好使用堆实现Dijkstra – 在我提供的链接中，使用堆来查找最小值。 如果您在每个查询上运行经典Dijkstra，那也可能需要很长时间。

另一个选择是在每个查询上使用Bellman-Ford算法，这将为每个查询提供O(Nodes*Edges)运行时。 但是，如果你没有像维基百科告诉你的那样实​​现它，这是一个很大的高估。 而是使用类似于BFS中使用的队列。 每当节点更新其与源的距离时，将该节点插回队列。 这在实践中将非常快，并且也适用于负权重。 我建议你使用这个或Dijkstra堆，因为经典的Dijkstra可能需要很长时间在18 000个节点上。

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

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

如果你有18 000个节点，这真的很糟糕，我不知道任何算法（简单的或其他的）对于这么多节点都能合理地运行。 考虑使用贪心算法逼近它。 或者您的图表可能具有某些可以利用的属性。 例如，它是DAG（有向无环图）吗？

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

意思是你想要找到图的直径。 最简单的方法是找到每两个节点之间的距离（所有对最短路径 – 在每两个节点之间运行Roy-Floyd或Dijkstra，并选择具有最大距离的两个节点）。

同样，使用您的节点数和边数很难快速完成。 我担心你在最后两个问题上运气不好，除非你的图表具有可被利用的特殊属性。

如果我将图形“转换”为邻接矩阵来表示链接权重和关系类型，您认为这会有所帮助吗？ 是否更容易执行该算法而不是链接列表？ 我可以轻松地实现一个函数来在需要时进行转换。 我这样说是因为我觉得在阅读了几页关于这个主题之后会更容易，但我可能是错的。

不，邻接矩阵和Roy-Floyd是一个非常糟糕的主意，除非你的应用程序针对超级计算机。

这假设O(E log V)是可接受的运行时间，如果你在网上做某事，这可能不是，并且它需要一些更高功率的机器。

Djikstra的算法对此有好处，一次性使用。 您可以保存结果以供将来使用，通过线性扫描所有顶点（或者更好的是，排序和二进制搜索）。

可能与上面几乎相同 – 只是使用一些function，如果它没有正确的关系，权重将是无穷大。

与上面相同，基本上，如果您匹配这两个用户，请尽早确定。 （或者，您可以“在中间相遇”，如果您在最短的路径上找到某人，则提前终止）

最长的路径是NP完全问题 。

这是图表的直径，您可以在Math World上阅读。

至于邻接列表与邻接矩阵问题，它取决于图表的密集程度。 此外，如果要缓存结果，那么矩阵可能就是要走的路。

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

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

需要了解更多c/c++开发分享对某些Graph操作的最简单算法的建议，也可以关注C/ C++技术分享栏目—计算机技术网(www.ctvol.com)!