Алгоритм: используйте объединение 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, когда размер входной матрицы можно уместить в память.

Однако, что нам делать, если входная матрица действительно большая, которая не помещается в памяти?

Я мог бы разбить / разделить матрицу ввода на разные небольшие файлы и прочитать их соответственно.

Но как их объединить?

Я застрял в том, как объединить их. У меня есть идея, что при объединении их мы должны прочитать какую-то перекрывающуюся часть. Но какой конкретный способ сделать это?

Пытаясь понять решение Мэтта.

Когда я нарисовал приведенный ниже образец на доске и обработал его построчно. Объединить влево, затем объединить верх, и, кажется, не будет работать.

Из решения Мэтта.

не уверен, что такое topidx, ботидкс означает

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

Answer 1

Используя union-find, основной алгоритм (не беспокоясь о памяти):

1. Создать набор для каждого 1
2. Объединить наборы для каждой пары смежных1 s.Не имеет значения, в каком порядке вы их находите, поэтому порядок чтения, как правило, в порядке.
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");
    }

}