Преглед на кода на Граф (структура от данни)

{{към пояснение|Граф|Граф (пояснение)}}
[[Файл:Directed graph.svg|200px|мини|Фиг. 1 – Ориентиран граф]]
[[Файл:Directed.svg|200px|мини|Граф с 3 върха и 3 ребра]]
[[Файл:Basic terms in graph theory Bulgarian.png|200px|мини|Пример за графи, използвани в графовата база от данни [[Neo4j]]]]
В [[Компютърни науки|компютърните науки]], '''граф''' (мн. ч. Графи) е [[структура от данни|абстрактна структура от данни]], имаща за цел да имплементира терминът [[Граф (математика)|граф]] от [[математика]]та.

Графът като структура от данни представлява връзките между отделните елементи на дадено [[множество]]. Всеки член на това множество се нарича '''връх''', а връзката между два върха се нарича '''ребро'''. Честата употреба на графите в практиката е довела до задълбочени изследвания в [[теория на графите]], в която са известни огромен брой задачи за графи и за повечето от тях има и добре известно решение.

Имплементацията на граф може да асоциира към всеки връх дадена '''стойност''', като ''буквено-цифрово'' означение или дадена ''стойност''(константа, капацитет, дължина и т.н.).

== История ==
Първата работа по теория на графите е статията на [[Ойлер]] за [[Седемте моста на Кьонигсберг|Кьонигсбергските мостове]] ([[1736]]). Тя обаче остава единствена в течение на 100 години. Интересът към този клон от [[математика]]та и към частния случай – [[дърво (математика)|дърветата]], се възражда около средата на 19 век и е съсредоточен главно в [[Англия]]. Върху развитието на Теорията на графите оказват забележимо влияние естествените науки, тъй като тя има приложения в различни области – при изследването на електрическите вериги, моделите на кристалите, структурата на молекулите, в теорията на игрите и програмирането, в биологията и психологията и т.н.

Терминът е употребен най-напред в статия на [[Кьониг]], а след това и в монографията му ''Theorie der endlichen und unendlichen Graphen'' („Теория на крайните и безкрайните графи“, [[1936]]), но самият Кьониг го е заимствал от статия на Шур ([[1912]]), в която граф се нарича фигура, състояща се от няколко числа или точки, някои двойки от които са съединени помежду си.

== Основни понятия ==
=== Дефиниция ===
Термин от [[математика]]та, с който се означава [[наредена двойка]] ''G=(V,E)'', където
* ''V'' е [[множество]] от елементи, наречени ''върхове'',
* ''E'' е множество от двучленни [[подмножество|подмножества]] на ''V'', т.е. ''E ⊆ V×V''. Когато в тези двучленни подмножества няма наредба, т.е. формират ненаредени двойки, е прието да се наричат ''ребра'' или още ''ръбове'' на графа, а той от своя страна – ''неориентиран (ненасочен) граф''. Когато тези двойки са наредени, елементите на ''Е'' се наричат ''дъги'', а графът ''G'' – ''ориентиран (насочен) граф''.

=== Връх ===
'''Връх''' на граф (на [[английски език]]: [[vertex]] или node) – елементи, съвкупността от които, свързани в подмножества образуват елемент от наредената двойка репрезентирана от графа.

=== Ребро (Дъга) ===
'''Дъга''' (англ.: ''arc'') за ориентиран граф, '''ребро''' (англ.: ''[[edge]]'') за неориентиран – това е релация между два върха в графа. В общия случай, дъга ''(i, j)'' бележи дали има път от i-тия връх до j-ия, като ''i-ия'' се нарича '''опашка''' (англ: ''tail''), а ''j-ия'' – '''глава''' на дъгата (англ.: ''head''). Често дъгите са свързани и със съответна стойност за преход през тях, която се нарича '''тегло''' на дъгата (англ.: ''edge value'').

=== Път ===
[[Файл:Натурализация гамильтоновых циклов.jpg|200px|мини|Три примера за хамилтонови цикли на квадратна решетка 8х8]]
'''Път''' в ориентиран (неориентиран) граф ''G(V,A'') се нарича последователност от върхове ''v1, v2, … vk'', такива че за всяко ''i = 1, 2… k-1'' е в сила ''(vi,vi+1)∈A''. Върховете ''v1'' и ''vk'' се наричат '''краища на пътя'''. Ако ''v1 = vk'', то има '''цикъл'''. Ако няма повтаряне на върхове в даден път (в частност цикъл), тогава пътят е '''прост''' (за всяко ''i≠j (1≤i,j≤k)'' следва ''vi≠vj''). Ако даден граф има път от всеки връх до всеки друг – графът е свързан. С ''O(n)'' сложност, където ''n'' е броят на дъгите, може да се определи дали даден граф е свързан или не ('''DFS''').
* '''Дължина на път''' е броят на ребрата, свързващи последователността от върхове в пътя. Този брой е равен на броят на върховете в пътя минус единица.
* '''Цена на път''' в претеглен граф, се нарича сумата от теглата на ребрата участващи в пътя.
* '''Цикъл''' (англ.: [[loop]]) в графа ''G'' е път, за който началният и крайният връх съвпадат.
** '''Прост цикъл''' – цикъл, в който няма повтарящи се възли.
** '''Хамилтонов цикъл''' – цикъл, който включва всички възли на графа точно по веднъж.
** '''Ойлеров цикъл''' – цикъл, който включва всички ребра на графа точно по веднъж.

== Видове графи ==
* '''Ориентиран граф''' (англ.: [[directed graph]]) – Фир. 1 – ребрата са насочени, изобразяват се чрез стрелки. Две ребра, свързващи еднакви върхове, но различно ориентирани, за по-голяма прегледност се изобразяват с една двупосочна стрелка.
* '''Краен неориентиран граф''' (англ.: [[undirected graph]]) се нарича наредената двойка ''(V,E)'', където:
** ''V = {v1,v2,…,vn}'' е крайно множество от върхове
** ''E = {e1, e2, …,em}'' е крайно множество от неориентирани ребра.
* '''Претеглен(тегловен)''' (англ.:[[weighted graph]]) – на всяко ребро е присвоена някаква стойност – тегло.
* [[Мултиграф]] (англ.: [[multigraph]]) – възможно е повече от едно ребро да свързва два върха (при ориентиран граф – възможно е тези ребра, освен това, да са ориентирани еднакво).
* [[Регулярен граф]] – граф, при който всеки връх има равен брой съседни върхове, т.е. всички върхове на графа са от една и съща степен.

== Алгоритми ==
Графовите [[Алгоритъм|алогоритми]] са значителна област на интерес в компютърните науки. Типични орерации от високо ниво, свързани с графите за намиране на път между два върха:
* [[Обхождане в дълбочина]].
* [[Обхождане в ширина]].
* Намиране на най-кратък път между два върха:
** [[Алгоритъм на Дейкстра]].
** [[Алгоритъм на Белман-Форд]].
** [[Алгоритъм на Флойд]](на [[английски език|английски]] език: [[Floyd–Warshall algorithm]]).

== Видове представяния ==
Съществуват много различни начини за представяне на граф в програмирането. Различните представяния имат различни свойства и кое точно трябва да бъде избрано, зависи от конкретния алгоритъм, който трябва да се приложи. Ето някои от най-често срещаните представяния на графи:
* '''Списък на ребрата''' – представя се, чрез списък от наредени двойки ''(vi, vj)'', където съществува ребро от ''vi'' до ''vj''. Ако графът е претеглен, то вместо наредена двойка имаме наредена тройка, като третият ѝ елемент показва какво е теглото на даденото ребро.
* '''Списък на наследниците''' (англ.: [[Adjacency list]]) – в това представяне за всеки връх ''v'' се пази списък с върховете, към които сочат ребрата започващи от ''v''. Тук отново, ако графът е претеглен, към всеки елемент от списъка с наследниците се добавя допълнително поле, показващо цената на реброто до него.
* '''Матрица на съседство''' (англ.: [[Adjacency matrix]]) – графът се представя като квадратна матрица ''g[N][N]'', в която, ако съществува ребро от ''vi'' до ''vj'', то на позиция ''g[i][j]'' в матрицата е записано 1. Ако такова ребро не съществува, то в полето ''g[i][j]'' е записано 0. Ако графът е претеглен, в позиция ''g[i][j]'' се записва теглото на даденото ребро, а матрицата се нарича матрица на теглата. Ако между два върха в такава матрица не съществува път, то тогава се записва специална стойност, означаваща безкрайност.
* '''Матрица на инцидентност между върхове и ребра''' (англ.: [[Incidence matrix]]) – в този случай отново се използва матрица, само че с размери ''g[M][N]'', където ''М'' е броят на върховете, а ''N'' е броят на ребрата. Всеки стълб представя едно ребро, а всеки ред един връх. Тогава в стълба съответстващ на реброто ''(vi, vj)'' само и единствено на позиция ''i'' и на позиция ''j'' ще бъдат записани 1, а на останалите позиции в този стълб ще е записана 0. Ако реброто е примка т.е. е ''(vi, vi)'', то на позиция ''i'' се записва 2. Ако графът, който се представя е ориентиран и се иска да се предсрави ребро от ''vi'' до ''vj'', то на позиция ''i'' се пише 1, а на позиция ''j'' съответно -1.

Следващата таблица предсвавя [[Теория на изчислителната сложност|изчислителната сложност]], нужна за извършването на дадени операции за даден вид представяне.

{| class="wikitable"
|-
!
! Списък на наследниците
! Матрица на съседство
! Матрица на инцидентност
|-
| Заемано ространсво
| <math> O(|V|+|E|) </math>
| <math> O(|V|^2) </math>
| <math> O(|V|\cdot|E|) </math>
|-
| Добавяне на връх
| <math> O(1) </math>
| <math> O(|V|^2) </math>
| <math> O(|V|\cdot|E|) </math>
|-
| Добавяне на ребро
| <math> O(1) </math>
| <math> O(1) </math>
| <math> O(|V|\cdot|E|) </math>
|-
| Изтриване на връх
| <math> O(|E|) </math>
| <math> O(|V|^2) </math>
| <math> O(|V|\cdot|E|) </math>
|-
| Изтриване на ребро
| <math> O(|E|) </math>
| <math> O(1) </math>
| <math> O(|V|\cdot|E|) </math>
|-
| Забележки
| При премахване на върхове или ребра, трябва да бъдат намерени всички ребра и върхове
| Бавен при премахване/добавяне на върхове, защото цялата матрица трябва да се оразмери
| Бавен при премахване и добавяне на ребра и върхове, защото цялата матрица трябва да се преоразмери/копира
|}

== Операции ==
Основните [[Команда (шаблон)|операции]] свързани със структура от данни – граф ''G'' обикновено включват:
* <code>adjacent</code>(''G'', ''x'', ''y''): проверка дали има път от връх ''x'' до връх ''y''.
* <code>neighbors</code>(''G'', ''x''): изкарва всички върхове ''y'' който осигуряват път между ''x'' и ''y''.
* <code>add</code>(''G'', ''x'', ''y''): добавя към ''G'' ребро(дъга) от ''x'' към ''y'', ако все още не съществува.
* <code>delete</code>(''G'', ''x'', ''y''): премахва реброто от ''x'' към ''y'', ако съществува.
* <code>get_node_value</code>(''G'', ''x''): връща стойността асоциирана с върха ''x''.
* <code>set_node_value</code>(''G'', ''x'', ''a''): присвоява на върха ''x'' стойност ''a''.

Към графи, в който са асоциирани стойности към ребрата, обикновено са включени следните команди(операции):
* <code>get_edge_value</code>(''G'', ''x'', ''y''): връща стойността на реброто (''x'',''y'').
* <code>set_edge_value</code>(''G'', ''x'', ''y'', ''v''): присвоява на дъгата (''x'',''y'') стойността ''v''.

== Основни приложения и задачи за графи<ref>{{cite book | last = Светлин Наков и колектив | year = 2009 | title = [http://www.introprogramming.info/intro-java-book/ Въведение в програмирането с Java] | publisher = Фабер | location = | pages = 653 – 662 | isbn = 978-954-400-055-4 | ref = harv}}</ref> ==
Графите се използват за моделиране на много ситуации от реалността, а задачите върху графи моделират множество реални проблеми, които често се налага да бъдат решавани:
* Карта на град може да се моделира с ориентиран претеглен граф. На всяка улица се съпоставя ребро с дължина съответстваща на дължината на улицата и посока – посоката на движение. Ако улицата е двупосочна може да ѝ се съпоставят две ребра за двете посоки на движение. На всяко кръстовище се съпоставя връх. При такъв модел са е стествени задачи като търсене на най-кратък път между две кръстовища, проверка дали има път между две кръстовища, проверка за цикъл (дали можем да се завъртим и да се върнем на изходна позиция), търсене на път с минимален брой завои и т.н.
* Компютърна мрежа може да се моделира с неориентиран граф, чиито върхове съответстват на компютрите в мрежата, а ребрата съответстват на комуникационните канали между компютрите. На ребрата могат да се съпоставят различни числа, примерно капацитет на канала или скорост на обмена и др. Типични задачи при такива модели на компютърна мрежа са проверка за свързаност между два компютъра, проверка за двусвързаност между две точки (съществуване на двойно-подсигурен канал, който остава при отказ на който и да е компютър) и др. В частност Интернет може да се моделира като граф, в който се решават задачи за маршрутизация на пакети, които се моделират като задачи за графи.
* Речната с истема в даден регион може да се моделира с насочен претеглен граф, в който всяка река се състои от едно или няколко ребра, а всеки връх съответства на място, където две или повече реки се вливат една в друга. По ребрата могат да се съпоставят стойности, свързани с количеството вода, което преминава по тях. Естествени при този модел са задачи като изчисление на обемите вода, преминаващи през всеки връх и предвиждане на евентуални наводнения при увеличаване на количествата.

== Вижте също ==
* [[Теория на графите]]
* [[Граф (математика)]]
* [[Структура от данни]]
** [[Дърво (структура от данни)]]
** [[Стек (структура от данни)]]
** [[Списък (абстрактен тип данни)]]

== Източници ==
* [https://www.youtube.com/playlist?list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P MyCodeSchool – Data structures]
* Светлин Наков, Веселин Колев и др., „[http://www.introprogramming.info/ Въведение в програмирането]“, Фабер, 2009. ISBN 978-954-400-527-6.
* Иржи Седлачек, „Теория на графите“, „Наука и изкуство“, София, 1967
* Красимир Манев, „Увод в дискретната математика“, издателство КЛМН, София, 2003, ISBN 954-535-136-5

== Вътрешни препратки ==
<references/>

== Външни препратки ==
* [http://www.mycodeschool.com/ My Code School] {{Webarchive|url=https://web.archive.org/web/20150502180039/http://www.mycodeschool.com/ |date=2015-05-02 }}
* [http://vista-2008.com/wp-content/uploads/custom/Grafi/ Увод в теория на графите]
* {{икона|en}} [http://www.introprogramming.info/ Въведение в програмирането]
* [http://www.programirane.org/ Програмиране=++Алгоритми]

[[Категория:Структури от данни|Структури от данни]]
[[Категория:Теория на графите|Теория на графите]]