对某些Graph操作的最简单算法的建议
这个项目的截止日期很快就会结束，我没有太多时间来处理剩下的事情。 因此，我正在寻找最简单的算法来实现Graph结构上的一些操作，而不是寻找最好的（可能更复杂/耗时）算法。
我需要做的操作如下：
- 在给定距离X的情况下列出图形网络中的所有用户
- 给定距离X和关系类型，列出图形网络中的所有用户
- 在给定一种关系的情况下，计算图形网络上2个用户之间的最短路径
- 计算图形网络上2个用户之间的最大距离
- 计算图形网络上最远的连接用户
关于我的Graph实现的一些注意事项：
- 边节点有2个属性，一个是
char类型，另一个是int。 它们分别代表关系和体重的类型。 - 图表使用链接列表实现，包括顶点和边。 我的意思是，每个顶点指向下一个顶点，每个顶点也指向不同链表的头部，即该特定顶点的边。
我知道我需要做什么：
- 我不知道这是否是最简单的，如上所述，但对于2个用户之间的最短路径，我相信Dijkstra算法是人们似乎经常推荐的，所以我想我会接受它。
- 我一直在搜索和搜索，我发现很难实现这个算法，有没有人知道任何教程或易于理解的东西，所以我可以自己实现这个算法？ 如果可能的话，使用C源代码示例，它会有很大帮助。 我看到许多带有数学符号的例子，但这让我更加困惑。
- 如果我将图形“转换”为邻接矩阵来表示链接权重和关系类型，您认为这会有所帮助吗？ 是否更容易执行该算法而不是链接列表？ 我可以轻松地实现一个函数来在需要时进行转换。 我这样说是因为我觉得在阅读了几页关于这个主题之后会更容易，但我可能是错的。
- 我对其他4个操作，建议没有任何想法？
在给定距离X的情况下列出图形网络中的所有用户
从什么距离X ？ 从起始节点或它们之间的距离X ？ 你能给我举个例子吗？ 这可能或可能不像进行BF搜索或运行Dijkstra那么简单。
假设您从某个节点开始并希望列出距起始距离为X所有节点，只需从起始节点运行BFS即可 。 当您要在队列中插入新节点时，检查从起始节点到要插入新节点的节点的距离是否是从要插入新节点的节点的边缘权重到新节点<= X 如果它严格降低，则插入新节点，如果它相等，则只打印新节点（如果也可以将0作为边缘权重，则仅插入它）。
给定距离X和关系类型，列出图形网络中的所有用户
往上看。 只考虑与BFS的关系类型：如果父类型与您尝试插入队列的节点的类型不同，请不要插入它。
在给定一种关系的情况下，计算图形网络上2个用户之间的最短路径
该算法取决于许多因素：
- 你需要多久计算一次？
- 你有几个节点？
既然你想要轻松，最简单的是Roy-Floyd和Dijkstra’s。
- 使用Roy-Floyd在节点数量上是立方的，因此效率低下。 只有在你能负担得起运行一次然后在O（1）中回答每个查询时才使用它。 如果您能够在内存中保留邻接矩阵，请使用此选项。
- 如果你想保持简单，Dijkstra的节点数是二次的，但每次你想要计算两个节点之间的距离时你都必须运行它。 如果您想使用Dijkstra，请使用邻接列表。
以下是C实现： Roy-Floyd和Dijkstra_1 ， Dijkstra_2 。 你可以在google上找到很多" 。
编辑：对于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)是可接受的运行时间，如果你在网上做某事，这可能不是，并且它需要一些更高功率的机器。
- 在给定距离X的情况下列出图形网络中的所有用户
Djikstra的算法对此有好处，一次性使用。 您可以保存结果以供将来使用，通过线性扫描所有顶点（或者更好的是，排序和二进制搜索）。
- 给定距离X和关系类型，列出图形网络中的所有用户
可能与上面几乎相同 – 只是使用一些function，如果它没有正确的关系，权重将是无穷大。
- 在给定一种关系的情况下，计算图形网络上2个用户之间的最短路径
与上面相同，基本上，如果您匹配这两个用户，请尽早确定。 （或者，您可以“在中间相遇”，如果您在最短的路径上找到某人，则提前终止）
- 计算图形网络上2个用户之间的最大距离
最长的路径是NP完全问题 。
- 计算图形网络上最远的连接用户
这是图表的直径，您可以在Math World上阅读。
至于邻接列表与邻接矩阵问题，它取决于图表的密集程度。 此外，如果要缓存结果，那么矩阵可能就是要走的路。
计算两个节点之间最短路径的最简单算法是Floyd-Warshall 。 它只是循环的三重嵌套; 而已。
它计算O(N^3) 所有最短路径，因此它可能比必要的工作更多，并且如果N很大则需要一段时间。