Граф (абстрактний тип даних)

В інформатиці граф — це абстрактний тип даних, який призначений для реалізації концепцій неорієнтованого і орієнтованого графів, які походять з математики, а саме, з теорії графів.

Орієнтований граф з трьома вершинами (сині кола) та трьома ребрами (чорні стрілки).

Структура даних графів складається зі скінченної (можливо, змінної) множини вершин (також, вони можуть називатися вузлами або точками) разом із множиною невпорядкованих пар цих вершин для неорієнтованого графу або множини впорядкованих пар для орієнтованого графу. Ці пари відомі як ребра (їх також називають зв'язками або відрізками), а для орієнтованого графу також відомі як стрілки. Вершини можуть бути частиною структури графу, або можуть бути зовнішніми об'єктами, представленими цілими індексами або посиланнями.

Структура даних у графах також може пов'язувати з кожним ребром якесь значення ребра, таке як символьний або числовий атрибут (вартість, місткість, довжина, тощо).

Операції

Основні операції, передбачені структурою даних графів G:

• суміжність(G, x, y): перевіряє наявність ребра між вершиною x та вершиною y;
• сусідство(G, x): перераховує всі вершини y такі, які мають ребро з вершиною x;
• додати_вершину(G, x): додає вершину x, якщо її немає;
• видалити_вершину(G, x): видаляє вершину x, якщо вона є;
• додати_ребро(G, x, y): додає ребро від вершини x до вершини y, якщо його немає;
• видалити_ребро(G, x, y): видаляє ребро від вершини x до вершини y, якщо воно є;
• отримати_значення_вершини(G, x): повертає значення, пов'язане з вершиною x ;
• задати_значення_вершини(G, x, v): встановлює значення, пов'язане з вершиною x на v .

Структури, які приписують значення ребрам:

• отримати_значення_ребра(G, x, y): повертає значення, пов'язане з ребром (x, y);
• задати_значення_ребра(G, x, y, v): встановлює значення, пов'язане з ребром (x, y), на v.

Структури даних для представлення

На практиці використовуються різні структури даних для представлення графів:

^[en]

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

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

Двовимірна матриця, в якій рядки представляють початкові вершини, а стовпці — кінцеві вершини. Дані про ребра та вершини повинні зберігатися окремо. Між кожною парою вершин може зберігатися лише одне ребро.

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

Двовимірна булева матриця, в якій рядки представляють вершини, а стовпці — ребра. Записи вказують, чи буде вершина в рядку інцидентною ребру у стовпчику.

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

	Список суміжності	Матриця суміжності	Матриця інцидентності
Зберігати граф	${\displaystyle O(|V|+|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
Додати вершину	${\displaystyle O(1)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
Додати ребро	${\displaystyle O(1)}$	${\displaystyle O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
Видалити вершину	${\displaystyle O(|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
Видалити ребро	${\displaystyle O(|V|)}$	${\displaystyle O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
Чи суміжні вершини x і y (якщо вважати, що місця їх зберігання відомі)?	${\displaystyle O(|V|)}$	${\displaystyle O(1)}$	${\displaystyle O(|E|)}$
Зауваження	Повільно видаляє вершини та ребра, тому що потрібно знаходити всі вершини чи ребра	Повільно додає або видаляє вершини, тому що матрицю потрібно змінювати розмір/копіювати	Повільно додає або видаляє вершини та ребра, тому що матрицю потрібно змінювати розмір/копіювати

Списки суміжності зазвичай є ефективнішими, оскільки вони краще представляють розріджені графи. Матриця суміжності є ефективнішою, якщо граф є щільним, тобто кількість ребер |Е| близька до квадрату кількості вершин — |V|², або якщо потрібно швидко знайти ребро, яке з'єднує дві вершини.

Див. також

• Пошук по графу для обходу графів
• Графова база даних для збереження графів (структур даних)
• ^[en] для перетворень графів заснованих на правилах
• (Програмне забезпечення для зображення графів)

Примітки

1. Див., наприклад Goodrich та Tamassia, (2015), Section 13.1.2: Operations on graphs, p. 360. Для більш детального набору операцій, див. Mehlhorn, K.; Näher, S. (1999), Chapter 6: Graphs and their data structures, LEDA: A platform for combinatorial and geometric computing, Cambridge University Press, с. 240—282
2. Cormen та ін., (2001), pp. 528—529; Goodrich та Tamassia, (2015), pp. 361—362.
3. Cormen та ін., (2001), pp. 529—530; Goodrich та Tamassia, (2015), p. 363.
4. Cormen та ін., (2001), Exercise 22.1-7, p. 531.
5. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2001) [1990]. Section 22.1: Representations of graphs. Вступ до алгоритмів (вид. 2nd). MIT Press і McGraw-Hill. с. 527—531. ISBN ..
6. ; (2015), Section 13.1: Graph terminology and representations, Algorithm Design and Applications, Wiley, с. 355—364.

Посилання

• Boost Graph Library — потужна бібліотека на C++ для роботи з графами [ 17 травня 2008 у Wayback Machine.], див. Boost
• Пакет Networkx для побудови графів на Python [ 10 березня 2013 у Wayback Machine.], див. NetworkX
• GraphMatcher [ 5 лютого 2020 у Wayback Machine.] — програма на Java для вирівнювання (не)орієнтованих графів
• GraphBLAS [ 21 вересня 2016 у Wayback Machine.] — специфікація інтерфейсу бібліотеки для операцій над графами, з акцентом на розріджені графи.