Перегляд вихідного коду сторінки Граф (абстрактний тип даних)

[[Файл:Directed.svg|міні|160x160пкс| [[Орієнтований граф]] з трьома [[Вершина (теорія графів)|вершинами]] (сині кола) та трьома [[Словник термінів теорії графів|ребрами]] (чорні стрілки).]]
В [[Інформатика|інформатиці]] '''граф'''&nbsp;— це [[абстрактний тип даних]], який призначений для реалізації концепцій [[Граф (математика)|неорієнтованого]] і [[Орієнтований граф|орієнтованого графів]], які походять з [[Математика|математики]], а саме, з [[Теорія графів|теорії графів]].

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

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

== Операції ==
Основні операції, передбачені структурою даних графів ''G'':<ref name="gt-ops">Див., наприклад {{Harvtxt|Goodrich|Tamassia|2015}}, Section 13.1.2: Operations on graphs, p. 360. Для більш детального набору операцій, див. {{Citation|contribution=Chapter 6: Graphs and their data structures|pages=240–282|title=LEDA: A platform for combinatorial and geometric computing|first=K.|last=Mehlhorn|author-link=Курт Мельгорн|first2=S.|last2=Näher|publisher=Cambridge University Press|year=1999}}</ref>

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

Структури, які приписують значення ребрам:<ref name="gt-ops"/>

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

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

; {{Нп|Список суміжності|||Adjacency list}}<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 528—529; {{Harvtxt|Goodrich|Tamassia|2015}}, pp. 361—362.</ref>
: Вершини зберігаються у вигляді записів або об'єктів, і кожна вершина зберігає [[Список (абстрактний тип даних)|список]] суміжних вершин. Ця структура даних дозволяє зберігати додаткові дані у вершинах. Додаткові дані можуть бути збережені, якщо ребра також збережені як об'єкти, і в цьому випадку кожна вершина зберігає інцидентні їй ребра, а кожне ребро зберігає інцидентні йому вершини.
; [[Матриця суміжності]]<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 529—530; {{Harvtxt|Goodrich|Tamassia|2015}}, p.&nbsp;363.</ref>
: Двовимірна матриця, в якій рядки представляють початкові вершини, а стовпці&nbsp;— кінцеві вершини. Дані про ребра та вершини повинні зберігатися окремо. Між кожною парою вершин може зберігатися лише одне ребро.
; [[Матриця інцидентності]]<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p.&nbsp;531.</ref>
: Двовимірна булева матриця, в якій рядки представляють вершини, а стовпці&nbsp;— ребра. Записи вказують, чи буде вершина в рядку інцидентною ребру у стовпчику.

У наступній таблиці наведена [[часова складність алгоритму|часову складність]] для виконання різних операцій над графами з |''V'' | кількістю вершин і |''Е'' | кількістю ребер залежно від способу представлення. У матричних представленнях записи дають вартість операції для наступного ребра. Вартість для ребер, яких немає, вважається нескінченною.
{| class="wikitable"
!
! scope="col" | Список суміжності
! scope="col" | Матриця суміжності
! scope="col" | Матриця інцидентності
|-
! class="rh heading table-rh" scope="row" {{rh2|align=left}} | Зберігати граф
| <math>O(|V|+|E|)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|\cdot|E|)</math>
|-
! class="rh heading table-rh" scope="row" {{rh2|align=left}} | Додати вершину
| <math>O(1)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|\cdot|E|)</math>
|-
! class="rh heading table-rh" scope="row" {{rh2|align=left}} | Додати ребро
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(|V|\cdot|E|)</math>
|-
! class="rh heading table-rh" scope="row" {{rh2|align=left}} | Видалити вершину
| <math>O(|E|)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|\cdot|E|)</math>
|-
! class="rh heading table-rh" scope="row" {{rh2|align=left}} | Видалити ребро
| <math>O(|V|)</math>
| <math>O(1)</math>
| <math>O(|V|\cdot|E|)</math>
|-
! class="rh heading table-rh" scope="row" {{rh2|align=left}} | Чи суміжні вершини ''x'' і ''y'' (якщо вважати, що місця їх зберігання відомі)?
| <math>O(|V|)</math>
| <math>O(1)</math>
| <math>O(|E|)</math>
|-
! class="rh heading table-rh" scope="row" {{rh2|align=left}} | Зауваження
| Повільно видаляє вершини та ребра, тому що потрібно знаходити всі вершини чи ребра
| Повільно додає або видаляє вершини, тому що матрицю потрібно змінювати розмір/копіювати
| Повільно додає або видаляє вершини та ребра, тому що матрицю потрібно змінювати розмір/копіювати
|}
Списки суміжності зазвичай є ефективнішими, оскільки вони краще представляють [[Щільний граф|розріджені графи]]. Матриця суміжності є ефективнішою, якщо граф є щільним, тобто кількість ребер |''Е''| близька до квадрату кількості вершин&nbsp;— |''V''|<sup>2</sup>, або якщо потрібно швидко знайти ребро, яке з'єднує дві вершини.<ref name="clrs">{{Вступ до алгоритмів|edition=2|chapter=Section 22.1: Representations of graphs|pages=527–531}}.</ref><ref name="gt">{{Citation|title=Algorithm Design and Applications|first=Michael T.|last=Goodrich|author-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|contribution=Section 13.1: Graph terminology and representations|pages=355–364}}.</ref>

== Див. також ==

* [[Пошук по графу]] для обходу графів
* [[Графова база даних]] для збереження графів (структур даних)
* {{Нп|Переписування графу|||Graph rewriting}} для перетворень графів заснованих на правилах
* [[Візуалізація_графів#Програмне_забезпечення|Програмне забезпечення для зображення графів]]

== Примітки ==
{{reflist}}

== Посилання ==
{{Commonscat}}
* [http://www.boost.org/libs/graph Boost Graph Library&nbsp;— потужна бібліотека на C++ для роботи з графами] {{Webarchive|url=https://web.archive.org/web/20080517081717/http://boost.org/libs/graph |date=17 травня 2008 }}, див. [[Boost]]
* [https://networkx.github.com/ Пакет Networkx для побудови графів на Python] {{Webarchive|url=https://web.archive.org/web/20130310032954/http://networkx.github.com/ |date=10 березня 2013 }}, див. [[NetworkX]]
* [http://www.graphmatcher.com GraphMatcher] {{Webarchive|url=https://web.archive.org/web/20200205201238/http://www.graphmatcher.com/ |date=5 лютого 2020 }}&nbsp;— програма на Java для вирівнювання (не)орієнтованих графів
* [http://graphblas.org GraphBLAS] {{Webarchive|url=https://web.archive.org/web/20160921202606/http://www.graphblas.org/ |date=21 вересня 2016 }}&nbsp;— специфікація інтерфейсу бібліотеки для операцій над графами, з акцентом на розріджені графи.

{{Структури даних}}

[[Категорія:Графи (теорія графів)]]
[[Категорія:Абстрактні типи даних]]
[[Категорія:Графи (структури даних)]]
[[Категорія:Теорія графів]]