Как наиболее эффективно определить, существует ли путь между двумя узлами?

Question

Мне дан массив целых чисел в C (предназначенный для представления двумерной матрицы узлов), который может содержать 0 или 1. Учитывая координаты 2 '0' узлов, я должен просто выяснить, существует ли путь 0 между ними (где узлы соединяются смежно - вверх, вниз, влево, вправо).

IsЕсть ли более простая альтернатива BFS / DFS, которую я могу использовать, чтобы решить мою проблему? Я знаю, что с BFS / DFS я могу не только определить наличие пути, но также найти и вернуть рабочий путь? Просто интересно, если это излишне для этой проблемы.

Answer 1

Я полагаю, что в общем случае поиск по глубине в первом случае (с кешем, позволяющим убедиться, что вы посещаете данный узел только один раз), обычно является самым быстрым способом проверить, существует ли путь.

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

Возможно, вы сможете выполнить оптимизацию, если знаете больше информации о своем графике. Например, если вы знаете, что любые подключенные узлы также должны быть соседями, вы должны использовать BFS вместо DFS. Если ваш график имеет какое-то пространственное (или подобное) отношение, то A *, вероятно, быстрее, чем DFS.

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

РЕДАКТИРОВАТЬ: перечитывая ваш вопрос, звучит так, как будто вы находите путь на карте. Я предлагаю рассмотреть A *, это может быть быстрее, если есть много путей одинаковой длины. Если правильный путь намного длиннее тупиков, то DFS, вероятно, все еще быстрее.

РЕДАКТИРОВАТЬ 2, электрический бугалу: если вы делаете эту проверку много раз на одной карте, и вам нужно только знать, есть липуть вообще существует, тогда, возможно, самое быстрое решение - заполнить заливку на карте и обозначить регионы. Тогда все, что вам нужно сделать, это проверить, находятся ли обе ваши точки в одном регионе.