Как я могу найти график для пути?

Question

Скажем, у меня есть список ребер, каждый из которых содержит два узла (туда и обратно). Каков наилучший способ найти ребро двух заданных узлов? Обратите внимание, что узлы на ребре могут повторяться.

Скажите, что у меня есть преимущество в этом формате:

1 <-> 5

3 <-> 7

5 <-> 6

2 <-> 6

Тогда запрос, такой как 1 5, вернет true .

Тогда запрос типа 5 2 вернет true , потому что 5 соединяет 6, а 6 соединяется с 2.

Тогда запрос типа 1 7 вернет false .

Тогда запрос типа 7 4 вернет false , так как 4 не существует, это означает, что это узел без края.

Answer 1

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

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

initialize the disjoint set structure (DSS)
for each edge:
  for each vertex in edge:
    if the vertex does not exist in the DSS:
      create a new subset in the DSS containing only the vertex
  merge the subsets of the two vertices

Чтобы определить, существует ли путь между двумя вершинами после обработки всех ребер, просто проверьте, находятся ли две вершины в одном и том же подмножестве. Если они есть, то между ними существует какой-то путь.

При эффективной реализации DSS этот алгоритм достигает чуть хуже линейного времени, и даже при простой реализации DSS со связанным списком это O (n * log (n)). Как упоминает хакер j _ random _, Флойд-Варшалл - это O (n ^ 3) времени и O (n ^ 2) памяти независимо от того, рассчитываете ли вы только транзитивное замыкание или нет, а использование алгоритма Дейкстры требует O (n * log (n)) вычисление для каждого запроса.

Answer 2

В основном вы ждете, чтобы проверить, есть ли заданная пара узлов между ними или нет. Это общий случай проблемы кратчайшего пути. Однако обратите внимание, что этого достаточно, если мы сможем найти кратчайший путь между парой рассматриваемых узлов. Используйте любое подходящее представление (матрица смежности, список смежности, наборы ребер, union-find ...) и продолжайте реализацию BFS / Djikstra для всех пар узлов. Тогда это только вопрос обслуживания запросов. Или вы можете запускать Djikstra / BFS на ленивой основе (и постепенно кэшировать прошлые вычисления).

Answer 3

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

for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      W[i][j] = W[i][j] or (W[i][k] and W[k][j])

W перед запуском этого кода должна быть двоичная матрица смежности для графа (W[i][j] == 1 <-> есть грань от i до j). После этого будет транзитивное закрытие. То есть W[i][j] будет равно 1 тогда и только тогда, когда j достижимо с i.

Answer 4

Проверьте JGraphT библиотека, она специализируется на алгоритмах графа и делает то, что вам нужно.