Hvad er Graph Data Structure?

EN Kurve er en ikke-lineær datastruktur bestående af toppunkter og kanter. Hjørnerne omtales nogle gange også som noder, og kanterne er linjer eller buer, der forbinder to vilkårlige noder i grafen. Mere formelt er en graf sammensat af et sæt toppunkter( I ) og et sæt kanter( OG ). Grafen er angivet med G(V, E) .

Repræsentationer af graf

Her er de to mest almindelige måder at repræsentere en graf på:

1. Adjacency Matrix
2. Tilgrænsende liste

Adjacency Matrix

En tilstødende matrix er en måde at repræsentere en graf som en matrix af boolean (0'er og 1'er).

Lad os antage, at der er n hjørner i grafen Så opret en 2D-matrix adjMat[n][n] med dimension n x n.

• Hvis der er en kant fra toppunktet jeg til j , mærke adjMat[i][j] som 1 .
• Hvis der ikke er nogen kant fra toppunktet jeg til j , mærke adjMat[i][j] som 0 .

Repræsentation af urettet graf til tilstødende matrix:

Nedenstående figur viser en urettet graf. I første omgang er hele Matrix initialiseret til 0 . Hvis der er en kant fra kilde til destination, indsætter vi 1 til begge tilfælde ( adjMat[destination] og adjMat [ bestemmelsessted]) fordi vi kan gå begge veje.

Udirigeret graf til tilstødende matrix

Repræsentation af Directed Graph til Adjacency Matrix:

Nedenstående figur viser en rettet graf. I første omgang er hele Matrix initialiseret til 0 . Hvis der er en kant fra kilde til destination, indsætter vi 1 for netop det adjMat[destination] .

Instrueret graf til Adjacency Matrix

Tilgrænsende liste

Et array af lister bruges til at gemme kanter mellem to hjørner. Størrelsen af ​​array er lig med antallet af hjørner (dvs. n) . Hvert indeks i dette array repræsenterer et specifikt toppunkt i grafen. Indgangen ved indekset i af arrayet indeholder en sammenkædet liste, der indeholder de hjørner, der støder op til vertex jeg .

Lad os antage, at der er n hjørner i grafen Så opret en række af listen af størrelse n som adjList[n].

• adjList[0] vil have alle de noder, som er forbundet (nabo) til vertex 0 .
• adjList[1] vil have alle de noder, der er forbundet (nabo) til vertex 1 og så videre.

Repræsentation af udirigeret graf til tilstødende liste:

Nedenstående urettede graf har 3 spidser. Så der oprettes en række liste i størrelse 3, hvor hvert indeks repræsenterer hjørnerne. Nu har toppunkt 0 to naboer (dvs. 1 og 2). Så indsæt toppunkt 1 og 2 ved indeks 0 af array. Tilsvarende, For toppunkt 1 har den to naboer (dvs. 2 og 0) Så indsæt toppunkter 2 og 0 ved indeks 1 i matrix. Tilsvarende, for vertex 2, indsæt dens naboer i rækken af ​​listen.

Liste over ikke-dirigeret graf til adjacency

Repræsentation af rettet graf til tilstødende liste:

Nedenstående rettede graf har 3 spidser. Så der oprettes en række liste i størrelse 3, hvor hvert indeks repræsenterer hjørnerne. Nu har toppunkt 0 ingen naboer. For toppunkt 1 har den to naboer (dvs. 0 og 2) Så indsæt toppunkter 0 og 2 ved indeks 1 i array. Tilsvarende, for vertex 2, indsæt dens naboer i rækken af ​​listen.

Rettet graf til tilgrænsende liste