最简单的算法对于一些图形操作建议 [英] Suggestions of the easiest algorithms for some Graph operations

问题描述

最后期限为这个项目是收在非常迅速，我没有太多的时间来处理它的左边。因此，寻找最佳的（也可能是更复杂耗时/时间）的算法，而不是，我在找实现在图形结构的一些操作最简单的算法。

是我需要做的操作如下：

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

我的图实现的几个注意事项：

• 在边缘节点有两个属性，一个是类型字符和其他 INT 。他们重新present关系和重量，分别的类型。
• 在该图用链表，同时为顶点和边实施。我的意思是，每个顶点到下一个和每个顶点还指出了一个不同的链表的头部，该特定顶点的边缘。

我知道什么，我需要做什么：

• 我不知道这是最简单的，因为我上面说的，但是对于用户之间的最短路径，我相信，Dijkstra算法是什么人似乎建议pretty的常常让我觉得我要去接着就，随即。
  • 我一直在寻寻觅觅，我发现很难实现这个算法，没有人知道任何教程或东西容易理解所以我可以实现这个算法我自己？如果可能的话，带C源代码code的例子，这将有很大的帮助。我看到很多例子用数学符号，但只是混淆了我，甚至更多。
  • 你认为这将有助于如果我转化图形以邻接矩阵重新present的链接权重和关系类型？难道是更容易执行上，而不是链表的算法？我可以很容易地实现一个功能，在需要的时候做转换。我这样说，因为我的感觉这将是读了几个关于主题页面后更容易，但我可能是错的。
• 在我没有关于其他4个操作的任何意见，建议？

解决方案

  

在给定距离X的图形网络列表中的所有用户。

一个距离 X 从什么？从起始节点或距离 X 它们之间？你能举个例子吗？这可能是也可能不是那么简单做BF搜索或运行Dijkstra算法

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

  

在给定的距离X和关系的类型的曲线网络列表中的所有用户的

见上面。只是因素关系到BFS的类型：如果父的类型比你试图插入到队列中的节点不同，不插入

。

  

计算给出的类型关系的曲线图上的网络用户之间的最短路径

该算法取决于许多因素：

• 您将需要多长时间来计算呢？
• 在多少个节点，你呢？

既然你想轻松，最简单的是罗伊 - 弗洛伊德和Dijkstra的。

• 使用罗伊-弗洛伊德是立方中节点的数量，所以效率不高。只使用这个，如果你能负担得起，一旦运行它，然后回答为O每个查询（1）。使用这个，如果你能负担得起，以保持邻接矩阵在内存中。
• 如果你想保持简单Dijkstra的是二次的节点数目，但你必须要计算两个节点之间的距离，每次运行它​​。如果你想使用Dijkstra的，使用邻接表。

下面是C实现的：罗伊 - 弗洛伊德和的 Dijkstra_1 ，的 Dijkstra_2 。你可以找到很多关于谷歌与＆LT;算法名称＆gt; C实现的。

编辑：罗伊 - 弗洛伊德是出18个节点的问题，因为是邻接矩阵。这将需要太多的时间来建立和太多的记忆。最好的办法是要么使用Dijkstra算法对于每个查询，但preferably实现Dijkstra算法采用堆 - 在我提供的链接，使用堆来找到最小。如果在每个查询运行经典的Dijkstra，这也可能需要很长的时间。

另一种选择是为使用每个查询贝尔曼 - 福特的算法，这将使每次查询您 0（节点*边缘）运行。然而，这是，如果你不执行它作为维基百科告诉你一个很大的高估。相反，使用一个类似于BFS中使用的队列。每当一个节点更新从源的距离，插入该节点返回到队列中。这将是在实践中非常快，而且也将适用于负权重。我建议你​​用非此即彼的Dijkstra算法与堆，因为经典的Dijkstra可能需要很长的时间在18个节点。

  

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

最简单的方法是使用回溯：尝试所有的可能性，并保持发现的最长路径。 这是一个NP完全，所以多项式的解决方案是不存在的。

这是非常糟糕的，如果你有18个节点，我不知道任何的算法（简单或以其他方式），将工作相当快了那么多的节点。考虑使用贪心算法逼近它。或者，也许你的图具有一定的特性，你可以利用的。例如，它是一个DAG（有向无环图）？

  

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

这意味着你要查找的图的直径。要做到这一点最简单的方法是找到每两个节点之间的距离（所有对最短路径 - 无论是运行罗伊 - 弗洛伊德或Dijkstra算法每两个节点之间，并挑选两人配合的最大距离）。

再次，这是很难与你的节点和边的数量做快。我怕你的运气在最后两个问题，除非你的图具有可利用的特殊性能。

  

你是否认为这将有助于如果我转化图形以邻接矩阵重新present的链接权重和关系类型？难道是更容易执行上，而不是链表的算法？我可以很容易地实现一个功能，在需要的时候做转换。我这样说，因为我的感觉这将是读了几个关于主题页面后更容易，但我可能是错的。

没有，邻接矩阵和罗伊 - 弗洛伊德是一个非常糟糕的主意，除非你的应用程序目标的超级计算机。

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?

解决方案

List all users in the graph network given a distance X

A distance X from what? from a starting node or a distance X between themselves? Can you give an example? This may or may not be as simple as doing a BF search or running Dijkstra.

Assuming you start at a certain node and want to list all nodes that have distances X to the starting node, just run BFS from the starting node. When you are about to insert a new node in the queue, check if the distance from the starting node to the node you want to insert the new node from + the weight of the edge from the node you want to insert the new node from to the new node is <= X. If it's strictly lower, insert the new node and if it is equal just print the new node (and only insert it if you can also have 0 as an edge weight).

List all users in the graph network given a distance X and the type of relation

See above. Just factor in the type of relation into the BFS: if the type of the parent is different than that of the node you are trying to insert into the queue, don't insert it.

Calculate the shortest path between 2 users on the graph network given a type of relation

The algorithm depends on a number of factors:

• How often will you need to calculate this?
• How many nodes do you have?

Since you want easy, the easiest are Roy-Floyd and Dijkstra's.

• Using Roy-Floyd is cubic in the number of nodes, so inefficient. Only use this if you can afford to run it once and then answer each query in O(1). Use this if you can afford to keep an adjacency matrix in memory.
• Dijkstra's is quadratic in the number of nodes if you want to keep it simple, but you'll have to run it each time you want to calculate the distance between two nodes. If you want to use Dijkstra's, use an adjacency list.

Here are C implementations: Roy-Floyd and Dijkstra_1, Dijkstra_2. You can find a lot on google with "<algorithm name> c implementation".

Edit: Roy-Floyd is out of the question for 18 000 nodes, as is an adjacency matrix. It would take way too much time to build and way too much memory. Your best bet is to either use Dijkstra's algorithm for each query, but preferably implementing Dijkstra using a heap - in the links I provided, use a heap to find the minimum. If you run the classical Dijkstra on each query, that could also take a very long time.

Another option is to use the Bellman-Ford algorithm on each query, which will give you O(Nodes*Edges) runtime per query. However, this is a big overestimate IF you don't implement it as Wikipedia tells you to. Instead, use a queue similar to the one used in BFS. Whenever a node updates its distance from the source, insert that node back into the queue. This will be very fast in practice, and will also work for negative weights. I suggest you use either this or the Dijkstra with heap, since classical Dijkstra might take a long time on 18 000 nodes.

Calculate the maximum distance between 2 users on the graph network

The simplest way is to use backtracking: try all possibilities and keep the longest path found. This is NP-complete, so polynomial solutions don't exist.

This is really bad if you have 18 000 nodes, I don't know any algorithm (simple or otherwise) that will work reasonably fast for so many nodes. Consider approximating it using greedy algorithms. Or maybe your graph has certain properties that you could take advantage of. For example, is it a DAG (Directed Acyclic Graph)?

Calculate the most distant connected users on the graph network

Meaning you want to find the diameter of the graph. The simplest way to do this is to find the distances between each two nodes (all pairs shortest paths - either run Roy-Floyd or Dijkstra between each two nodes and pick the two with the maximum distance).

Again, this is very hard to do fast with your number of nodes and edges. I'm afraid you're out of luck on these last two questions, unless your graph has special properties that can be exploited.

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.

No, adjacency matrix and Roy-Floyd are a very bad idea unless your application targets supercomputers.

这篇关于最简单的算法对于一些图形操作建议的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！