|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 02 Jun 2002 22:33:55
To : Andrei Bejenari
Subject : Re: Представление мультиграфов
--------------------------------------------------------------------------------
Sun Jun 02 2002 15:33, Andrei Bejenari wrote to Alexander Kazak:
>> Подскажите мне, пожалуйста (или скажите где прочитать), каким образом
>> рационально представить мультиграф в памяти ЭВМ.
>> (Мультиграф - это такой, у которого любые две вершины могут быть
>> соединены более чем одной дугой)
>> Матрица смежности, понятно, не подходит.
AB> k матриц смежности зато подходят :) делаешь трехмерную
AB> матрицу смежности NxNxK, где N - понятно, кол-во вершин,
AB> а К - максимальное число ребер которые могут соединять любые
AB> две вершини. если нет, можешь использовать списки, тут вообще
AB> никаких отличий от обычного графа не будет.
AB> а что рациональней, так это от конкретных условий задачи зависит.
AB> первое будет экономить время, второе, при разряженных графах, память.
Я бы обошелся одной:)
Разумеется, если все дуги идентичны. Просто вместо (0;1) указывается число
дуг.
А вот если различны - указатель на список дуг с их характеристиками...
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
