algorithm - 循环查找算法

Question

我需要找到一个在给定点开始和结束的循环。不能保证它存在。我使用 bool[,] points 来表示哪个点可以在循环中。点只能在网格上。 points 表示网格上的给定点是否可以循环。我需要使用最少的点数找到这个循环。一个积分只能使用一次。连接只能是垂直或水平的。

让这成为我们的观点(红色是起点):

删除无效的 ImageShack 链接

我意识到我可以做到:

while(numberOfPointsChanged)
{
    //remove points that are alone in row or column
}

所以我有:

删除无效的 ImageShack 链接

现在，我可以找到路径了。

删除无效的 ImageShack 链接

但是如果有点没有被这个循环删除但不应该在路径中怎么办？

我写过代码:

class MyPoint
{
    public int X { get; set; }
    public int Y { get; set; }
    public List<MyPoint> Neighbours = new List<MyPoint>();
    public MyPoint parent = null;
    public bool marked = false;
}

    private static MyPoint LoopSearch2(bool[,] mask, int supIndexStart, int recIndexStart)
    {
        List<MyPoint> points = new List<MyPoint>();

        //here begins translation bool[,] to list of points
        points.Add(new MyPoint { X = recIndexStart, Y = supIndexStart });

        for (int i = 0; i < mask.GetLength(0); i++)
        {
            for (int j = 0; j < mask.GetLength(1); j++)
            {
                if (mask[i, j])
                {
                    points.Add(new MyPoint { X = j, Y = i });
                }
            }
        }

        for (int i = 0; i < points.Count; i++)
        {
            for (int j = 0; j < points.Count; j++)
            {
                if (i != j)
                {
                    if (points[i].X == points[j].X || points[i].Y == points[j].Y)
                    {
                        points[i].Neighbours.Add(points[j]);
                    }
                }
            }
        }
        //end of translating

        List<MyPoint> queue = new List<MyPoint>();
        MyPoint start = (points[0]); //beginning point
        start.marked = true; //it is marked
        MyPoint last=null;   //last point. this will be returned
        queue.Add(points[0]);


        while(queue.Count>0)
        {
            MyPoint current = queue.First(); //taking point from queue
            queue.Remove(current);           //removing it

            foreach(MyPoint neighbour in current.Neighbours) //checking Neighbours
            {
                if (!neighbour.marked) //in neighbour isn't marked adding it to queue
                {
                    neighbour.marked = true;
                    neighbour.parent = current;
                    queue.Add(neighbour);
                }
                //if neighbour is marked checking if it is startig point and if neighbour's parent is current point. if it is not that means that loop already got here so we start searching parents to got to starting point
                else if(!neighbour.Equals(start) && !neighbour.parent.Equals(current))
                {                        
                    current = neighbour;
                    while(true)
                    {
                        if (current.parent.Equals(start))
                        {
                            last = current;
                            break;
                        }
                        else
                            current = current.parent;

                    }
                    break;
                }
            }
        }

        return last;            
    }

但它不起作用。它找到的路径包含两个点:起点和它的第一个邻居。
我做错了什么？

编辑:忘了说了。。。水平连线后还要有竖线，横线，竖线等等。。。更重要的是，在每一行和每一列中，循环中最多需要两个点(两个或没有)。但是这个条件和“周期必须是最短的周期”是一样的。

Answer 1

首先，您应该将表示更改为更高效的表示。您应该使顶点成为一个结构/类，它保留连接顶点的列表。

更改表示后，您可以使用 breadth-first search 轻松找到最短周期.

您可以使用以下技巧加快搜索速度:按广度优先顺序遍历图，标记遍历的顶点(并在每个顶点的根路径上存储“父顶点”编号)。一旦找到一个已经标记的顶点，搜索就结束了。您可以通过返回存储的“父”顶点来找到从找到的顶点到根的两条路径。

---

编辑:
你确定你的代码是正确的？我尝试了以下方法:

while (queue.Count > 0)
{
    MyPoint current = queue.First(); //taking point from queue
    queue.Remove(current);           //removing it

    foreach (MyPoint neighbour in current.Neighbours) //checking Neighbours
    {
        if (!neighbour.marked) //if neighbour isn't marked adding it to queue
        {
            neighbour.marked = true;
            neighbour.parent = current;
            queue.Add(neighbour);
        }
        else if (!neighbour.Equals(current.parent)) // not considering own parent
        {
            // found!
            List<MyPoint> loop = new List<MyPoint>();
            MyPoint p = current;
            do
            {
                loop.Add(p);
                p = p.parent;
            }
            while (p != null);
            p = neighbour;
            while (!p.Equals(start))
            {
                loop.Add(p);
                p = p.parent;
            }
            return loop;
        }
    }
}

return null;

而不是代码中的相应部分(我也将返回类型更改为 List<MyPoint> )。它可以正常工作并正确找到一个较小的循环，该循环由 3 个点组成:红点、正上方的点和正下方的点。