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

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

• суміжність(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 .

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

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

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

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

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

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

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

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

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

У наступній таблиці наведена часову складність для виконання різних операцій над графами з |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|², або якщо потрібно швидко знайти ребро, яке з'єднує дві вершини.[5][6]

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

• Boost Graph Library — потужна бібліотека на C++ для роботи з графами, див. Boost
• Пакет Networkx для побудови графів на Python, див. NetworkX
• GraphMatcher — програма на Java для вирівнювання (не)орієнтованих графів
• GraphBLAS — специфікація інтерфейсу бібліотеки для операцій над графами, з акцентом на розріджені графи.