|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitry Volkov 2:5015/185.5 03 Jun 2002 10:34:36
To : "Andrei Bejenari"
Subject : Re^2: Представление мультиграфов
--------------------------------------------------------------------------------
Правильно ли помню я, что 02.06.02 14:33:15
разговаривал ты с Alexander Kazak про "Re: Представление мультиграфов"?
>> Подскажите мне, пожалуйста (или скажите где прочитать), каким образом
>> рационально представить мультиграф в памяти ЭВМ. (Мультиграф - это такой,
>> у которого любые две вершины могут быть соединены более чем одной дугой)
>> Матрица смежности, понятно, не подходит.
U> k матриц смежности зато подходят :) делаешь трехмерную матрицу смежности
U> NxNxK, где N - понятно, кол-во вершин, а К - максимальное число ребер
U> которые могут соединять любые две вершини. если нет, можешь использовать
U> списки, тут вообще никаких отличий от обычного графа не будет. а что
U> рациональней, так это от конкретных условий задачи зависит. первое будет
U> экономить время, второе, при разряженных графах, память.
Списки ребер - логично, подходят для всех графов.
Hо *K* матриц смежности... Это круто :) А если от одной вершины много, очень
много:) дуг отходит, а от другой-нет??
Лучше "скрестить":) матрицу смежностей и список ребер:
элемент a[i, j] содержит указатель на начало списка дуг из i в j - это если для
дуг нужны какие-то еще параметры (вес и т.п.). Если нет, еще лучше: a[i, j] -
просто кол-во дуг из i в j.
Ветра в спину, Andrei,
Hе забывай о
2mi3 (DiMiTry Volkov)
--- WP/95 Rel 1.78E (215.0) Reg.
* Origin: Сколько на Свете живу, а такого не видел... (2:5015/185.5)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
