通过无向无环图找到所有路径

Question

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

    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

我的几乎所有 google 结果都是针对有向图的，我能找到的使它们适用于我的无向图的唯一方法是将每条边添加两次，每个方向一次，我认为这是甚至比我目前无法使用的解决方案还要混乱。

这是我想出的最好的尝试递归遍历图：

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);
    }
}

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

我是新手，才几天就开始使用图形，而且对递归很生疏。我做错了什么？

Answer 1

以下是我如何处理递归遍历。我已将图形设置为顶点名称到邻居列表的字典。此外，由于“开始”以小写字母开头，我只是依靠它来让它不通过那个顶点返回。这里的另一个技巧是将路径传递到当前顶点，以便您可以在每个递归中构建它，但每个递归都不会受到其他递归的影响。因为你有路径，你可以检查它是否包含小写顶点。另请注意，根据图表，我们仍然可以获得无限路径和 Whosebug。例如，如果您的图形将“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

通过无向无环图找到所有路径

Find all paths through an undirected, acyclic graph

c#

recursion

graph-theory