Prim's Algorithm迷宫生成为何需要二次检查单元格是否已在迷宫中

我正按照教程在迷宫生成器中实现Prim's Algorithm，目前功能正常，但代码中有一处额外校验逻辑我不清楚其必要性。

我的算法逻辑如下：

• 用列表maze存储已加入迷宫的单元格，先将起始单元格加入maze
• 维护frontiers列表存储边界单元格（即已在迷宫中单元格的相邻未加入单元格），每次随机选取一个边界单元格chosenFrontier
• 找出chosenFrontier所有已在maze中的相邻单元格，随机选一个打通墙壁，将chosenFrontier加入maze、从frontiers中移除，再将它的未加入maze的相邻单元格加入frontiers列表

我在向frontiers添加单元格时已经通过if (neighbour.Cell != null && !maze.Contains(neighbour.Cell))做了过滤，仅添加不在maze中的单元格。但如果我不对选中的chosenFrontier额外做是否已在maze中的校验，算法就会出错，会出现所有相邻单元格都已加入迷宫的情况下仍判定存在有效边界单元格的问题。

为什么需要这层二次校验？明明添加到frontiers时已经做了过滤，问题出在哪里？以下是我的代码：

private IEnumerator PrimsAlgorithm(Cell startingCell)
{
    List<Cell> maze = new List<Cell>();
    maze.Add(startingCell);
    startingCell.Visit();
        
    // Determine starting cell's frontier cells
    List<Neighbour> frontiers = new List<Neighbour>();
    foreach(Neighbour neighbour in startingCell.GetNeighbours())
    {
        if (neighbour.Cell != null && !maze.Contains(neighbour.Cell))
        {
            frontiers.Add(neighbour);
        }
    }

    yield return new WaitForSeconds(stepSize);
    startingCell.Leave();

    // While there are frontier cells,
    while (frontiers.Count > 0)
    {
        // Choose a random frontier from the list
        Neighbour chosenFrontier = frontiers[random.Next(frontiers.Count)];

        if (maze.Contains(chosenFrontier.Cell))
        {
            // ----- Why is this neccessary??? -----
            frontiers.Remove(chosenFrontier);
        }
        else
        {
            // Determine the frontier cells's possible neighbours
            // Possible neighbours are only cells that are already part of the maze.
            Neighbour[] chosenFrontierNeighbours = chosenFrontier.Cell.GetNeighbours();
            List<Neighbour> adjacentInMazeNeighbours = new List<Neighbour>();
            foreach (Neighbour chosenFrontierNeighbour in chosenFrontierNeighbours)
            {
                if (chosenFrontierNeighbour.Cell != null && maze.Contains(chosenFrontierNeighbour.Cell))
                {
                    adjacentInMazeNeighbours.Add(chosenFrontierNeighbour);
                }
            }

            // Choose a random neighbour from the possible neighbours
            if (adjacentInMazeNeighbours.Count > 0)
            {
                Neighbour chosenInMazeNeighbour = adjacentInMazeNeighbours[random.Next(adjacentInMazeNeighbours.Count)];

                // Connect the frontier cell to their new neighbour (and the other way around)
                maze.Add(chosenFrontier.Cell);
                chosenFrontier.Cell.Visit();
                chosenFrontier.Cell.AddConnection(chosenInMazeNeighbour.Dir);
                chosenInMazeNeighbour.Cell.AddConnection(GetOppositeDir(chosenInMazeNeighbour.Dir));
                // Remove the frontier from the set
                frontiers.Remove(chosenFrontier);

                // Determine the chosenFrontiers' possible neighbours and add them to the list of frontiers.
                // Possible neighbours are cells that exist and aren't yet contained in the maze.
                // These become the new frontier nodes.
                foreach (Neighbour neighbour in chosenFrontier.Cell.GetNeighbours())
                {
                    if (neighbour.Cell != null && !maze.Contains(neighbour.Cell))
                    {
                        frontiers.Add(neighbour);
                    }
                }
            }
            // Wait to show this iteration
            yield return new WaitForSeconds(stepSize);
            // Leave current cell
            chosenFrontier.Cell.Leave();
        }
    }
    yield return new WaitForSeconds(stepSize);
}

下图是保留该校验逻辑时算法正常运行的效果：

下图是移除校验逻辑后算法出错的效果：

原因解答 #

核心问题出在你用了允许重复元素的List类型存储边界单元格：
同一个未加入迷宫的单元格，可能作为多个已加入迷宫单元格的邻居，被多次添加到frontiers列表里。比如已经加入迷宫的A、B两个单元格相邻，它们的共同邻居C还没加入迷宫，那么C会在A被处理时加一次到frontiers，B被处理时又加一次，frontiers里就会存在两个指向C的条目。
当C第一次被选中处理时，你会把它加入maze，并且移除当前选中的这一个C条目，但另一个重复的C条目还留在frontiers里。后续如果随机选到了这个重复条目，对应的C单元格已经在maze中，没有校验的话就会尝试对已经加入迷宫的单元格重复执行处理逻辑，自然就会出现错误。
你添加的这层校验本质就是在清理frontiers里残留的无效重复条目，避免重复处理已经加入迷宫的单元格。如果想要去掉这层校验，可以把frontiers换成自动去重的集合类型，或者在添加新边界单元格时额外判断它是否已经存在于frontiers中，从源头避免重复加入即可。

内容的提问来源于stack exchange，提问作者KamielDev