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

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

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

Основні операції, передбачені структурою даних графів 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.

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

Список суміжності^[en][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]

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

Вікісховище має мультимедійні дані за темою: Граф (абстрактний тип даних)

• 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.] — специфікація інтерфейсу бібліотеки для операцій над графами, з акцентом на розріджені графи.