8

The deadline for this project is closing in very quickly and I don't have much time to deal with what it's left. So, instead of looking for the best (and probably more complicated/time consuming) algorithms, I'm looking for the easiest algorithms to implement a few operations on a Graph structure.

The operations I'll need to do is as follows:

  • List all users in the graph network given a distance X
  • List all users in the graph network given a distance X and the type of relation
  • Calculate the shortest path between 2 users on the graph network given a type of relation
  • Calculate the maximum distance between 2 users on the graph network
  • Calculate the most distant connected users on the graph network

A few notes about my Graph implementation:

  • The edge node has 2 properties, one is of type char and another int. They represent the type of relation and weight, respectively.
  • The Graph is implemented with linked lists, for both the vertices and edges. I mean, each vertex points to the next one and each vertex also points to the head of a different linked list, the edges for that specific vertex.

What I know about what I need to do:

  • 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.
    • I've been searching and searching and I'm finding it hard to implement this algorithm, does anyone know of any tutorial or something easy to understand so I can implement this algorithm myself? If possible, with C source code examples, it would help a lot. I see many examples with math notations but that just confuses me even more.
    • Do you think it would help if I "converted" the graph to an adjacency matrix to represent the links weight and relation type? Would it be easier to perform the algorithm on that instead of the linked lists? I could easily implement a function to do that conversion when needed. I'm saying this because I got the feeling it would be easier after reading a couple of pages about the subject, but I could be wrong.
  • I don't have any ideas about the other 4 operations, suggestions?
4

3 回答 3

8

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

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

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

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

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

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

该算法取决于许多因素：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

于 2010-04-15T17:09:37.227 回答
5

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

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

Djikstra 的算法很适合这个，一次性使用。您可以保存结果以备将来使用，对所有顶点进行线性扫描（或者更好的是，排序和二进制搜索）。

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

可能与上面几乎相同 - 如果它不是正确的关系，只需使用一些权重将是无穷大的函数。

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

与上面相同，本质上，只要尽早确定您是否匹配两个用户。（或者，您可以“在中间相遇”，如果您在最短路径生成树上都找到某人，则提前终止）

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

最长路径是一个NP完全问题。

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

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

至于邻接列表与邻接矩阵的问题，这取决于您的图形的人口密度。此外，如果你想缓存结果，那么矩阵可能是要走的路。

于 2010-04-15T17:04:20.143 回答
1

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

它计算ALL -pairs 中的最短路径O(N^3)，因此它可能会做比必要更多的工作，如果N很大，则需要一段时间。

于 2010-04-15T17:16:18.237 回答