Матричные операции для перечисления всех путей через n-раздельный граф

Question

У меня есть n-раздельный (ненаправленный) граф, заданный в виде матрицы смежности, например, вот этот:

  a b c d
a 0 1 1 0
b 0 0 0 1
c 0 0 0 1
d 0 0 0 0

Я хотел бы знать, существует ли набор матричных операций, которые я могу применить к этой матрице, что приведет к матрице, которая "перечисляет" все пути (длиной n, т.е. через все разбиения) в этом графе , Для приведенного выше примера существуют пути a-> b-> d и a-> c-> d. Следовательно, я хотел бы получить следующую матрицу в результате:

a b c d
1 1 0 1
1 0 1 1

Первый путь содержит узлы a, b, d, а второй - узлы a, c, d. При необходимости матрица результатов может иметь несколько строк со значением 0, как здесь:

a b c d
1 1 0 1
0 0 0 0
1 0 1 1
0 0 0 0

Спасибо!

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

Answer 1

Одна вещь, которую вы можете сделать, - это вычислить n-ю степень вашей матрицы A. Результат скажет вам, сколько там путей длины n от одной вершины до любой другой.

Теперь, если вам интересно знать все вершины вдоль пути, я не думаю, что использование чисто матричных операций - это путь. Принимая во внимание, что у вас есть n-раздельный граф, я бы настроил структуру данных следующим образом: (Имейте в виду, что стоимость пространства будет дорогой для всех, кроме небольших значений.)

Каждый столбец будет иметь одну запись каждого из узлов в нашем графике. N-й столбец будет содержать 1, если этот узел доступен на n-й итерации из нашей назначенной начальной вершины или начального набора, и ноль в противном случае. Каждая запись в столбце также будет содержать список обратных указателей на вершины в столбце n-1, которые привели к этой вершине в n-м столбце. (Это похоже на алгоритм Витерби, за исключением того, что мы должны поддерживать список обратных указателей для каждой записи, а не только для одной.) Сложность выполнения этого составляет (m ^ 2) * n, где m - количество вершин в график, а п длина желаемого пути.

Меня немного смущает ваша верхняя матрица: с недискаженным графом я бы ожидал, что матрица смежности будет симметричной.

Answer 2

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

'Одна вещь, которую вы можете сделать, - это вычислить n-ю степень вашей матрицы A. Результат скажет вам, сколько там путей длины n от одной вершины до любой другой.'

Сила matriax порождает прогулки, а не пути.