Как называется этот тип матрицы представления графа?

В курсе алгоритмов несколько лет назад я наткнулся на интересное графовое представление. По сути, это матрица пути, но с дополнительной информацией. Каждая ячейка Aij содержит (возможно, пустой) список вершин, смежных с i, через которые можно пройти, чтобы достичь j.

Например, ориентированный граф, неформально представленный как:

(Z X) (Z Y) (X W) (Y W)

получает следующую матрицу:
введите здесь описание изображения
При сохранении такой матрицы у вас есть Преимущество знания не только того, есть ли путь от i к j, но и каковы все возможные пути.

Но я не могу найти ссылку на это представление в Интернете. Как это называется?


graph data-structures adjacency-matrix
person mhelvens    schedule 07.11.2012    source источник
comment
Похоже на вариант матрицы смежности   -  person SomeWittyUsername    schedule 08.11.2012
comment
Я бы сказал, что это больше похоже на матрицу пути, поскольку вы можете определить доступность с помощью одного поиска. Он также имеет характеристики списка смежности. Вы можете получить все вершины, смежные с i, если возьмете объединение ячеек в строке i.   -  person mhelvens    schedule 08.11.2012

Ответы (2)


arrow_upward
0
arrow_downward

Кажется, это называется матрица списка смежности. См. http://www.dmi.usherb.ca/~hlaoui/th.pdf или выполните поиск в Академии Google

person Xiao Jia    schedule 21.11.2012
comment
Нет, я так не думаю. Из того, что я понимаю из этой статьи (которая не особенно хорошо представлена), они просто берут матрицу путей и как бы «добавляют» информацию о списке смежности в каждую ячейку. Это кажется немного неэлегантным, и я не вижу преимуществ по сравнению с поддержкой обеих структур по отдельности. --- Матрица, о которой я говорю, говорит вам, как добраться из точки А в точку Б. Эта информация отсутствует в матрице списка смежности. - person mhelvens; 21.11.2012

arrow_upward
0
arrow_downward

После долгих поисков и подсказки старого учителя я наткнулся на реконструкцию пути. раздел статьи Википедии об алгоритме Флойда-Уоршалла. Они сохраняют «следующий узел» на кратчайшем пути между i и j в ячейке Aij того, что они называют:

следующая матрица

В наборе слайдов кто-то, похоже, коллега по моему это называется:

расстояние-следующая таблица

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

матрица следующего пути

Если кто-нибудь может процитировать научную публикацию, в которой говорится об обратном, я все равно буду рад принять их ответ вместо своего собственного.

person mhelvens    schedule 21.11.2012