Водич за структуру података графикона

Ефикасном програмеру је потребно добро разумевање структура података и алгоритама. Технички интервјуи ће често тестирати ваше вештине решавања проблема и критичког размишљања.

Графови су једна од многих важних структура података у програмирању. У већини случајева, разумевање графова и решавање проблема заснованих на графовима није лако.

МАКЕУСЕОФ ВИДЕО ДАНА

Шта је графикон и шта треба да знате о њему?

Шта је граф?

Граф је нелинеарна структура података која има чворове (или врхове) са ивицама које их повезују. Сва стабла су подтипови графова, али нису сви графови стабла, а граф је структура података из које су стабла настала.

Иако можете граде структуре података у ЈаваСцрипт-у и другим језицима, можете имплементирати графикон на различите начине. Најпопуларнији приступи су ивице листе , листе суседности , и матрице суседности .

Тхе Кхан Ацадеми водич за представљање графова је одличан ресурс за учење о томе како представити граф.

Постоји много различитих типова графикона. Једна уобичајена разлика је између усмерено и неусмерено графови; ови се често појављују у изазовима кодирања и употребе у стварном животу.

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

Усмерени граф: Граф у коме све ивице имају правац, који се такође назива диграф.
Неусмерени граф: Неусмерени граф је такође познат као двосмерни граф. У неусмереним графовима, правац ивица није битан, а прелазак може ићи у било ком смеру.
Пондерисани графикон: Пондерисани граф је граф чији чворови и ивице имају придружену вредност. У већини случајева, ова вредност представља цену истраживања тог чвора или ивице.
Коначан граф: Граф који има коначан број чворова и ивица.
Бесконачан графикон: Граф који има бесконачну количину чворова и ивица.
Тривијалан графикон: Граф који има само један чвор и без ивице.
Једноставан графикон: Када само једна ивица повезује сваки пар чворова графа, назива се једноставним графом.
Нулл график: Нулти граф је граф који нема ивице које повезују његове чворове.
мултиграф: У мултиграфу, најмање пар чворова има више од једне ивице која их повезује. У мултиграфима не постоје само петље.
Комплетан графикон: Потпуни граф је граф у коме се сваки чвор повезује са сваким другим чвором у графу. Такође је познат као а пун графикон .
Псеудо график: Граф који има самопетљу поред других ивица графа назива се псеудо граф.
Редовни графикон: Регуларни граф је граф где сви чворови имају једнаке степене; тј. сваки чвор има исти број суседа.
Повезани графикон: Повезани граф је једноставно било који граф у коме се повезују било која два чвора; односно граф са најмање једном путањом између свака два чвора графа.
Неповезани графикон: Неповезани граф је директна супротност повезаном графу. У неповезаном графу, нема ивица које повезују чворове графа, као што је а нула граф.
Циклични графикон: Циклични граф је граф који садржи најмање један циклус графа (пут који се завршава тамо где је почео).
Ациклични графикон: Ациклични граф је граф без циклуса. Може бити усмјерено или неусмјерено.
Подграф: Подграф је изведени граф. То је граф формиран од чворова и ивица које су подскупови другог графа.