Машинне представлення орграфів

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

МАТРИЧНЕ ПРЕДСТАВЛЕННЯ ОРГРАФІВ. При використанні матриць суміжності їхні елементи представляються в пам'яті ЕОМ елементами масиву. При цьому, для простого графа матриця складається з нулів і одиниць, для мультиграфа - з нулів і цілих чисел, що вказують кратність відповідних ребер, для зваженого графа - з нулів і речовинних чисел, що задають вагу кожного ребра.

Наприклад, для простого орієнтованого графа, зображеного на рис. 7.5 масив визначається як:

mas:array[1..4,1..4]=((0,1,0,0),(0,0,1,1),(0,0,0,1),(1,0,1,0))

Матриці суміжності застосовуються, коли в графі багато зв'язків і матриця добре заповнена.

ЗВ'ЯЗНЕ ПРЕДСТАВЛЕННЯ ОРГРАФІВ. Орграф представляється зв'язним нелінійним списком, якщо він часто змінюється або якщо напівступені заходу і виходу його вузлів великі. Розглянемо два варіанти представлення орграфів зв'язаними нелінійними списками. У першому варіанті два типи елементів - атомарний і вузол зв'язку.

На рис. 7.9 показана схема такого представлення для графа рис. 7.5. Скобковий запис зв'язків цього графа: ( <A,B>, <B,C>, <C,D>, <B,D>, <D,C> )

 

Рис.7.9. Машинне

представлення графа

елементами двох типів

 

Більш раціонально представляти граф елементами одного формату, подвійними: атом-покажчик і покажчик-покажчик або потрійними:

покажчик-data/down-покажчик. На рис.7.10 той же граф представлений елементами одного формату.

Рис.7.10. Машинне представлення графа однотипними елементами

 

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