Čo je štruktúra údajov grafu?

A Graf je nelineárna dátová štruktúra pozostávajúca z vrcholov a hrán. Vrcholy sa niekedy označujú aj ako uzly a hrany sú čiary alebo oblúky, ktoré spájajú ľubovoľné dva uzly v grafe. Formálnejšie sa graf skladá z množiny vrcholov ( V ) a množinu hrán ( A ). Graf je označený G(V, E) .

Reprezentácie grafu

Tu sú dva najbežnejšie spôsoby znázornenia grafu:

1. Matica susedstva
2. Zoznam susedstva

Matica susedstva

Matica susedstva je spôsob znázornenia grafu ako logickej matice (0 a 1).

Predpokladajme, že existujú n vrcholy v grafe Vytvorte teda 2D maticu adjMat[n][n] s rozmermi n x n.

np.priemer

• Ak existuje hrana z vrcholu i do j , značka adjMat[i][j] ako 1 .
• Ak z vrcholu nie je žiadna hrana i do j , značka adjMat[i][j] ako 0 .

Znázornenie neorientovaného grafu k matici susedstva:

Nižšie uvedený obrázok ukazuje neorientovaný graf. Spočiatku je celý Matrix inicializovaný 0 . Ak existuje hrana od zdroja k cieľu, vložíme 1 v oboch prípadoch ( adjMat[destinácia] a adjMat [ destinácia]) pretože môžeme ísť oboma smermi.

tabuľka v reakcii

Neorientovaný graf na maticu susedstva

Znázornenie smerovaného grafu k susednej matici:

Nižšie uvedený obrázok znázorňuje orientovaný graf. Spočiatku je celý Matrix inicializovaný 0 . Ak existuje hrana od zdroja k cieľu, vložíme 1 za to konkrétne adjMat[destinácia] .

Directed Graph to Adjacency Matrix

Zoznam susedstva

Pole zoznamov sa používa na ukladanie hrán medzi dvoma vrcholmi. Veľkosť poľa sa rovná počtu vrcholy (t. j. n) . Každý index v tomto poli predstavuje konkrétny vrchol v grafe. Záznam na indexe i poľa obsahuje prepojený zoznam obsahujúci vrcholy, ktoré susedia s vrcholom i .

Predpokladajme, že existujú n vrcholy v grafe Takže vytvorte an pole zoznamu veľkosti n ako adjList[n].

• adjList[0] bude mať všetky uzly, ktoré sú pripojené (susedné) s vrcholom 0 .
• adjList[1] bude mať všetky uzly, ktoré sú pripojené (susedné) s vrcholom 1 a tak ďalej.

Znázornenie neusmerneného grafu so zoznamom susedstva:

Nižšie uvedený neorientovaný graf má 3 vrcholy. Takže sa vytvorí pole zoznamu veľkosti 3, kde každý index predstavuje vrcholy. Teraz má vrchol 0 dvoch susedov (t.j. 1 a 2). Takže vložte vrchol 1 a 2 na indexy 0 poľa. Podobne pre vrchol 1 má dvoch susedov (t. j. 2 a 0). Takže vložte vrcholy 2 a 0 na indexy 1 poľa. Podobne pre vrchol 2 vložte jeho susedov do poľa zoznamu.

Neorientovaný graf na zoznam susedstva

rekurzia java

Znázornenie riadeného grafu k zoznamu susedných miest:

Nižšie orientovaný graf má 3 vrcholy. Takže sa vytvorí pole zoznamu veľkosti 3, kde každý index predstavuje vrcholy. Teraz vrchol 0 nemá žiadnych susedov. Pre vrchol 1 má dvoch susedov (t.j. 0 a 2) Takže vložte vrcholy 0 a 2 na indexy 1 poľa. Podobne pre vrchol 2 vložte jeho susedov do poľa zoznamu.

Nasmerovaný graf na zoznam susedstva