Vad är Graph Data Structure?

A Graf är en icke-linjär datastruktur som består av hörn och kanter. Topparna kallas ibland också för noder och kanterna är linjer eller bågar som förbinder två valfria noder i grafen. Mer formellt är en graf sammansatt av en uppsättning hörn( I ) och en uppsättning kanter( OCH ). Grafen betecknas med G(V, E) .

Representationer av graf

Här är de två vanligaste sätten att representera en graf:

1. Adjacency matris
2. Adjacency List

Adjacency matris

En närliggande matris är ett sätt att representera en graf som en matris av booleska (0:or och 1:or).

Låt oss anta att det finns n hörn i grafen Så skapa en 2D-matris adjMat[n][n] med dimension n x n.

• Om det finns en kant från vertex i till j , märke adjMat[i][j] som 1 .
• Om det inte finns någon kant från vertex i till j , märke adjMat[i][j] som 0 .

Representation av oriktad graf till närliggande matris:

Bilden nedan visar en oriktad graf. Inledningsvis initieras hela matrisen till 0 . Om det finns en kant från källa till destination, infogar vi 1 i båda fallen ( adjMat[destination] och adjMat [ destination]) för vi kan gå åt båda hållen.

Oriktad graf till Adjacency Matrix

Representation av riktad graf till närliggande matris:

Bilden nedan visar en riktad graf. Inledningsvis initieras hela matrisen till 0 . Om det finns en kant från källa till destination, infogar vi 1 för just det adjMat[destination] .

Riktad graf till Adjacency Matrix

Adjacency List

En array av listor används för att lagra kanter mellan två hörn. Storleken på arrayen är lika med antalet hörn (dvs n) . Varje index i denna array representerar en specifik vertex i grafen. Posten vid index i för arrayen innehåller en länkad lista som innehåller de hörn som gränsar till vertex i .

Låt oss anta att det finns n hörn i grafen Så skapa en rad av listan av storlek n som adjList[n].

• adjList[0] kommer att ha alla noder som är anslutna (granne) till vertex 0 .
• adjList[1] kommer att ha alla noder som är anslutna (granne) till vertex 1 och så vidare.

Representation av oriktad graf till angränsande lista:

Den oriktade grafen nedan har 3 hörn. Så en lista kommer att skapas i storlek 3, där varje index representerar hörnen. Nu har vertex 0 två grannar (dvs 1 och 2). Så, infoga vertex 1 och 2 vid index 0 i matrisen. På liknande sätt, för vertex 1, har den två grannar (dvs 2 och 0). Så infoga hörn 2 och 0 vid index 1 i matrisen. På liknande sätt, för vertex 2, infoga dess grannar i listan.

Oriktad graf till angränsande lista

om annat java

Representation av listan med riktad graf till angränsning:

Den nedan riktade grafen har 3 hörn. Så en lista kommer att skapas i storlek 3, där varje index representerar hörnen. Nu har vertex 0 inga grannar. För vertex 1 har den två grannar (dvs 0 och 2) Så infoga hörn 0 och 2 vid index 1 i matrisen. På liknande sätt, för vertex 2, infoga dess grannar i listan.

Riktad Graph till Adjacency lista