Структуре података 101: Графикони - Визуелни увод за почетнике

Упознајте структуре података које свакодневно користите

? Добродошли! Почнимо са неким виталним контекстом. Да те питам нешто:

✅ Да ли користите Гоогле претрагу?

✅ Да ли користите Гоогле Мапс?

✅ Да ли користите веб локације на друштвеним мрежама?

Ако је ваш одговор „да“ на било које од ових питања, онда сте дефинитивно користили графиконе, а нисте то ни знали! Изненађени? ? И ја сам био! Овај чланак ће вам дати визуелни увод у свет графикона, њихову намену, елементе и врсте.

Ове структуре података су ми заиста привукле пажњу због својих невероватних могућности. Они су толико моћни да нећете ни замислити колико разнолике могу бити њихове стварне апликације. Почнимо! ?

Апплицатионс Апликације из стварног света - чаролија почиње!

Графикони се користе у разним индустријама и областима:

  • ГПС системи и Гоогле мапе користе графиконе да би пронашли најкраћи пут од једног одредишта до другог.
  • Друштвене мреже користе графиконе за представљање веза између корисника.
  • Алгоритам Гоогле претраге користи графиконе за одређивање релевантности резултата претраге.
  • Операциона истраживања су област која користи графиконе за проналажење оптималног пута за смањење трошкова превоза и испоруке добара и услуга.
  • Чак се и Хемија користи графиконимада представљају молекуле !!! ❤

Њихове апликације су невероватне, зар не?

Почнимо наше путовање кроз овај свет! ?

Упознајте графиконе!

Сад кад имате неки контекст, кренимо од разговора о њиховој главној сврси и елементима.

Графикони се користе за представљање, проналажење, анализу и оптимизацију веза између елемената (кућа, аеродрома, локација, корисника, чланака итд.).

Ово је пример како графикон изгледа:

? Грађевински блокови

Сигуран сам да сте приметили два главна елемента на горњем дијаграму: кругове и дебеле линије које их повезују. Они се зову, односно, чворови и Ивице .

Да их видимо детаљније! ?

  • Чворови: они су елементи који креирају мрежу. Могли би представљати куће, локације, аеродроме, луке, аутобуска стајалишта, зграде, кориснике, у основи све што бисте могли представити као повезано са другим сличним елементима у мрежи.
  • Ивице: они су везе између чворова. Они могу представљати улице, летове, аутобуске руте, везу између два корисника на друштвеној мрежи или било шта што би могло представљати везу између чворова у контексту са којим радите.

? Шта се дешава ако нема везе?

Ако два чвора нису повезана ивицом, то значи да између њих нема директне везе. Али не паничите! ? Можда ћете и даље моћи да пређете са једног чвора на други пратећи низ ивица, слично вожњи кроз неколико улица до вашег крајњег одредишта. ? ? ?

На пример, на доњем дијаграму, иако не постоји директна веза ( ивица ) између љубичастог чвора (лево) и жутог чвора (десно), можете ићи од љубичастог чвора до наранџастог чвора, до розе чвора, до зеленог чвора, и на крају доћи до жутог чвора. ?

Ово је кључни аспект графикона, који можете тражити по елементу који тражите пратећи доступне путање.

Татион Означавање и терминологија

Веома је важно научити формални „језик“ за рад са графиконима:

  • |V|= Укупан број врхова ( чворова ) на графикону.
  • |E|= Укупан број веза ( ивица ) на графикону.

У доњем примеру, |V| = 6јер постоји шест чворова (кругова) и

|E| = 7јер има седам ивица (линија).

Врсте графикона

Графикони се класификују на основу карактеристика њихових ивица (веза). Погледајмо их детаљно! ?

1⃣ Усмерени графикони

У усмереним графиконима ивице имају правац. Прелазе са једног чвора на други и кроз ту ивицу нема начина да се врате у почетни чвор.

Као што видите на доњем дијаграму, ивице (везе) сада имају стрелице које упућују на одређени правац. Замишљајте ове ивице као једносмерне улице. Можете да идете у једном смеру и стигнете до одредишта, али не можете да се вратите том истом улицом, па треба да пронађете алтернативни пут.

На пример, ако креирамо графикон за услугу доставе пице, који представља град, две куће (чворови) могу бити повезане једносмерном улицом (ивицом). Овом улицом сте могли да стигнете од куће А до куће Б, али се нисте могли вратити, па бисте морали да идете алтернативним путем.

? Напомена: У усмереном графикону можда се уопште нећете моћи вратити на своју почетну локацију ако не постоји путања са одговарајућим упутствима. ? На доњем дијаграму можете видети да можете успешно да пређете од љубичастог до зеленог, али приметите да не постоји начин да се вратите од зеленог до љубичастог, јер су ивице „једносмерне улице. ”

2⃣ Неусмерени графикони

У овој врсти графика ивице су усмерене (немају одређени правац). Неусмерене ивице сматрајте двосмерним улицама. Можете прећи са једног чвора на други и вратити се истим тим „путем“.

? Напомена: Када видите дијаграм графикона где ивице немају стрелице усмјерене у одређеном смјеру, можете претпоставити да је графикон неусмјерен.

? За нашу услугу доставе пице то би значило да мотоцикл за доставу може да иде од извора до одредишта истом улицом или стазом (На њихово олакшање! ?).

На доњем графикону можете ићи од љубичастог до зеленог чвора и вратити се истим путем , тако да не дођете до тачке без повратка. ?

? Тегови? - Да, тегови!

1⃣ Пондерисани графикони

У пондерисаним графиконима свака ивица има повезану вредност (која се назива тежина) . Ова вредност се користи за представљање одређене мерљиве везе између чворова које повезују.

На пример, пондери могу представљати удаљеност, време, број веза које деле два корисника на друштвеној мрежи или било шта друго што се може користити за описивање везе између чворова у контексту са којим радите.

Те тежине користи Дијкстрин алгоритам за оптимизацију рута проналажењем најкраћих или најскупљих стаза између чворова у мрежи. (Пратите чланак о Дијкстрином алгоритму!!).

2⃣ Непондерисани графикони

Насупрот томе, непондерисани графикони немају пондере повезане са својим ивицама. Пример ове врсте графикона може се наћи у друштвеним мрежама, где ивице представљају везу између два корисника. Веза се не може квантификовати. Према томе, ивица нема тежину.

? Напомена: Можда сте приметили да до сада наши графови имају само једну ивицу која повезује сваки пар чворова. Природно је запитати се може ли бити више од једне ивице између пара чворова. У ствари, то је могуће са М ултиграфима! Т. хеј може имати више ивице повезују исти пар чворова.

? Број ивица! - важан фактор

Веома је важно знати да ли графикон има много или мало ивица, јер је то пресудан фактор за одлучивање како ћете представити ову структуру података у свом коду. Да видимо различите врсте! ?

1⃣ Густи графикони

Густи графикони имају много ивица. Али чекај! Кнов Знам о чему мораш размишљати, како можеш утврдити шта се квалификује као „много ивица“? Ово је мало превише субјективно, зар не? Слажем се са вама, па хајде да га мало квантификујемо:

Финд Пронађимо максималан број ивица у усмереном графикону. Ако |V|у усмереном графу постоје чворови (у доњем примеру шест чворова), то значи да сваки чвор може имати највише |v|веза (у примеру доле шест веза).

Зашто? Зато што би се сваки чвор могао потенцијално повезати са свим осталим чворовима и са собом (погледајте „петљу“ доле) . Стога максималан број ивица које граф може имати је , што је укупан број чворова помножен са максималним бројем прикључака да сваки чвор може имати.|V|*|V|

Када је број ивица на графикону близак максималном броју ивица, графикон је густ. ?

? Напомена: „Петље“ се јављају када чвор има ивицу која га повезује са собом. Чудно и занимљиво, зар не? ?

2⃣ Проређени графикони

Проређени графикони имају мало ивица. Као што видите на доњем дијаграму, нема много веза између чворова.

Када је број ивица на графикону знатно мањи од максималног броја ивица, графикон је оскудан. ?

Упознајте циклусе!

Сада да видимо витални концепт за разумевање графикона, циклуса.

Вероватно сте приметили да ако следите низ веза на графикону, можда ћете пронаћи путању која ће вас вратити до истог чвора. Ово је попут „ходања у кругу“, тачно као да се возите по свом граду и кренете стазом која вас може вратити на почетну локацију.

На графиконима се ови „кружни“ путеви називају „циклусима“. То су важеће путање које почињу и завршавају се на истом чвору. На пример, на доњем дијаграму можете видети да ако започнете на било ком чвору, можете се вратити на исти чвор пратећи ивице.

Циклуси нису увек „изоловани“, јер могу бити део већег графикона. Можете их открити покретањем претраживања на одређеном чвору и проналажење путање која вас води до истог чвора.

? Укратко ...

  • Графови су сјајне структуре података које свакодневно користите путем Гоогле претраге, Гоогле мапа, ГПС-а и друштвених медија.
  • Користе се за представљање елемената који деле везе .
  • Елементи на графикону називају се Чворови, а везе између њих Ивице .
  • Графови могу бити усмерени када њихове ивице имају специфичну оријентацију, сличну једносмерним улицама, или неусмерене, када њихове ивице немају одређену оријентацију, слично двосмерним улицама.
  • Ивице могу имати повезану вредност, која се назива тежина .
  • Ако граф има много ивица, назива се густ граф. У супротном, ако има мало ивица, назива се проређени граф.
  • Низ веза може да формира циклус ако креира путању која вам омогућава повратак на исти чвор.

Наставите да учите о овим невероватним структурама података! Исплатиће се за вашу будућност као програмера. Тренутно учим о структурама података и сматрам их потпуно фасцинантнима. ? ? ❤

Важно је да не престанете да испитујете. Знатижеља има свој разлог постојања. - Алберт Ајнштајн

? Хвала!

Заиста се надам да вам се свидео мој чланак. ❤

Прати ме; прати ме уТвиттер. ?