Ефикасном програмеру је потребно добро разумевање структура података и алгоритама. Технички интервјуи ће често тестирати ваше вештине решавања проблема и критичког размишљања.
Графови су једна од многих важних структура података у програмирању. У већини случајева, разумевање графова и решавање проблема заснованих на графовима није лако.
Шта је графикон и шта треба да знате о њему?
Шта је граф?
Граф је нелинеарна структура података која има чворове (или врхове) са ивицама које их повезују. Сва стабла су подтипови графова, али нису сви графови стабла, а граф је структура података из које су стабла настала.
Иако можете граде структуре података у ЈаваСцрипт-у и другим језицима, можете имплементирати графикон на различите начине. Најпопуларнији приступи су ивице листе, листе суседности, и матрице суседности.
Тхе Кхан Ацадеми водич за представљање графова је одличан ресурс за учење о томе како представити граф.
Постоји много различитих типова графикона. Једна уобичајена разлика је између усмерено и неусмерено графови; ови се често појављују у изазовима кодирања и употребе у стварном животу.
Врсте графикона
- Усмерени графикон: Граф у коме све ивице имају правац, који се такође назива диграф.
- Неусмерени граф: Неусмерени граф је такође познат као двосмерни граф. У неусмереним графовима, правац ивица није битан, а прелазак може ићи у било ком смеру.
- Пондерисани графикон: Пондерисани граф је граф чији чворови и ивице имају придружену вредност. У већини случајева, ова вредност представља цену истраживања тог чвора или ивице.
- Коначан граф: Граф који има коначан број чворова и ивица.
- Бесконачан графикон: Граф који има бесконачну количину чворова и ивица.
- Тривијалан графикон: Граф који има само један чвор и без ивице.
- Једноставан графикон: Када само једна ивица повезује сваки пар чворова графа, назива се једноставним графом.
- Нулл график: Нулти граф је граф који нема ивице које повезују његове чворове.
- мултиграф: У мултиграфу, најмање пар чворова има више од једне ивице која их повезује. У мултиграфима не постоје само петље.
- Комплетан графикон: Потпуни граф је граф у коме се сваки чвор повезује са сваким другим чвором у графу. Такође је познат као а пун графикон.
- Псеудо график: Граф који има самопетљу поред других ивица графа назива се псеудо граф.
- Редовни графикон: Регуларни граф је граф где сви чворови имају једнаке степене; тј. сваки чвор има исти број суседа.
- Повезани графикон: Повезани граф је једноставно било који граф у коме се повезују било која два чвора; односно граф са најмање једном путањом између свака два чвора графа.
- Неповезани графикон: Неповезани граф је директна супротност повезаном графу. У неповезаном графу, нема ивица које повезују чворове графа, као што је а нула граф.
- Циклични графикон: Циклични граф је граф који садржи најмање један циклус графа (пут који се завршава тамо где је почео).
- Ациклични графикон: Ациклични граф је граф без циклуса. Може бити усмјерено или неусмјерено.
- Подграф: Подграф је изведени граф. То је граф формиран од чворова и ивица које су подскупови другог графа.
А петља у графу је ивица која почиње од чвора и завршава се на истом чвору. Стога, а селф-лооп је петља преко само једног чвора графа, као што се види на псеудо графу.
Алгоритми преласка графа
Будући да је тип нелинеарне структуре података, прелазак графа је прилично тежак. Прелазак кроз граф значи пролазак и истраживање сваког чвора с обзиром да постоји исправна путања кроз ивице. Алгоритми за обилажење графа су углавном два типа.
- Претрага у ширину (БФС): Претрага у ширину је алгоритам обиласка графа који посећује чвор графа и истражује његове суседе пре него што пређе на било који од његових подређених чворова. Иако можете почети да прелазите преко графа из било ког изабраног чвора, коренски чвор је обично пожељна полазна тачка.
- Претрага у дубину (ДФС): Ово је други главни алгоритам обиласка графа. Посећује чвор графа и истражује његове подређене чворове или гране пре него што пређе на следећи чвор – то јест, прво иде дубоко пре него што се шири.
Претрага у ширину је препоручени алгоритам за проналажење путања између два чвора што је брже могуће, посебно најкраће путање.
Претрага у дубину се углавном препоручује када желите да посетите сваки чвор на графикону. Оба алгоритма преласка раде добро у сваком случају, али један може бити једноставнији и оптимизованији од другог у одабраним сценаријима.
Једноставна илустрација може помоћи да боље разумете оба алгоритма. Замислите стања неке земље као графикон и покушајте да проверите да ли су две државе, Икс и И, су повезани. Потрага у дубину могла би да крене путем скоро широм земље, а да то није довољно рано схватила И удаљен је само 2 државе Икс.
Предност претраге у ширину је у томе што одржава близину тренутног чвора што је више могуће пре него што пређе на следећи. Наћи ће везу између Икс и И за кратко време без потребе за истраживањем целе земље.
Још једна велика разлика између ова два алгоритма је у начину на који су имплементирани у коду. Претрага у ширину је ан итеративни алгоритам и користи а куеуе, док се претрага у дубину обично имплементира као а рекурзивни алгоритам који утиче на гомила.
Испод је неки псеудокод који показује имплементацију оба алгоритма.
Претрага у ширину
бфс (Графикон Г, корен ГрапхНоде) {
дозволити к бити Нова Куеуе// означи корен као посећен
роот.виситед = истинито// додај роот у ред
к.енкуеуе(корен)
док (к није празан) {
дозволити тренутно је к.декуеуе() // уклони предњи елемент у реду
за (суседи н струје у Г) {
ако (н јене још посећено) {
// додати у ред - тако да можете истражити и његове суседе
к.енкуеуе(н)
н.посетио = истинито
}
}
}
}
Претрага у дубину
дфс (Графикон Г, корен ГрапхНоде) {
// основни случај
ако (корен је нула) повратак// означи корен као посећен
роот.виситед = истинито
за (суседи н корена у Г)
ако (н јене још посећено)
дфс (Г, н) // рекурзивни позив
}
Неколико других алгоритама за обилажење графова произилази из претраживања у ширину и у дубину. Најпопуларнији су:
- Двосмерна претрага: Овај алгоритам је оптимизован начин проналажења најкраћег пута између два чвора. Користи две претраге у ширину које се сударају ако постоји пут.
- Тополошка сорта: Ово се користи у усмерени графови да сортирате чворове у жељеном редоследу. Не можете применити тополошко сортирање на неусмерене графове или графове са циклусима.
- Дијкстрин алгоритам: Ово је такође врста БФС. Такође се користи за проналажење најкраћег пута између два чвора у а пондерисани усмерени граф, који може имати циклусе или не.
Уобичајена питања за интервју заснована на графиконима
Графикони су међу важним структуре података које сваки програмер треба да зна. Често се постављају питања на ову тему у техничким интервјуима, а можда ћете наићи на неке класичне проблеме у вези са том темом. То укључује ствари као што су проблеми „градски судија“, „број острва“ и „путујући продавац“.
Ово су само неки од многих популарних проблема интервјуа заснованих на графовима. Можете их испробати ЛеетЦоде, ХацкерРанк, или ГеексфорГеекс.
Разумевање структура података графикона и алгоритама
Графикони нису корисни само за техничке интервјуе. Имају и случајеве употребе у стварном свету, као што је у умрежавање, мапе, и авио-системи за проналажење рута. Они се такође користе у основној логици рачунарских система.
Графикони су одлични за организовање података и за помоћ у визуелизацији сложених проблема. Међутим, графиконе треба користити само када је то апсолутно неопходно да би се спречила сложеност простора или проблеми са меморијом.