Графът е структура от данни изградена от върхове (възли) и връзки между тях, които се наричат ребра. Ако ребрата имат посока графът е ориентиран, в противен случай е неориентиран. Ребрата могат да имат и тегло (или дължина). Тогава се казва, че графът е претеглен. Свързаните списъци и дърветата са частни случаи на графи. Ето пример за ориентиран, претеглен граф:

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

Повече за социалните мрежи, услугите, които предлагат и софтуерът за тях може да научите от Wikipedia.
Повече за теория на графите може да научите от сайта на доц. Манев.

Един възможен начин за представяне на граф е чрез матрицата на съседство. Тя се състои от n реда и n стълба, където n е броят на върховете в графа. Всеки ред и стълб съответстват на конкретен връх. Ако има ребро между връх 1 и връх 2 то елементът на позиция [1][2] е 1, а ако няма ребро - 0. Матрицата на съседство за горния граф изглежда по следния начин:

	0	1	1	0	0
	0	0	1	0	1
	0	0	0	1	0
	0	0	0	0	0
	0	0	0	1	0

На позиция [2][1] има 0, защото няма ребро от връх 2 към връх 1.
Когато графът е претеглен вместо единици можем да записваме теглото на ребрата:

	0	10	9	0	0
	0	0	13	0	15
	0	0	0	24	0
	0	0	0	0	0
	0	0	0	8	0

Друг вариант за представяне е матрицата на инцидентност. В нея редовете представляват върховете, а стълбовете ребрата. Елементът на позиция [i][j] е -1 ако реброто j излиза от върха i, 1 ако реброто j влиза във върха i и 0 в противен случай. За горния граф матрицата на инцидентност изглежда така:

	−1	−1	0	0	0	0
	1	0	−1	−1	0	0
	0	1	1	0	−1	0
	0	0	0	0	1	1
	0	0	0	1	0	−1

Ако забелязвате в матриците на съседство има много елементи със стойност 0. Такива матрици се наричат разредени. При големи графи тези матрици заемат много излишна памет, затова е по-удачно да използваме динамична памет за представянето на графите. Това може да стане, чрез списъци на съседство. За всеки връх от графа има списък, в който се намират номерата на съседните му върхове. Списъците могат да се пазят в масив. Ако искаме да представим претеглен граф ще трябва да съхраняваме информация и за дължината на ребрата:

Можем в клас Ребро да съхраняваме номера на върха, в който влиза реброто и дължината му. Това е направено във файла graph.cpp. Той ползва файловете list.h, stack_no_elem.h и queue_no_elem.h. В последните два е премахната декларацията на структурата Elem, тъй като тя вече е деклариране в list.h

Във файла по-горе са реализирани и два алгоритъма за обхождане на граф: в дълбочина и в широчина.

При обхождането в дълбочина се тръгва от някакъв начален връх и се преминава към негов наследник, след което към наследник на наследника и така, докато се стигне връх без наследници (от който не излизат ребра). Тогава се прави връщане назад към предишния връх.

При обхождането в широчина се тръгва от някакъв начален връх и се обхождат всички негови наследници, чак след това се обхождат наследниците на наследниците.

Нека е даден графът:

Ако обхождаме наследниците на един връх в нарастващ ред на номерата им, тогава:
при обхождането в дълбочина, върховете ще се обходят в следната последователност: 1 2 4 8 9 5 10 3 6 11 7;
при обхождането в широчина, последователността ще е: 1 2 3 4 5 6 7 8 9 10 11.

Нека е даден друг граф:

Ако обхождаме наследниците на един връх в нарастващ ред на номерата им, тогава:
при обхождането в дълбочина, върховете ще се обходят в следната последователност: 1 2 4 5 9 10 8 3 6 7;
при обхождането в широчина, последователността ще е: 1 2 3 4 5 6 7 8 9 10.

За да обходим в дълбочина графа можем да приложим следния алгоритъм:

За да обходим в широчина графа можем да приложим следния алгоритъм:

Интересни задачи и алгоритми свързани с графи са:
- алгоритъмът на Дейкстра за намиране на най-къс път между два върха;
- намиране на минимално покриващо дърво: Stony Brook University, mst2007.hit.bg
- откриването на Хамилтонов цикъл в граф;
- конструирането на Ойлеров път в граф. За първи път този проблем е разглеждан от Леонард Ойлер, докато решава проблема за Кьонигсбергските мостове;
и други алгоритми за графи.

Главна страница

<< Упражнение 7 - Дървета

Упражнение 9 - Динам. оптимиране, Връщане назад >>

Траян Момков е автор на сайта и материалите в него, с изключение на тези, за които изрично е упоменато друго.
Забранено е копирането им по какъвто и да било начин освен след изрично разрешение от автора.