Способи представлення графа в пам'яті ЕОМ

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

У подальшому будемо припускати, що вершини графа мають номери від 1 до N, а ребра — від 1 до M. Кожному ребру і кожній вершині зіставлена вага — ціле позитивне число.

Матриця суміжності

Детальніше Матриця суміжності

Матриця суміжності це двовимірний масив розміром N*N:

// матриця суміжності

Type TAdjacencyMatrix = array [1..N, 1..N] of Integer;

Var Graph: TAdjacencyMatrix;

При цьому Graph[i, j] дорівнює 0, якщо вершини i та j не є суміжними, та 1 для суміжних вершин. Для зваженого графа Graph[i, j] дорівнює вазі вершини i, якщо i=j, а для суміжних вершин — вазі ребра (дуги) з вершини i у вершину j.

Просторова складність цього способу O(N2)

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

Матриця інцидентності

Детальніше Матриця інцидентності

Матриця інцидентності це двовимірний масив розміром N*M:

// матриця інцидентності

Type TIncidenceMatrix = array [1..N, 1..M] of Integer;

Var Graph: TIncidenceMatrix;

При цьому Graph[i, j] дорівнює 0, якщо вершини i та ребро j не є інцидентними, −1, якщо вершина i є кінцем орієнтованого ребра j, +1, якщо вершина i є початком орієнтованого ребра j. Інколи зручно користуватись означенням, у якому Graph[i, j] вазі ребра (дуги) j, що є інцидентним вершині i.

Матриця інцидентності найкраще підходить для операції перерахування ребер, що є інцидентними вершині x.