 Методы задания графов. |
Правила раздела!
1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!
  |
| Altair |
  29.05.2005 20:09
Сообщение
#1
|
 Ищущий истину  Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация:  45   |
Кто знает какие-нибудь методы заданя графа, не описанные выше, пишите сюда.
Итак, 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 |
29.05.2005 20:21
Сообщение
#2
|
|
Ищущий истину Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: 45 |
-------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
|
|
|
| Atos |
30.05.2005 11:56
Сообщение
#3
|
 Прогрессор Группа: Модераторы Сообщений: 602 Пол: Мужской Реальное имя: Михаил Репутация: 9 |
6. Список смежности
Каждой вершине ставится в соответствие список указателей на смежные ей вершины. |
|
|
|
| zeus |
4.09.2007 17:38
Сообщение
#4
|
|
Новичок Группа: Пользователи Сообщений: 10 Пол: Мужской Репутация: 0 |
Цитата(Atos @ 30.05.2005 11:56)  6. Список смежности Каждой вершине ставится в соответствие список указателей на смежные ей вершины. а кто нибудь знает о FO и MFO-представлении графа? |
|
|
|
| Fanat |
17.09.2007 21:40
Сообщение
#5
|
 Fanat Группа: Пользователи Сообщений: 261 Пол: Мужской Реальное имя: Сергей Репутация: 5 |
Цитата(zeus @ 4.09.2007 18:38) а кто нибудь знает о FO и MFO-представлении графа? FO-Есть массив А, такой что, первая цифра это количество вершин,за ней до 0 вершины сменжные с первой, после 0 смежные со второй, и так далее, в конце ставиться 0. Требует 2*число рёбер+число вершин ячеек помяти. MFO-нечто похожее,вместо разделитилей-0ей,есть второй массив, который на i-ом месте содержит номер элемента в массиве A на котором заканчиваються вершины смежные с i-ой вершиной. |
|
|
|
| 2ral |
21.12.2007 11:13
Сообщение
#6
|
 Новичок Группа: Пользователи Сообщений: 22 Пол: Мужской Реальное имя: Neymanov Tural Репутация: 0 |
Есть еще цепная запись. вершина показывает на те с которыми она соеденина, каждая из следующих показывает на "свои вершины" и т.д. один из самых эффективных но сложный вариантов.
-------------------- Смейся и весь мир будет смеяться вместе с тобой, плачь и ты будешь плакать в одиночестве (Old Boy)
|
|
|
|
| Atos |
21.12.2007 11:16
Сообщение
#7
|
|
Прогрессор Группа: Модераторы Сообщений: 602 Пол: Мужской Реальное имя: Михаил Репутация: 9 |
Цитата(2ral @ 21.12.2007 8:13) Есть еще цепная запись. вершина показывает на те с которыми она соеденина, каждая из следующих показывает на "свои вершины" и т.д. один из самых эффективных но сложный вариантов. А чем это отличается от списка смежности? |
|
|
|
| Michael_Rybak |
21.12.2007 13:08
Сообщение
#8
|
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата(Atos @ 21.12.2007 10:16) А чем это отличается от списка смежности? Очень похоже на обычное дерево:) |
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 6.11.2024 5:03 |