算法：使用 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。

但是，如果输入矩阵很大，内存装不下怎么办？

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

但是如何合并呢？

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

试图理解 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. 将新行中的集合与上一行中的相邻集合合并。始终将链接指向下方，这样您就永远不会在新行中得到一组 linked 到旧行中的父项。
   3. 计算上一行中剩余的根集，并将该数字添加到您的岛数中。这些将永远无法与其他任何东西合并。
   4. 舍弃上一行中的所有集合——您再也不需要它们了，因为您已经数过它们，link什么也没有。

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

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

因为这实际上是我最喜欢的算法之一，这里是 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");
    }

}