检索图中的所有简单路径 [英] Retrieve all simple paths in a graph

问题描述

你好，

我正在尝试使用深度优先搜索来检索无向图中两个给定节点之间的所有简单路径.
我的真正问题是，由于计算时间过长，即使在较小的图形(100个顶点，但各方面都有大量边)的情况下，也无法在生产中使用它，这很快就需要一个多小时.

我的算法如下:

Hello,

I''m trying to retrieve all simple paths between two given nodes in an undirected graph, using depth first search.
My real problem is it is unusable in production due to a too long computation time, even in small graphs (100 vertices but with tons of edges in every ways), it quickly take more an hour.

My algo is the following:

public ICollection<MyObject[]> FindPaths(MyObject sourceObject, MyObject targetObject)
{
    ICollection<MyObject[]> paths = new Collection<MyObject[]>();

    Stack<MyObject> visited = new Stack<MyObject>();
    visited.Push(sourceObject);

    AllSimplePathsDepthFirstSearch(visited, targetObject, paths);

    return paths;
}

private void AllSimplePathsDepthFirstSearch(Stack<MyObject> visited, MyObject target, ICollection<MyObject[]> paths)
{
    MyObject lastVisited = visited.Peek();

    //Explore adjacent edges
    IEnumerable<TaggedEquatableEdge<MyObject, MyRelation> edges = _graph.AdjacentEdges(lastVisited);
    foreach (TaggedEquatableEdge<MyObject, MyRelation> edge in edges)
    {
        MyObject linkedVertice = lastVisited == edge.Source ? edge.Target : edge.Source;
        if (visited.Contains(linkedVertice))
        {
            continue;
        }
        else if (linkedVertice.Equals(target))
        {
            visited.Push(linkedVertice);
            paths.Add(visited.ToArray().Reverse().ToArray());
            visited.Pop();
            continue;
        }
        visited.Push(linkedVertice);
        AllSimplePathsDepthFirstSearch(visited, target, paths);
        visited.Pop();
    }
}

有人知道更好的方法，或者我如何优化它....

在此先感谢您的帮助.

Do somebody know a better approach, or how i could optimize this....

Thanks in advance for your help.

推荐答案

此问题很难解决.一百个顶点足以使任何实现几乎永远运行(直到内存耗尽)，因为它需要计算太多东西.

This problem is NP-hard. Hundred vertices is enough to make any implementation run almost forever (until it runs out of memory) because it needs to compute way too many things.

<br />
| /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\<br />
|S---*---*---*---*---*---*---*---*---*---*---*---*---T<br />
| \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/<br />

上面的40个顶点图中的简单路径数为3 ^ 13，或者1,594,323.拥有100个顶点，它的潜力可能达到数万亿！

P.S.为什么仍然需要所有路径?

The number of simple paths in the 40-vertex graph above is 3^13, or 1,594,323. With 100 vertices it has a potential of going into trillions!

P.S. Why do you need all paths, anyway?

这里有一些不同的算法.如果您发现那些有效的方法，则可以选择.

http://msdn.microsoft.com/library/ms379574.aspx

Some different algorithms here. Your choice if you find those efficient.

http://msdn.microsoft.com/library/ms379574.aspx

这篇关于检索图中的所有简单路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！