Структуры и алгоритмы обработки данных. Ключарев А.А - 55 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

55
type
PNode = ^TNode;
PBranch = ^TBranch;
TNode = record {вершина}
Name: string; {имя вершины}
Weight: integer; {вес вершины}
Branch: PBranch; {выходящее ребро}
Next: PNode; {следующая вершина}
end;
TBranch = record {ребро}
Node: PNode; {вершина, в которую входит}
Weight: integer; {вес ребра}
Next: PBranch; {следующее выходящее ребро}
end;
var
Graph: PBranch;
Пространственная сложность этого способа V(n, m)~O(n+m).
1.3.4. Деревья
1.3.4.1. Общие понятия
Дерево является одним из важных и интересных частных случаев
графа, поэтому оно рассматривается отдельно от графов других видов.
Деревом называется орграф, для которого:
1) существует узел, в который не входит ни одной дуги (корень);
2) в каждую вершину, кроме корня, входит одна дуга.
Вершины дерева подразделяют на следующие три группы:
– корень – вершина, в которую не входит ни одной дуги;
– узлы – вершины, в которые входит одна дуга и выходит одна или
более дуг;
– листья – вершины, в которые входит одна дуга и не выходит ни
одной дуги.
Все вершины, в которые входят дуги, исходящей из одной вершины,
называются потомками этой вершины, а сама вершина – предком. Ко-
рень не имеет предка, а листья не имеют потомков.
Выделяют уровни дерева. На первом уровне дерева может быть только
одна вершина – корень, на втором – потомки корня, на третьем – по-
томки потомков корня и т. д.
Поддеревом называется вершина со всеми ее потомками.

Страницы