Увод у граф у структури података
Графови су нелинеарне структуре података које садрже коначни скуп чворова и ивица. Чворови су елементи и рубови су поредани парови веза између чворова.
Примјетите ријеч нелинеарна. Нелинеарна структура података је она у којој елементи нису распоређени у редним редоследом. На пример, низ је линеарна структура података јер су елементи распоређени један за другим. Можете прећи све елементе матрице у једном покрету. То није случај са нелинеарним структурама података. Елементи нелинеарне структуре података распоређени су у више нивоа, често пратећи хијерархијски образац. Графикони су нелинеарни.
Следећа реч на коју треба обратити пажњу је коначна. Граф дефинирамо тако да има коначан и бројив број чворова. Ово је прилично нескладан термин. У суштини, граф може имати неограничен број чворова и још увек је коначан. На пример, породично стабло које сеже од Адама и Еве. Ово је релативно бесконачан граф, али се и даље може рачунати и зато се сматра коначним.
Пример из реалног света
Најбољи пример графова у стварном свету је Фацебоок. Свака особа на Фацебооку је чвор и повезана је преко ивица. А је пријатељ Б. Б је пријатељ Ц и тако даље.
Терминологиес
Овде су наведене Терминологије графикона у структури података
1. Графички приказ: Граф је генерално представљен као пар скупова (В, Е). В је скуп врхова или чворова. Е је скуп ивица. У горњем примеру,
В = (А, Б, Ц, Д, Е)
Е = (АБ, АЦ, АД, БЕ, ЦД, ДЕ)
2. Чвор или Вертек: Елементи графикона повезани су преко ивица.
3. Ивице: Пут или линија између две врхове у графу.
4. Суседни чворови: Два чвора називају се сусједна ако су повезана преко ивице. У горњем примеру, чвор А је уз чворове Б, Ц и Д, али не и чвор Е.
5. Пут: Стаза је низ ивица између два чвора. То је у суштини кретање које почиње на једном чвору и завршава на другом. У горњем примјеру, постоји више путања од чвора А до чвора Е.
Пут (А, Е) = (АБ, БЕ)
ИЛИ
Пут (А, Е) = (АЦ, ЦД, ДЕ)
ИЛИ
Пут (А, Е) = (АД, ДЕ)
6. Неизређени графикон: Неусмерени граф је онај где ивице не одређују одређени правац. Ивице су двосмерне.
Пример
Према томе, у овом примеру се рубни АЦ може прећи од А до Ц и од Ц до А. Слично свим ивицама. Пут од чвора Б до чвора Ц био би (БА, АЦ) или (БД, ДЦ).
7. Усмерени граф: Усмерени граф је онај где се ивице могу кретати само у одређеном смеру.
Пример
Тако су у истом примеру сада ивице усмерене. Можете само да пређете ивицу дуж његовог смера. Сада нема путање од чвора Б до чвора Ц сада.
8. Графички пондерисани графикон: Пондерирани графикон је онај где су ивице повезане са тежином. То је генерално трошак преласка ивице.
Пример
Дакле, у истом примјеру сада ивице имају одређену тежину повезану са њима. Постоје два могућа путања између чвора А до чвора Е.
Патх1 = (АБ, БД, ДЕ), Тежина1 = 3 + 2 + 5 = 10
Патх2 = (АЦ, ЦД, ДЕ), Тежина2 = 1 + 3 + 5 = 9
Јасно је да би радије био Патх2 ако је циљ достићи чвор Е из чвора А уз минималне трошкове.
Основне операције на графу
Овде су наведене основне операције графикона
1. Додавање / уклањање вертекса
Ово је најједноставнија операција на графикону. Једноставно додате тачку у графикон. Не мора бити повезан са било којим другим врхом преко ивице. Када уклањате вертекс, морате уклонити све ивице које потичу из краја и завршавају на избрисаном вертексу.
2. Додавање / уклањање ивица
Ова операција додаје или уклања ивицу између две врхове. Када се бришу све ивице које потичу од врха и завршавају их, она постаје изолована.
3. Прва потрага за крухом (БФС)
Ово је пречна операција на графу. БФС хоризонтално прелази граф. То значи да прелази све чворове на једном нивоу пре него што пређе на следећи ниво.
БФС алгоритам започиње на врху првог чвора на графикону, а затим пролази кроз све сусједне чворове на њему. Једном када се прелазе сви суседни чворови, алгоритам понавља исти поступак за дечије чворове.
Пример
Помицање горњег графа на начин БФС резултирало би из А -> Б -> Ц -> Д -> Е -> Ф -> Г. Алгоритам полази од чвора А и пролази кроз све његове суседне чворове Б, Ц и Д. сва четири чворова као посећена. Једном када су прешли сви суседни чворови А, алгоритам прелази на први суседни чвор А и понавља исти поступак. У овом случају, чвор је Б, а суседни чворови на Б су Е и Ф. Даље, суседни чворови на Ц пролазе. Након што су посећени сви чворови, операција се завршава.
4. Прва дубина (ДФС)
Дубина прве претраге или ДФС прелази граф вертикално. Почиње коријенским чвором или првим чвором графикона и прелази све подређене чворове прије него што пређе на сусједне чворове.
Пример
Помицање горњег графа на начин БФС резултирало би из А -> Б -> Е -> Ф -> Ц -> Г -> Д. Алгоритам почиње од чвора А и пролази кроз све његове подређене чворове. Чим наиђе на Б, чини се да има даље дечије чворове. Дакле, дечји чворови Б се прелазе пре него што пређу на следећи дечји чвор А.
Реална имплементација графикона
- Дизајн електричних кола за пренос снаге.
- Дизајн мреже међусобно повезаних рачунара.
- Проучавање молекуларне, хемијске и ћелијске структуре било које материје, нпр. Људске ДНК.
- Дизајн транспортних рута између градова и места у граду.
Закључак - Графикон у структури података
Графови су веома користан концепт у структурама података. Има практичне имплементације у готово свим областима. Веома је важно разумјети основе теорије графова, развити разумијевање алгоритама структуре графова.
Овај чланак је био само увод у графиконе. То је само одскочни камен. Препоручује се дубље заронити даље у теми теорије графова.
Препоручени чланци
Ово је водич за граф у структури података. Овде смо расправљали о терминологијама и основним операцијама графикона у структури података. Такође можете погледати следећи чланак да бисте сазнали више -
- Питања за интервју о структури података
- Модел података у Цассандри
- Шта је Дата Март?
- Шта је Дата Сциентист?