Структури даних для представлення графів
Інформацію про графах або орграф можна зберігати двома способами: у вигляді матриці примикань або у вигляді списку примикань. У цій статті графі і орграфів представляються однаково, тому будемо використовувати для них загальний термін "граф". Ми побачимо також, що застосовуються методи зберігання інформації усувають відмінність в обробці графів і орграфов.
Матриця примикань забезпечує швидкий доступ до інформації про ребрах графа, проте якщо в графі мало ребер, то ця матриця буде містити набагато більше порожніх клітин, ніж заповнених. Довжина списку примикань пропорційна числу ребер в графі, однак при користуванні списком час отримання інформації про ребрі збільшується.
Жоден з цих методів не перевищує інший свідомо. В основі вибору відповідного методу повинні лежати наші попередні знання про графах, які будуть оброблятися алгоритмом. Якщо в графі багато вершин, причому кожна з них пов'язана лише з невеликою кількістю інших вершин, список примикань виявляється вигідніше, оскільки він займає менше місця, а довжина переглядаються списків ребер невелика. Якщо ж число вершин в графі мало, то краще користуватися матрицею примикань: вона буде невеликою, і навіть втрати при зберіганні в матричному вигляді розрідженого графа будуть незначні. Якщо ж в графі багато ребер і він майже повний, то матриця примикань завжди є кращим способом зберігання графа.
Використання матриці і списку примикань детально описано нижче.
матриця примикань
Матриця примикань AdjMat графа G = (V, E) з числом вершин | V | = N записується у вигляді двовимірного масиву розміром N x N. У кожній клітинці [i, j] цього масиву записано значення 0 за винятком лише тих випадків, коли з вершини vi в вершину vj веде ребро, і тоді в осередку записано значення 1. Говорячи більш строго,
На рис. 2 зображені матриці примикань для графа і орграфа, зображених на рис. 1.
Осередок матриці примикань зваженого графа або орграфа містить знак нескінченності, якщо відповідне ребро відсутня, а у всіх інших випадках її значення дорівнює вазі ребра. Діагональні елементи такої матриці дорівнюють 0, оскільки подорож з вершини в неї саму не варто нічого.
список примикань
Список примикань AdjList графа G = (V, E) з числом вершин | V | = N записується у вигляді одновимірного масиву довжини N, кожен елемент якого являє собою посилання на список. Такий список приписаний кожній вершині графа, і він містить по одному елементу на кожну вершину графа, сусідню з даної.
На рис. 3 зображені списки примикань для графа і орграфа, зображених на рис. 1.
Елементи списку примикань для зваженого графа містять додаткове поле, призначене для зберігання ваги ребра.