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-FloydDijkstra_1Dijkstra_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 回答