Kaj je struktura podatkov grafa?

A Graf je nelinearna podatkovna struktura, sestavljena iz oglišč in robov. Točke se včasih imenujejo tudi vozlišča, robovi pa so črte ali loki, ki povezujejo kateri koli dve vozlišči v grafu. Bolj formalno je graf sestavljen iz množice vozlišč ( IN ) in niz robov ( IN ). Graf je označen z G(V, E) .

Predstavitve grafa

Tukaj sta dva najpogostejša načina za predstavitev grafa:

1. Matrika sosednosti
2. Seznam sosednosti

Matrika sosednosti

Matrika sosednosti je način predstavitve grafa kot matrike logičnih vrednosti (0 in 1).

Predpostavimo, da obstajajo n vozlišča v grafu Torej, ustvarite 2D matriko adjMat[n][n] ki ima dimenzijo n x n.

• Če obstaja rob iz vertex jaz do j , označite adjMat[i][j] kot 1 .
• Če ni roba iz vrha jaz do j , označite adjMat[i][j] kot 0 .

Predstavitev neusmerjenega grafa v matriko sosednosti:

Spodnja slika prikazuje neusmerjen graf. Na začetku je inicializirana celotna matrica 0 . Če obstaja rob od vira do cilja, vstavimo 1 v obeh primerih ( adjMat[destinacija] in adjMat [ cilj]) ker lahko gremo tako ali drugače.

binarno iskalno drevo

Neusmerjeni graf v matriko sosednosti

Predstavitev usmerjenega grafa v matriko sosednosti:

Spodnja slika prikazuje usmerjen graf. Na začetku je inicializirana celotna matrica 0 . Če obstaja rob od vira do cilja, vstavimo 1 za to posebno adjMat[destinacija] .

Usmerjeni graf v matriko sosednosti

Seznam sosednosti

Niz seznamov se uporablja za shranjevanje robov med dvema vozliščema. Velikost niza je enaka številu vozlišča (tj. n) . Vsak indeks v tem nizu predstavlja določeno vozlišče v grafu. Vnos na indeksu i matrike vsebuje povezan seznam, ki vsebuje vozlišča, ki so sosednja točki jaz .

tabela v reakciji

Predpostavimo, da obstajajo n vozlišč v grafu Torej, ustvarite niz seznama velikosti n kot adjList[n].

• adjList[0] bo imel vsa vozlišča, ki so povezana (soseda) z vozliščem 0 .
• adjList[1] bo imel vsa vozlišča, ki so povezana (soseda) z vozliščem 1 in tako naprej.

Predstavitev neusmerjenega grafa na seznamu sosednosti:

Spodnji neusmerjeni graf ima 3 vozlišča. Tako bo ustvarjen niz seznamov velikosti 3, kjer vsak indeks predstavlja vozlišča. Zdaj ima vozlišče 0 dva soseda (tj. 1 in 2). Torej, vstavite točko 1 in 2 na indekse 0 matrike. Podobno, za točko 1 ima dva soseda (tj. 2 in 0). Torej, vstavite točki 2 in 0 v indekse 1 matrike. Podobno za točko 2 vstavite njene sosede v matriko seznama.

Neusmerjeni graf na seznam sosednosti

Predstavitev usmerjenega grafa na seznamu sosednosti:

Spodnji usmerjeni graf ima 3 vozlišča. Tako bo ustvarjen niz seznamov velikosti 3, kjer vsak indeks predstavlja oglišča. Točka 0 zdaj nima sosedov. Za točko 1 ima dva soseda (tj. 0 in 2). Torej, vstavite točki 0 in 2 v indekse 1 matrike. Podobno za točko 2 vstavite njene sosede v matriko seznama.

Usmerjen graf na seznam sosednosti