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

Преглед садржаја

Графичка терминологија
Приказ графикона
Графичке операције

У овом упутству ћете научити шта је структура података графикона. Такође ћете наћи приказе графа.

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

Покушајмо ово да разумемо на примеру. На фацебооку је све чвор. То укључује корисника, фотографију, албум, догађај, групу, страницу, коментар, причу, видео, везу, белешку … све што има податке је чвор.

Свака веза је ивица од једног чвора до другог. Било да објавите фотографију, придружите се групи, попут странице итд., За ту везу се ствара нова ивица.

Пример структуре података графикона

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

Тачније, граф је структура података (В, Е) која се састоји од

Збирка темена В.
Колекција ивица Е, представљена као уређени парови врхова (у, в)

Врхови и ивице

На графикону,

 В = (0, 1, 2, 3) Е = ((0,1), (0,2), (0,3), (1,2)) Г = (В, Е)

Графичка терминологија

Суседност : За врх се каже да је суседан другом темену ако постоји ивица која их повезује. Врхови 2 и 3 нису суседни јер између њих нема ивице.
Путања : Низ ивица који вам омогућава да пређете из врха А у врх Б назива се путања. 0-1, 1-2 и 0-2 су путање од темена 0 до темена 2.
Усмерени граф : График у коме ивица (у, в) не мора да значи да постоји и ивица (в, у). Ивице на таквом графикону представљене су стрелицама да покажу правац ивице.

Приказ графикона

Графови су обично представљени на два начина:

1. Матрица суседства

Матрица суседности је 2Д низ В к В темена. Сваки ред и колона представљају врх.

Ако је вредност било ког елемента a(i)(j)1, то представља да постоји ивица која повезује темена и и врх ј.

Матрица суседности за графикон који смо горе креирали је

Матрица суседности графа

Будући да је то усмерени граф, за ивицу (0,2) такође морамо да означимо ивицу (2,0); чинећи матрицу суседства симетричном око дијагонале.

Тражење ивица (провера да ли постоји ивица између темена А и темена Б) је изузетно брзо у представљању матрице суседства, али морамо резервисати простор за сваку могућу везу између свих врхова (В к В), па захтева више простора.

2. Листа суседства

Листа суседности представља графикон као низ повезаних листа.

Индекс низа представља врх, а сваки елемент на повезаној листи представља остале врхове који са врхом чине ивицу.

Листа суседности за графикон који смо направили у првом примеру је следећа:

Заступљеност листе суседства

Листа суседности је ефикасна у погледу складиштења, јер треба да сачувамо само вредности за ивице. За граф са милионима темена то може значити много уштеде простора.