针对某些图操作的最简单算法的建议

这个项目的截止日期很快就到了，我没有太多时间来处理剩下的事情。因此，我不是寻找最好的（可能更复杂/耗时）算法，而是寻找最简单的算法来实现图结构上的一些操作。

我需要做的操作如下：

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

关于我的 Graph 实现的一些注意事项：

• 边缘节点有2个属性，一个是类型char和另一个int。它们分别代表关系类型和权重。
• 该图的顶点和边都是通过链表实现的。我的意思是，每个顶点都指向下一个顶点，每个顶点还指向不同链表的头，即该特定顶点的边。

我所知道的我需要做什么：

• I don't know if this is the easiest as I said above, but for the shortest path between 2 users, I believe the Dijkstra algorithm is what people seem to recommend pretty often so I think I'm going with that.
  • 我一直在搜索和搜索，发现很难实现这个算法，有谁知道任何教程或易于理解的东西，以便我可以自己实现这个算法？如果可以的话，有C源代码示例，会有很大帮助。我看到很多带有数学符号的例子，但这让我更加困惑。
  • 您认为如果我将图“转换”为邻接矩阵来表示链接权重和关系类型会有帮助吗？在其上执行算法而不是链表会更容易吗？我可以轻松地实现一个函数来在需要时进行转换。我这么说是因为我感觉在阅读了几页有关该主题的内容后会更容易，但我可能是错的。
• 我对其他 4 个操作没有任何想法，有建议吗？

列出给定距离 X 的图网络中的所有用户

一段距离X从何而来？从起始节点或距离X他们之间？你能给个例子吗？这可能会也可能不会像进行 BF 搜索或运行 Dijkstra 那样简单。

假设您从某个节点开始并想要列出具有距离的所有节点X到起始节点，只需运行BFS http://en.wikipedia.org/wiki/Breadth-first_search从起始节点开始。当要向队列中插入新节点时，检查起始节点到要插入新节点的节点的距离是否+要插入新节点的节点到的边的权重新节点X。如果它严格较低，则插入新节点，如果相等，则仅打印新节点（并且仅当边缘权重也可以为 0 时才插入）。

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

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

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

该算法取决于许多因素：

• 您需要多久计算一次？
• 你有多少个节点？

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

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

以下是 C 实现：罗伊-弗洛伊德 http://www.joshuarobinson.net/docs/fwarsh.html and 迪克斯特拉_1 http://snippets.dzone.com/posts/show/4832, 迪克斯特拉_2 http://vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in-c/。你可以在谷歌上找到很多"<algorithm name> c implementation".

Edit:对于 18 000 个节点，Roy-Floyd 是不可能的，邻接矩阵也是如此。构建会花费太多时间和太多内存。最好的选择是对每个查询使用 Dijkstra 算法，但最好使用堆来实现 Dijkstra - 在我提供的链接中，使用堆来查找最小值。如果您对每个查询运行经典的 Dijkstra，这也可能需要很长时间。

另一种选择是使用贝尔曼-福特 http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm每个查询的算法，这会给你O(Nodes*Edges)每个查询的运行时间。然而，如果您没有按照维基百科的要求实现它，那么这就是一个很大的高估。相反，请使用类似于 BFS 中使用的队列。每当一个节点更新其与源的距离时，将该节点插入回队列中。这在实践中会非常快，并且也适用于负权重。我建议您使用此方法或带有堆的 Dijkstra，因为经典的 Dijkstra 可能在 18000 个节点上花费很长时间。

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

最简单的方法是使用回溯：尝试所有可能性并保留找到的最长路径。这是 NP 完全的 http://en.wikipedia.org/wiki/Longest_path_problem，所以多项式解不存在。

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

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

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

同样，对于节点和边的数量来说，这很难快速完成。恐怕您在最后两个问题上运气不佳，除非您的图表具有可以利用的特殊属性。

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

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