c# - 非加权有向图上的 BFS。如何返回 A 和 B 之间的路径列表

Question

我有一个用图表表示的网格。每个“节点”称为 Cell。

我想要的输出是一条从 A 到 B 的路径。我在控制台上写了输出，但我发现它是错误的。特别是它似乎产生了一条“跳跃”很多的路径，这意味着从一个节点到下一个节点没有直接链接。

如果工作，我只需要一条从 A 到 B 的路径，而不是到达每个节点的路径。

我的代码有什么问题？

单元格是一个包含 List<Cell> NearCells 的对象引用所有相邻细胞。

    private List<Cell> FindPath(Cell A, Cell B)
    {
        List<Cell> path = new List<Cell>();
        List<Cell> visited = new List<Cell>();

        path.Add(A);

        while (path.Count != 0)
        {
            Cell c = path[0];
            path.RemoveAt(0);

            visited.Add(c);

            if (c == B)
                return path;

            foreach (Cell near in c.NearCells)
            {
                    if (!visited.Contains(near))
                    {
                        visited.Add(near);
                        path.Add(near);
                    }
            }

        }

        return path;
    }

Answer 1

您代码中的路径变量将仅返回您排队但尚未检查的节点，无论如何不代表 A 和 B 之间的路径。为此，您应该创建一个存储每个节点的父节点的映射，当您找到匹配项时，您将遍历该映射直到到达起始节点，同时构建一个列表。然而，此列表将被颠倒，您将需要修复它。

记住这些要点，你应该做这样的事情:

private List<Cell> FindPath(Cell A, Cell B)
{
    var parent = new Dictionary<Cell, Cell>();

    List<Cell> queue = new List<Cell>();
    List<Cell> visited = new List<Cell>();

    queue.Add(A);
    parent.Add(A, null);

    while (queue.Count != 0)
    {
        Cell c = queue[0];
        queue.RemoveAt(0);

        visited.Add(c);

        if (c == B)
            break;

        foreach (Cell near in c.NearCells)
        {                    
            if (!visited.Contains(near))
            {
                parent.Add(near, c);
                visited.Add(near);
                queue.Add(near);
            }
        }
    }

    List<Cell> path = new List<Cell>();

    if(parent.ContainsKey(B))
    {
        Cell backTrack = B;
        do
        {
            path.Add(backTrack);
            backTrack = parent[backTrack];
        }
        while (backTrack != null);
        path.Reverse();
    }
    return path;
}