Adjacency List og Matrix Repræsentation af Graph

Selvom de ser anderledes ud, alle sammen typer af grafer kan repræsenteres på en lignende måde. Der er generelt to typer grafrepræsentation:

1. Adjacency Matrix
2. Tilstødelsesliste

Tilstødelsesliste

En adjacensliste består af sammenkædede lister. Hvert hjørne betragtes som et arrayindeks, og hvert element repræsenterer en sammenkædet liste. Disse sammenkædede lister indeholder de hjørner, der deler en kant med indekshjørnet.

Her er et eksempel på en liste over tilstødende områder:

Lad en graf indeholde V antal hjørner og E antal kanter. Rumkompleksiteten af ​​adjacenslisten er O(V + E), som skalerer med antallet af reelle kanter i stedet for alle mulige par af hjørner.

Worst-case rumkompleksitet bliver O(V²) hvis den givne graf er en komplet graf, da hvert hjørne så er forbundet med ethvert andet hjørne.

Adjacency Matrix

En adjacensmatrix er sammensat af et 2D-array. For en graf med V hjørner vil matrixens størrelse være V × V.

Sige matrix[i][j] = 5Det betyder, at der er en kant mellem knudepunkt i og knudepunkt j, hvor vægten er 5.

Lad os se på følgende graf og dens adjacensmatrix:

Vi byggede 2D-array ved at bruge disse trin:

Trin 1) Hjørnet A har en lige kant med B, og vægten er 5. Så cellen i række A og kolonne B vil være fyldt med 5. Resten af ​​cellerne i række A vil være fyldt med nul.

Trin 2) Hjørnet B har en lige kant med C, og vægten er 4. Så cellen i række B og kolonne C vil være fyldt med 4. De resterende celler i række B vil være fyldt med nul, da B ikke har nogen udgående kant til nogen anden node.

Trin 3) Hjørnet C har ingen direkte kanter med andre hjørner. Så række C vil være fyldt med nuller.

Trin 4) Hjørnet D har en rettet kant med A og C.

• Cellen i række D og kolonne A vil have en værdi på 7. Cellen i række D og kolonne C vil have en værdi på 2.
• Resten af ​​cellerne i række D vil være fyldt med nuller.

Trin 5) Hjørnet E har en rettet kant med B og D. Cellen i række E og kolonne B vil have en værdi på 6. Cellen i række E og kolonne D vil have en værdi på 3. Resten af ​​cellerne i række E vil være udfyldt med nuller.

Her er nogle punkter at bemærke:

• Grafen har ingen selv-løkker, når den primære diagonal af adjacensmatricen er 0.
• Grafen er en rettet graf, hvis cellerne ved (a, b) og (b, a) ikke har den samme værdi. Ellers er grafen ikke-rettet.
• Grafen er en vægtet graf, hvis værdien af ​​en celle er større end 1.

Hovedproblemet med adjacensmatricen er, at den kræver kvadratisk plads. Selv kanter, der ikke eksisterer, allokerer stadig celler i hukommelsen.

Hvis vi for eksempel har en graf med 100 noder, skal der bruges 10,000 celler til at gemme den. RAMMed færre kanter i grafen kan allokering af så stor hukommelse være spild af tid. Så rumkompleksiteten ved brug af adjacensmatricen er O(N²), hvor N er antallet af noder i grafen.

Tilstødningsliste vs. tilstødningsmatrix

Før man vælger en repræsentation, er det en god idé at sammenligne begge modeller side om side på tværs af de operationer, der dominerer i virkelige grafbelastninger:

Produktion	Adjacency Matrix	Tilstødelsesliste
Rumkompleksitet	O(V²)	O(V + E)
Tilføj et hjørne	O(V²)	O (1)
Tilføj en kant	O (1)	O (1)
Fjern en kant	O (1)	O(E)
Tjek om kanten (i, j) eksisterer	O (1)	O (grad af i)
Iterer over naboer til i	O (V)	O (grad af i)
Bedste for	Tætte grafer, hyppige kantforespørgsler	Sparsomme grafer, traversal-tunge opgaver

Kort sagt vinder adjacency-matricen ved kantopslag i konstant tid, mens adjacency-listen vinder ved hukommelses- og nabo-iteration, hvilket er grunden til, at algoritmer som BFS, DFS og Dijkstra normalt parres med adjacency-lister.

Fordele og ulemper ved grafrepræsentation

Hver repræsentation har sine egne afvejninger. Kendskab til styrkerne og svaghederne ved begge modeller hjælper dig med at vælge den rigtige til det problem, du løser.

Fordele ved tilstødningsmatrix:

• Konstanttids O(1) kanteksistensforespørgsler mellem et hvilket som helst par af hjørner.
• Fast indeksering gør matrixbaserede algoritmer som Floyd-Warshall og transitiv lukning nemme at implementere.
• Vægtede kanter passer naturligt i en enkelt matrixcelle.

Ulemper ved adjacency matrix:

• Spilder O(V²) hukommelse, når grafen er sparsom.
• Tilføjelse af et nyt hjørne kræver ændring af størrelsen på hele matricen.
• Iterering over naboer til et enkelt hjørne tager O(V), selv når hjørnet kun har få kanter.

Fordele ved tilstødningsliste:

• Bruger kun O(V + E) hukommelse, som er tæt på det reelle kantantal i sparse grafer.
• Tilføjelse af et nyt hjørne eller en ny kant er O(1).
• Traversalalgoritmer som BFS og DFS itererer naboer i O(grad), hvilket giver den samlede O(V + E) køretid.

Ulemper ved tilstødende liste:

• Det tager O(grader) tid at kontrollere, om en specifik kant eksisterer, i stedet for O(1).
• Cache-lokalitet er svagere, fordi sammenkædede lister er spredt ud over hukommelsen.
• Vægtede kanter kræver et ledsagende felt eller en liste af par, hvilket komplicerer datastrukturen en smule.

Hvornår skal man bruge en adjacency-liste vs. en adjacency-matrix

Valget af repræsentation afhænger af grafens tæthed og de operationer, du udfører oftest. Brug denne hurtigguide til at vælge den rigtige struktur:

• Foretrækker adjacensmatricen når grafen er tæt (E er tæt på V²), når kanterne sjældent ændrer sig, og når din algoritme spørger "er der en kant mellem i og j?" mange gange.
• Foretrækker tilstødningslisten når grafen er sparsom (E er meget mindre end V²), når hjørne- eller kantmængden vokser under udførelse, og når du gennemløber grafen med BFS, DFS eller Dijkstras korteste-vejsalgoritme.
• Foretrækker en blandet model (tilstødningsliste plus et hashsæt af kanter) når du har brug for både hurtig nabo-iteration og O(1) kantforespørgsler, på bekostning af ekstra hukommelse.

Moderne grafbiblioteker som NetworkX og igraph bruger som standard tilstødende lister, fordi de fleste grafer i den virkelige verden - sociale netværk, vejkort, websider, pakkeafhængigheder - er sparsomme og kræver mange gennemgange.

Ofte Stillede Spørgsmål