Списки суміжності

Детальніше Список суміжності

Список суміжності це послідовність (масив, список) розміром N, кожен елемент якої є списком вершин суміжних з даною:

// список суміжності

Type TAdjacencyList = array [1..N] of record

Count: Integer; {кількість елементів у списку}

List: array[1..N] of

record {список}

Node, {номер суміжної вершини}

Weight: Integer; {вага ребра}

end;

end;

Var Graph: AdjacencyList;

Цей спосіб збереження найкраще підходить для перерахування усіх вершин суміжних з x.

Список ребер [ред.]

Детальніше Список ребер

// динамічний список ребер (із вказівниками)

// застосовують тоді, коли кількість ребер невідома наперед і їх багато

Type ListElPtr=^ListEl; {вершини графа позначені числами }

{(номерами)}

ListE l= record

Node1, Node2: integer; {список складаються із пар цілих чисел: }

{перше - звідки ребро, друге - куди}

Next:ListElPtr; {вказівник на наступне ребро графа}

end;

// список (масив) ребер

// застосовують тоді, коли кількість ребер відома наперед і невелика

Type TBranchList = array [1..M] of

record

Node1, Node2, {пари вершин, що зв'язує ребро}

Weight: Integer; {вага ребра}

end;

Var Graph: BranchList;

Як видно з цієї таблиці, цей спосіб збереження графа є особливо зручним, якщо головною операцією є перерахування ребер або пошук вершин і ребер, що знаходяться у відносинах інцидентності.