Как найти количество связных компонентов в неявном графе?

У меня есть проблема CS, которая сформулирована так:

У меня есть лист бумаги с вырезанными ячейками, представленными символами (либо "." (вырезано), либо "#" (не вырезано)), мне нужно найти, сколько частей получится.

Пример:

##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####

Ответ для примера выше: 5.

Из одного куска получится:

....
.##.
....

Образуются две части:

....
.#..
..#.

Здравый смысл подсказывает мне найти способ представить лист графом (каждый знак числа является вершиной, и две вершины связаны, если они имеют общую сторону). Однако мне непонятно, как это сделать. Я обнаружил, что существуют неявные графы (графы, определяемые функцией, которая возвращает всех соседей данной вершины). Такая функция тривиальна для реализации в случае.

Возникает вопрос: Как мне изменить алгоритм DFS, чтобы найти компоненты в графе такого типа?


graph algorithm implicit connected-components depth-first-search
person Alex Danilov    schedule 27.09.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

  1. Когда мы перебираем ребра из вершины, мы используем неявные ребра вместо сохраненных ребер.

  2. Удобно представлять вершины в виде их двумерных координат (row, col).

Псевдокод может быть следующим:

dRow = [-1,  0, +1,  0]
dCol = [ 0, -1,  0, +1]
...later, when we want to move from vertex (row, col)...
for dir in [0..4):
    nRow = row + dRow[dir]
    nCol = col + dCol[dir]
    if vertex (nRow, nCol) is in rectangle bounds:
        try to move from vertex (row, col) to vertex (nRow, nCol)

Это то место, где классическая реализация DFS имела бы такой цикл:

for each vertex u in {neighbors of vertex v}:
    try to move from vertex v to vertex u
person Gassa    schedule 27.09.2017