Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Это у тебя связный орграф 16.10.06 16:55 Число просмотров: 3761
Автор: whiletrue <Роман> Статус: Elderman
|
Способов хранения графа фактически два
Способ первый: массив ребер.
Пусть в графе M ребер. Заведем массив размером Mx2, в котором будем хранить ребра парами вершин, которые они соединяют. Это наиболее понятный, но достаточно неудобный способ хранения графа. Однако у него есть один большой плюс - при таком способе представления легко вводить дополнительные характеристики ребер. Например, чтобы сохранить веса ребер, достаточно сделать массив размером Mx3 и в дополнительную ячейку для каждого ребра записать его вес.
Способ второй: матрица смежности.
Пусть в графе N вершин. Заведем матрицу размером NxN, где в элемент ai,j запишем количество ребер из вершины i в вершину j. Если граф взвешенный, то вместо количества запишем вес соответствующего ребра. В случае отсутствия ребра запишем бесконечность. Таким образом, проявился один из недостатков такого представления: в матрице смежности невозможно хранить взвешенный граф с кратными ребрами. Однако, в некоторых случаях, это можно обойти. Очень часто из всего множества ребер между данной парой вершин нам достаточно хранить только одно - самое легкое.
В твоем случае - второй способ не очень удобен, т.к. у тебя БД
Насчет конкретно твоего алгоритма поиска еще подумаю.. позже напишу
http://www.intuit.ru/department/algorithms/gaa/
|
|
|
подробно о проекте
Анализ криптографических сетевых...
