Hva er Graph Data Structure?
EN Kurve er en ikke-lineær datastruktur som består av toppunkter og kanter. Toppunktene blir noen ganger også referert til som noder, og kantene er linjer eller buer som forbinder hvilke som helst to noder i grafen. Mer formelt er en graf sammensatt av et sett med toppunkter( I ) og et sett med kanter( OG ). Grafen er merket med G(V, E) .
Representasjoner av graf
Her er de to vanligste måtene å representere en graf på:
- Adjacency Matrix
- Tilknytningsliste
Adjacency Matrix
En tilstøtende matrise er en måte å representere en graf på som en matrise av boolske (0-er og 1-er).
La oss anta at det finnes n toppunkter i grafen Så lag en 2D-matrise adjMat[n][n] har dimensjon n x n.
- Hvis det er en kant fra toppunktet Jeg til j , merke adjMat[i][j] som 1 .
- Hvis det ikke er noen kant fra toppunktet Jeg til j , merke adjMat[i][j] som 0 .
Representasjon av urettet graf til tilstøtende matrise:
Figuren nedenfor viser en urettet graf. Til å begynne med er hele matrisen initialisert til 0 . Hvis det er en kant fra kilde til destinasjon, setter vi inn 1 til begge tilfeller ( adjMat[destinasjon] og adjMat [ mål]) fordi vi kan gå begge veier.
Urettet graf til Adjacency Matrix
Representasjon av rettet graf til tilstøtende matrise:
Figuren nedenfor viser en rettet graf. Til å begynne med er hele matrisen initialisert til 0 . Hvis det er en kant fra kilde til destinasjon, setter vi inn 1 for akkurat det adjMat[destinasjon] .
Rettet graf til Adjacency Matrix
Tilknytningsliste
En rekke lister brukes til å lagre kanter mellom to toppunkter. Størrelsen på matrisen er lik antall hjørner (dvs. n) . Hver indeks i denne matrisen representerer et spesifikt toppunkt i grafen. Oppføringen ved indeksen i av matrisen inneholder en koblet liste som inneholder toppunktene som er ved siden av toppunktet Jeg .
La oss anta at det finnes n toppunkter i grafen Så lag en rekke av listen av størrelse n som adjList[n].
- adjList[0] vil ha alle nodene som er koblet (nabo) til toppunktet 0 .
- adjList[1] vil ha alle nodene som er koblet (nabo) til toppunktet 1 og så videre.
Representasjon av udirigert graf til tilgrensende liste:
Den urettede grafen nedenfor har 3 toppunkter. Så det vil bli laget en liste med størrelse 3, der hver indeks representerer hjørnene. Nå har toppunktet 0 to naboer (dvs. 1 og 2). Så sett inn toppunkt 1 og 2 ved indeksene 0 i matrisen. På samme måte, for toppunkt 1, har den to naboer (dvs. 2 og 0). Så sett inn toppunktene 2 og 0 ved indeksene 1 i matrisen. På samme måte, for toppunkt 2, sett inn naboene i listen.
Udirigert graf til tilgrensende liste
Representasjon av rettet graf til tilstøtende liste:
Grafen nedenfor har 3 hjørner. Så det vil bli laget en liste med størrelse 3, der hver indeks representerer hjørnene. Nå har toppunkt 0 ingen naboer. For toppunkt 1 har den to naboer (dvs. 0 og 2). Så sett inn toppunktene 0 og 2 ved indeksene 1 i matrisen. På samme måte, for toppunkt 2, sett inn naboene i listen.
Rettet Graph til Adjacency-liste