循环查找算法

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

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

编辑： 忘了提一下...水平连接之后必须是垂直、水平、垂直等等... 而且每行和每列中最多只能有两个点（两个或没有）在循环中。但这个条件与“循环必须是最短的”是相同的。

- Miko Kronn

---

你所谓的“loop”通常在图论中被称为“cycle”（在看了你的图片之前，我并不清楚你所说的“loop”是什么意思）。我已经适当地编辑了问题以使其可理解。但是，在二维布尔数组中存储你的点还不太清楚。 - Konrad Rudolph

编辑以澄清我如何存储点数。 - Miko Kronn

这不是关于C#的问题，而是关于算法的问题。 - Tomas Jansson

已添加我的代码示例，请查看更新后的答案。 - Vlad

Answer 1

首先，您应该将表示更改为更高效的表示方式。您应该使顶点成为一个结构/类，其中包含连接顶点的列表。

更改表示后，您可以使用广度优先搜索轻松找到最短循环。

您可以使用以下技巧加快搜索速度：按广度优先顺序遍历图形，在遍历的顶点上打标记（并在到根的路径上存储“父顶点”号码）。一旦找到已标记的顶点，搜索就结束了。您可以通过沿着存储的“父”顶点向后行走，找到从找到的顶点到根的两条路径。

---

编辑：
你确定你的代码是正确的吗？我尝试了以下内容：

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>）。这样做可以正确地找到一个由三个点组成的更小的循环，包括红色点、正上方的点和正下方的点。

- Vlad

---

我之前不知道这被认为是一种“技巧”。大多数书籍（例如CLRS）中的示例都会标记已访问的顶点。 - MAK

@MAK：关键在于当找到一个标记顶点时停止搜索，而不是（天真的方法）当搜索命中根节点时停止。顺便说一句，严格来说，BF应该应用于树，我们的图可能不是一棵树（因为它有循环）。 - Vlad

@Vlad 对的！因为当所有边权重相同时，BFS返回最短路径。我的错 :) - teto

很遗憾，这不是正确的答案（上下点）。我编辑了我的问题来解释为什么。对于我在图片上展示的情况，正确的答案就像第三张图片一样（尽管我已经知道删除点的步骤是多余的）。 - Miko Kronn

@Miko：嗯，不同的需求需要不同的解决方案 :-) 在需求更新后，我的解决方案就不再有效了。 - Vlad

Answer 2

这就是我所做的。我不知道它是否被优化了，但它确实可以正常工作。我还没有像@marcog建议的那样对点进行排序。

private static bool LoopSearch2(bool[,] mask, int supIndexStart, int recIndexStart, out List<MyPoint> path)
    {
        List<MyPoint> points = new List<MyPoint>();
        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]);
                    }
                }
            }
        }

        List<MyPoint> queue = new List<MyPoint>();
        MyPoint start = (points[0]);
        start.marked = true;
        queue.Add(points[0]);

        path = new List<MyPoint>();

        bool found = false;

        while(queue.Count>0)
        {
            MyPoint current = queue.First();
            queue.Remove(current);

            foreach (MyPoint neighbour in current.Neighbours)
            {
                if (!neighbour.marked)
                {
                    neighbour.marked = true;
                    neighbour.parent = current;
                    queue.Add(neighbour);
                }
                else
                {
                    if (neighbour.parent != null && neighbour.parent.Equals(current))
                        continue;

                    if (current.parent == null)
                        continue;

                    bool previousConnectionHorizontal = current.parent.Y == current.Y;
                    bool currentConnectionHorizontal = current.Y == neighbour.Y;

                    if (previousConnectionHorizontal != currentConnectionHorizontal)
                    {
                        MyPoint prev = current;

                        while (true)
                        {
                            path.Add(prev);
                            if (prev.Equals(start))
                                break;
                            prev = prev.parent;
                        }

                        path.Reverse();

                        prev = neighbour;

                        while (true)
                        {
                            if (prev.Equals(start))
                                break;
                            path.Add(prev);                                
                            prev = prev.parent;
                        }

                        found = true;
                        break;
                    }                      
                }
                if (found) break;
            }
            if (found) break;
        }

        if (path.Count == 0)
        {
            path = null;
            return false;
        }
        return true;   
    }   

- Ichibann

Answer 3

你的点移除步骤在实现不良的情况下最坏情况是 O(N^3)，最坏情况是每次迭代只删除一个点。而且由于它并不总是在循环检测中节省太多计算，我建议避免这样做，因为它还会给解决方案增加额外的复杂度。

从点集中创建一个邻接表开始。如果按照X和Y（分别）排序并按顺序遍历点，则可以在O（NlogN）的时间内高效地完成此操作。然后，为了找到最短的循环长度（由点数确定），从每个点开始BFS，最初将所有点放入队列中。当你遍历一条边时，将路径的源与当前点一起存储。然后，当BFS返回源时，我们就知道找到了一个循环。如果在找到循环之前队列为空，则表示不存在循环。注意不要立即返回到上一个点，否则会得到由两个点形成的无效循环。您可能还希望避免例如由点（0,0），（0,2）和（0,1）形成的循环，因为这会形成一条直线。

BFS算法的最坏情况可能是指数级的，但我相信这种情况可以被证明不存在或者极其罕见，因为图越密集，你就越快能找到一个循环；而图越稀疏，你的队列就越小。平均来说，BFS算法的运行时间更接近于邻接表构建的运行时间，或者在最坏的实际情况下为O(N^2)。

- moinudin

Answer 4

我认为我会使用一种改进的Dijkstra算法，每当它第二次到达任何节点时就停止并返回循环。如果这从未发生过，则没有循环。

这种方法应该比广度优先或深度优先搜索要高效得多，特别是如果您有许多节点。保证您只会访问每个节点一次，因此您具有线性运行时间。

- Lucero

---

为什么这样会更有效率呢？因为BF和DF搜索是线性的，时间复杂度为“节点数+边数”，而Dijkstra算法至少还有一个对数因子。 - IVlad

如果没有你的“技巧”，BF和DF将尝试每条可能的路径，其中包括如果B和C都连接到A，则包括A-B-C和A-C-B。你的“技巧”基本上是实现Dijkstra算法。如果没有发现循环，那么Dijkstra将访问每个节点一次，使其在运行时呈线性状态，不是吗？ - Lucero

@Vlad - 哎呀，抱歉，我的错。不过已经不能编辑了，对此感到抱歉！ - Lucero

显然，您使用了@Vlad的技巧，这甚至不是一个技巧，而是常识。如果所有边的权重都相等，那么Dijkstra算法不就是一种广度优先搜索吗？我认为将其视为广度优先搜索比将其视为Dijkstra算法的应用更容易理解。 - IVlad