Лучший и самый простой алгоритм поиска вершины на графе?

Question

После реализации большинства общих и необходимых функций для моей реализации Graph я понял, что пара функций (удаление вершины, поиск вершины и получение вершины) не имеют «лучшей» реализации.

Я использую списки смежности со связанными списками для своей реализации Graph, и я искал одну вершину за другой, пока она не нашла ту, которую я хочу. Как я уже сказал, я понял, что не использую «лучшую» реализацию. У меня может быть 10000 вершин, и мне нужно искать последнюю, но эта вершина может иметь ссылку на первую, что значительно ускорит процесс. Но это только гипотетический случай, это может случиться или не происходить.

Итак, какой алгоритм вы рекомендуете для поиска? Наши учителя говорили в основном о широте и глубине (и алгоритме Дикжстры, но это совершенно другой предмет). Между этими двумя, какой из них вы рекомендуете?

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

Полагаю, лучше использовать Depth-first, проще в реализации и, глядя на то, как они работают, кажется лучшим выбором. Но это действительно зависит от ввода.

Но что вы, ребята, предлагаете?

Answer 1

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

Обход графика (например, DFS или BFS) не улучшит это с точки зрения производительности.

Answer 2

Поиск и удаление узлов в графе - это проблема «поиска», а не проблемы графа, поэтому, чтобы сделать это лучше, чем O (n) = линейный поиск, BFS, DFS, вам нужно хранить ваши узлы в другой структуре данных оптимизирован для поиска или сортировки их. Это дает вам O (log n) для операций поиска и удаления. Кандидаты - это древовидные структуры, такие как b-деревья или хеш-таблицы. Если вы хотите написать код самостоятельно, я бы выбрал хеш-таблицу, которая обычно дает очень хорошую производительность и достаточно проста в реализации.

Answer 3

Я думаю, что BFS обычно быстрее среднего. Прочитайте вики-страницы для DFS и BFS .

Причина, по которой я говорю, что BFS быстрее, заключается в том, что он обладает свойством достижения узлов в порядке их расстояния от вашего начального узла. Таким образом, если ваш график содержит N узлов и вы хотите найти узел N, а узел 1, который является узлом, с которого вы запускаете форму поиска, связан с N, то вы найдете его немедленно. Однако DFS может расширить весь граф до того, как это произойдет. DFS будет быстрее, если вам повезет, в то время как BFS будет быстрее, если узлы, которые вы ищете, находятся рядом с вашим начальным узлом. Короче говоря, они оба зависят от ввода, но я бы выбрал BFS.

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

Если вы можете нормализовать свои узлы (пронумеровать их от 1 до 10 000 и получить к ним доступ по номеру), то вы можете легко сохранить Exists[i] = true if node i is in the graph and false otherwise, что даст вам O (1) время поиска. В противном случае рассмотрите возможность использования хеш-таблицы , если нормализация невозможна или вы не хотите этого делать.

Answer 4

Линейный поиск быстрее, чем BFS и DFS.Но быстрее, чем линейный поиск, будет A * с нулевой стоимостью шага.Когда стоимость шага равна нулю, A * будет расширять только те узлы, которые находятся ближе всего к целевому узлу.Если стоимость шага равна нулю, тогда стоимость пути каждого узла равна нулю, и A * не будет расставлять приоритеты для узлов с более коротким путем.Это то, что вам нужно, поскольку вам не нужен кратчайший путь.

A * быстрее линейного поиска, потому что линейный поиск, скорее всего, завершится после O (n / 2) итераций (каждый узел имеет равные шансы наявляясь целевым узлом), но A * отдает приоритет узлам, которые имеют более высокий шанс стать целевым узлом.

Answer 5

Если вы ищете конкретную вершину и завершаете ее, когда я ее нахожу, я бы порекомендовал использовать A *, что является лучшим поиском в начале.

Идея состоит в том, что вы вычисляете расстояние от исходной вершины до текущей обрабатываемой вершины, а затем «угадываете» расстояние от текущей вершины до цели.

Вы начинаете с источника, вычисляете расстояние (0) плюс предположение (что бы это ни было) и добавляете его в очередь с приоритетами, где приоритет - расстояние + угадывание. На каждом шаге вы удаляете элемент с наименьшим расстоянием + угадывание, выполняете вычисления для каждой вершины в списке смежности и помещаете их в очередь с приоритетами. Остановитесь, когда найдете целевую вершину.

Если ваша эвристика (ваше «предположение») допустима, то есть, если она всегда занижена, то вы гарантированно найдете кратчайший путь к вашей целевой вершине при первом посещении Это. Если ваша эвристика недопустима, вам придется запустить алгоритм до завершения, чтобы найти кратчайший путь (хотя, похоже, вам не важен кратчайший путь, просто любой путь).

На самом деле это не так сложно реализовать, как поиск в ширину (на самом деле, нужно просто добавить эвристику), но он, вероятно, даст более быстрые результаты. Единственная сложная часть - выяснить вашу эвристику. Для вершин, представляющих географические местоположения, обычной эвристикой является использование эвристики "как мухи" (прямое расстояние).

Answer 6

Я бы прокомментировал сообщение Конрада, но пока не могу комментировать, так что ... Я хотел бы во-вторых, что это не влияет на производительность, если вы реализуете DFS или BFS через простой линейный поиск через список. Ваш поиск определенного узла в графе не зависит от структуры графа, поэтому нет необходимости ограничиваться алгоритмами графа. С точки зрения времени кодирования, линейный поиск - лучший выбор; если вы хотите освежить свои навыки в графовых алгоритмах, используйте DFS или BFS, в зависимости от того, что вам нравится.

Answer 7

алгоритмы глубины первый и ширина-первый почти идентичны, за исключением использования стека в одном (DFS), очереди в другом (BFS) и нескольких обязательных переменных-членов. Реализация их обоих не должна занимать у вас много дополнительного времени.

Кроме того, если у вас есть список смежных вершин, то ваш поиск в любом случае будет O (V). С помощью одного из двух других поисков будет получено практически ничего.

Answer 8

Поиск в глубину лучше, потому что

1. Он использует гораздо меньше памяти
2. Проще реализовать