En angränsande lista är en datastruktur som används för att representera en graf där varje nod i grafen lagrar en lista över dess närliggande hörn.
Grafrepresentation av Riktad graf till angränsande lista
Egenskaper för Adjacency List:
- Storleken på matrisen bestäms av antalet noder i nätverket.
- Antalet grafkanter är lätt att beräkna.
- Närhetslistan är en taggig array .
Hur bygger man en Adjacency List?
Det är väldigt enkelt och enkelt att konstruera en angränsande lista för en graf, det finns vissa steg nedan som du måste följa:
- Skapa en rad länkade listor av storlek N , där N är antalet hörn i grafen.
- Skapa en länkad lista med angränsande hörn för varje hörn i grafen.
- För varje kant (u, v) i grafen, lägg till i till den länkade listan över i , och lägg till i till den länkade listan över i om grafen är oriktad lägg till i till listan över i om det är riktat från i till i . (Vid viktade grafer lagra vikten tillsammans med anslutningarna).
Tillämpningar av Adjacency List:
- Dijkstras algoritm , Utöka första sökningen , och Djup första sökning använd närliggande listor för att representera grafer.
- Bildbehandling : Närliggande listor kan användas för att representera närliggande relationer mellan pixlar i en bild.
- Spelutveckling : Dessa listor kan användas för att lagra information om kopplingarna mellan olika områden eller nivåer som spelutvecklarna använder grafer för att representera spelkartor eller nivåer.
Fördelar med att använda en Adjacency-lista:
- En angränsande lista är enkel och lätt att förstå.
- Det går snabbt och enkelt att lägga till eller ta bort kanter från en graf.
Nackdelar med att använda en Adjacency-lista:
- I grannlistor kan åtkomst till kanterna ta längre tid än närliggande matris.
- Det kräver mer minne än närliggande matris för täta grafer.
Vad mer kan du läsa?
- Adjacency Matrix betydelse och definition i DSA
- Lägg till och ta bort kant i Adjacency List representation av en graf
- Konvertera Adjacency Matrix till Adjacency List representation av Graph
- Konvertera Adjacency List till Adjacency Matrix representation av en graf
- Jämförelse mellan Adjacency List och Adjacency Matrix representation av graf