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

Question

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

Менее эффективное решение: Для выполнения BFS, начиная с одной из вершин, отслеживайте посещенные вершины до достижения конечной вершины. Это будет выполняться в O (V + E). Но это нужно сделать для каждой пары вершин. Следовательно, если есть M-число запросов для поиска пути, сложностью будет O (M * (E + V)).

Можем ли мы сделать это лучше? Можно ли использовать вывод BFS и решить остальные?

Answer 1

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

Время выполнения: O(V+E), а именно время выполнения алгоритма поиска te; дополнительные вычислительные затраты могут потребоваться для генерации самих реальных путей.