Автор: Altair 30.05.2005 0:09
Кто знает какие-нибудь методы заданя графа, не описанные выше, пишите сюда.
Итак,
1. Матрица смежности.
M[1..N,1..N], где N-число вершин.
Строки и столбцы-номера вершин,на пересечении вес ребра соединяющегоэти вершины или бесконечность (машинная) если ребра нет. (нули по диагонали).
2. Список ребер.
M[1..R,1..2], где R -число ребер.
Список ребер (строки матрицы), 1 и 2 столбец это соответсвенно соединяемые ребром вершины.
3. Матрица инцедентности.
M[1..N, 1..R], где N- кол-во вершин, R-кол-во ребер.
(номера строк матрицы - номера ребер, номера столбцов-номера вершин.)
На пересечении 1 или 0 взависимости принадлежит ли вершина ребру или нет.
Автор: Altair 30.05.2005 0:21
volvo указал материал:
http://ric.uni-altai.ru/Fundamental/pascal3/lab1/teor1-3.htm
http://ric.uni-altai.ru/Fundamental/pascal3/lab1/teor1-4.htm
Автор: Atos 30.05.2005 15:56
6. Список смежности
Каждой вершине ставится в соответствие список указателей на смежные ей вершины.
Автор: zeus 4.09.2007 21:38
Цитата(Atos @ 30.05.2005 11:56)
6. Список смежности
Каждой вершине ставится в соответствие список указателей на смежные ей вершины.
а кто нибудь знает о FO и MFO-представлении графа?
Автор: Fanat 18.09.2007 1:40
Цитата(zeus @ 4.09.2007 18:38)
а кто нибудь знает о FO и MFO-представлении графа?
FO-Есть массив А, такой что, первая цифра это количество вершин,за ней до 0 вершины сменжные с первой, после 0 смежные со второй,
и так далее, в конце ставиться 0. Требует 2*число рёбер+число вершин ячеек помяти.
MFO-нечто похожее,вместо разделитилей-0ей,есть второй массив, который на i-ом месте содержит номер элемента в массиве A на котором заканчиваються вершины смежные с i-ой вершиной.
Автор: 2ral 21.12.2007 15:13
Есть еще цепная запись. вершина показывает на те с которыми она соеденина, каждая из следующих показывает на "свои вершины" и т.д. один из самых эффективных но сложный вариантов.
Автор: Atos 21.12.2007 15:16
Цитата(2ral @ 21.12.2007 8:13)
Есть еще цепная запись. вершина показывает на те с которыми она соеденина, каждая из следующих показывает на "свои вершины" и т.д. один из самых эффективных но сложный вариантов.
А чем это отличается от списка смежности?
Автор: Michael_Rybak 21.12.2007 17:08
Цитата(Atos @ 21.12.2007 10:16)
А чем это отличается от списка смежности?
Очень похоже на обычное дерево:)