通过无向无循环图查找所有路径

提问者：小点点

通过无向无循环图查找所有路径

我试图通过下图找到所有路径：

    start
    /   \
c--A-----b--d
    \   /
     end

它只是非循环的，因为小写名称的顶点只能被访问一次，例如顶点d不应该被访问，因为要将其包含在图的路径中，顶点b必须被访问两次。

通过图的所有允许路径是：

start,A,b,A,c,A,end
start,A,b,A,end
start,A,b,end
start,A,c,A,b,A,end
start,A,c,A,b,end
start,A,c,A,end
start,A,end
start,b,A,c,A,end
start,b,A,end
start,b,end

几乎我所有的谷歌搜索结果都是针对有向图的，我能找到的唯一方法是在我的无向图中添加每一条边两次，每一个方向添加一次，我认为这比我目前的非工作解决方案还要混乱。

我想出的最好的方法是通过图进行递归遍历：

private HashSet<List<Edge>> paths = new();
private List<Edge> _path = new();
HashSet<Vertex> smallsVisited = new HashSet<Vertex>();
private void Traverse(Vertex start)
{
    var traverseEnd = GetVertexByName("end");
    if (start == traverseEnd)
    {
        paths.Add(_path.ToList());
        _path.Clear();
        return;
    }

    if (smallsVisited.Contains(start))
        return;

    if (start.Name != "start" && char.IsLower(start.Name[0]))
        smallsVisited.Add(start);

    var traverseStart = GetVertexByName("start");
    var neighbours = _adjacencyList[start].Where(v => v != traverseStart);
    foreach (var end in neighbours)
    {
        _path.Add(new Edge(start, end));
        Traverse(end);
    }
}

我调用transverse，并使用名为start的顶点来设置进程滚动。当参数start是名为end的顶点时，我希望遍历停止，但结果只有一条路径，即顶点start到顶点b。

我是一个非常新的，只有几天的时间，来处理图形，并且对递归非常生疏。我做错了什么？

共1个答案

匿名用户

下面是我如何处理使用递归遍历的方法。我已经将该图设置为一个顶点名称字典，并添加到一个邻域列表中。而且因为“开始”是以小写字母开头的，所以我只能依靠它，不让它回到顶点。这里的另一个技巧是将路径传递到当前顶点，以便在每次递归中都可以在此基础上进行构建，但每个递归都不受其他递归的影响。既然你有路径，你可以检查它是否包含小写顶点。还要注意的是，我们仍然可以根据图获得无限路径和堆栈溢出。例如，如果您的图形将“b”更改为“b”，那么您可以在“a”和“b”之间移动无限次，而此代码不会以任何方式检测到这一点。

void Main()
{
    var graph = new Dictionary<string, List<string>>
    {
        ["start"] = new List<string>{"A", "b"},
        ["A"] = new List<string>{"c", "b", "end", "start"},
        ["b"] = new List<string>{"A", "d", "end", "start"},
        ["c"] = new List<string>{"A"},
        ["d"] = new List<string>{"b"},
        ["end"] = new List<string>{"A", "b"},
    };
    
    var result = Traverse(graph, "start", "end");

    foreach(var x in result)
    {
        Console.WriteLine(string.Join("-", x));
    }
}

public static IEnumerable<IEnumerable<string>> Traverse(
    Dictionary<string, List<string>> graph, 
    string current, 
    string end, 
    IEnumerable<string> path = null)
{
    // Initialize the path if we don't have one yet.
    path ??= Enumerable.Empty<string>();
    
    // Do not allow the path to go to a lower cast vertex 
    // more than once.
    if(char.IsLower(current[0]) && path.Contains(current))
    {
        yield break;
    }
    
    path = path.Append(current);
    
    // If we are at the end then return the path and break.
    if(current == end)
    {
        yield return path;
        yield break;
    }
    
    // Find all the paths from the current vertex through
    // each of it's neighbors and return them.
    foreach(var neighbor in graph[current])
    {
        foreach(var subPath in Traverse(graph, neighbor, end, path))
        {
            yield return subPath;
        }   
    }   
}

结果是

start-A-c-A-b-A-end
start-A-c-A-b-end
start-A-c-A-end
start-A-b-A-c-A-end
start-A-b-A-end
start-A-b-end
start-A-end
start-b-A-c-A-end
start-b-A-end
start-b-end