算法:使用 union find 来计算岛屿的数量

Question

假设你需要计算一个矩阵上的岛数

                    {1, 1, 0, 0, 0},
                    {0, 1, 0, 0, 1},
                    {1, 0, 0, 1, 1},
                    {0, 0, 0, 0, 0},
                    {1, 0, 1, 0, 1}

当输入矩阵大小适合内存时，我们可以简单地使用 DFS 或 BFS。

但是，如果输入矩阵非常大，无法放入内存，我们该怎么办？

我可以将输入矩阵分块/拆分成不同的小文件并分别读取它们。

但是如何合并它们呢？

我卡在了如何合并它们上。我的想法是，在合并它们时我们必须阅读一些重叠的部分。但具体的做法是什么？

试图理解 Matt 的解决方案。

当我在白板上绘制下面的示例并逐行处理它时。合并左侧然后合并顶部，这似乎行不通。

来自 Matt 的解决方案。

不知道topidx, botidx是什么意思

            int topidx = col * 2;
            int botidx = topidx + 1;

Answer 1

使用union-find，基本算法(不用担心内存)是:

1. 为每 1 创建一个集合
2. 合并每对相邻 1 的集合。您找到它们的顺序并不重要，因此阅读顺序通常没问题。
3. 计算根集的数量——每个岛屿都有一个。

简单且稍加小心，您可以使用对矩阵的顺序访问和仅 2 行的内存来做到这一点:

1. 将岛屿计数初始化为0
2. 读取第一行，为每个 1 创建一个集合，并合并相邻列中的集合。

3. 每增加一行:

   1. 读取行，为每个 1 创建一个集合，并合并相邻列中的集合；
   2. 将新行中的集合与前一行中的相邻集合合并。始终将链接指向下方，这样您就永远不会在新行中的集合链接到旧行中的父项。
   3. 计算上一行中剩余的根集，并将该数字添加到您的岛数中。这些将永远无法与其他任何东西合并。
   4. 舍弃前一行中的所有集合——您再也不需要它们了，因为您已经对它们进行了计数，没有任何链接指向它们。

4. 最后，计算最后一行中的根集并将它们添加到您的岛数中。

当然，关键是当您链接不同行中的集合时，始终将链接指向下方。这不会影响算法的复杂性，如果您使用自己的联合查找，那么它很容易实现。如果您使用的是库数据结构，那么您可以只对每一行使用它，并自己跟踪不同行中根集之间的链接。

因为这实际上是我最喜欢的算法之一，这里是 Java 的实现。这不是最易读的实现，因为它涉及一些低级技巧，但它非常高效且简短——我会在性能非常重要的地方写这样的东西:

import java.util.Arrays;

public class Islands
{
    private static final String[] matrix=new String[] {
        "  #############  ###   ",
        "  #      #####   ##    ",
        "  #  ##  ##   #   #    ",
        "    ###      ##   #  # ",
        "  #   #########  ## ## ",
        "          ##       ##  ",
        "          ##########   ",
    };

    // find with path compression.
    // If sets[s] < 0 then it is a link to ~sets[s].  Otherwise it is size of set
    static int find(int[] sets, int s)
    {
        int parent = ~sets[s];
        if (parent>=0)
        {
            int root = find(sets, parent);
            if (root != parent)
            {
                sets[s] = ~root;
            }
            return root;
        }
        return s;
    }

    // union-by-size
    // If sets[s] < 0 then it is a link to ~sets[s].  Otherwise it is size of set
    static boolean union(int[] sets, int x, int y)
    {
        x = find(sets,x);
        y = find(sets,y);
        if (x!=y)
        {
            if ((sets[x] < sets[y]))
            {
                sets[y] += sets[x];
                sets[x] = ~y;
            }
            else
            {
                sets[x] += sets[y];
                sets[y] = ~x;
            }
            return true;
        }
        return false;
    }

    // Count islands in matrix

    public static void main(String[] args)
    {
        // two rows of union-find sets.
        // top row is at even indexes, bottom row is at odd indexes.  This arrangemnt is chosen just
        // to make resizing this array easier.
        // For each value x:
        // x==0 => no set. x>0 => root set of size x. x<0 => link to ~x
        int cols=4;
        int[] setrows= new int[cols*2];

        int islandCount = 0;

        for (String s : matrix)
        {
            System.out.println(s);
            //Make sure our rows are big enough
            if (s.length() > cols)
            {
                cols=s.length();
                if (setrows.length < cols*2)
                {
                    int newlen = Math.max(cols,setrows.length)*2;
                    setrows = Arrays.copyOf(setrows, newlen);
                }
            }
            //Create sets for land in bottom row, merging left
            for (int col=0; col<s.length(); ++col)
            {
                if (!Character.isWhitespace(s.charAt(col)))
                {
                    int idx = col*2+1;
                    setrows[idx]=1; //set of size 1
                    if (idx>=2 && setrows[idx-2]!=0)
                    {
                        union(setrows, idx, idx-2);
                    }
                }
            }
            //merge up
            for (int col=0; col<cols; ++col)
            {
                int topidx = col*2;
                int botidx = topidx+1;
                if (setrows[topidx]!=0 && setrows[botidx]!=0)
                {
                    int toproot=find(setrows,topidx);
                    if ((toproot&1)!=0)
                    {
                        //top set is already linked down
                        union(setrows, toproot, botidx);
                    }
                    else
                    {
                        //link top root down.  It does not matter that we aren't counting its size, since
                        //we will shortly throw it aaway
                        setrows[toproot] = ~botidx;
                    }
                }
            }
            //count root sets, discard top row, and move bottom row up while fixing links
            for (int col=0; col<cols; ++col)
            {
                int topidx = col * 2;
                int botidx = topidx + 1;
                if (setrows[topidx]>0)
                {
                    ++islandCount;
                }
                int v = setrows[botidx];
                setrows[topidx] = (v>=0 ? v : v|1); //fix up link if necessary
                setrows[botidx] = 0;
            }
        }

        //count remaining root sets in top row
        for (int col=0; col<cols; ++col)
        {
            if (setrows[col*2]>0)
            {
                ++islandCount;
            }
        }

        System.out.println("\nThere are "+islandCount+" islands there");
    }

}