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

Упражнение 8 - Графи

Графи

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

Структура от данни граф

Теория на графите е обширен дял от математиката с много приложения, примерно изучаването на социалните мрежи, една от които е доста използвана от студентите в момента (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
- откриването на Хамилтонов цикъл в граф;
- конструирането на Ойлеров път в граф. За първи път този проблем е разглеждан от Леонард Ойлер, докато решава проблема за Кьонигсбергските мостове;
и други алгоритми за графи.

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