C ++ рекурсия для графа связности

Я еще ничего не реализовал, но я думал об использовании рекурсии для идентификации всех ячеек в сетке, которые «активно связаны» с данной ячейкой, то есть ячеек, которые «активны» и напрямую связаны в силу совместного использования лица. с (активной) ячейкой, о которой идет речь, или более отдаленно / опосредованно соединенной, разделяя лицо с одним из (активных) соседей. Разъединения происходят потому, что некоторые ячейки в сетке могут считаться «неактивными» (по любому определению). Моя идея / псевдокод состоит в следующем:

//Call function to traverse connections
traverse_connections(cell);

//Traverse function definition
bool traverse_connections(cell) {
//Check if cell is inactive or traversed - base case
if (current cell is inactive or traversed) {
return true;
}
//-Mark cell then move on to its neighbors
Mark cell as traversed and add it to the list of 'actively connected' cells;
bool ok = true;
for(neighbor_cell in neighbors of cell) {
ok &= traverse_connections(neighbor_cell);
}
return ok;
}

Я думаю, что это покрывает базовый случай, помечает ячейку, затем переходит к тому же, чтобы сделать то же самое для своих соседей, соседей своих соседей и так далее. Это выглядит хорошо? Есть ли какие-то очевидные пробелы, которые мне не хватает? Был бы признателен, если бы кто-то с опытом в связности графов и рекурсии мог взвесить. У меня также есть проблема при создании итеративного эквивалента. Любые идеи по этому поводу также будут высоко оценены.

Заранее спасибо!

2

Решение

Это решение не будет работать, потому что оно смешивает понятия «пройденный» и «активный / связанный». Они являются ортогональными: например, ячейка может быть неактивной и пройденной или активной и не пройденной. if заявление в верхней части вашего псевдокода возвращается true для обоих, что неверно.

Вы должны держать таблицу, помечающую пройденные ячейки, отдельно от таблицы, которая помечает активные ячейки. Прежде чем перейти к рекурсивному вызову, необходимо убедиться, что ячейка помечена как пройденная, иначе решение может быть слишком медленным или даже исчерпать стек.

Наконец, решение не должно быть рекурсивным: вы можете выполнить то, что вам нужно, простым Поиск в ширину, что можно сделать с помощью очереди вместо рекурсии.

2

Другие решения

То, как вы помечаете клетки в данный момент, скорее всего, вызовет у вас проблемы. Например, если одна из этих отмеченных вами ячеек имеет соседние ячейки, которые необходимо пройти позже, тогда они могут не пересекаться.

Если вы посмотрите в A * (A-Star) алгоритм должен дать вам хорошее представление об обходе графа. UCS (поиск с равномерной стоимостью) также является другим алгоритмом, который использует обход графа.

1

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector