Angränsningslista - Adjacency list
Inom grafteori och datavetenskap är en angränsningslista en samling oordnade listor som används för att representera ett ändligt diagram . Varje oordnad lista i en angränsningslista beskriver uppsättningen grannar till en viss toppunkt i grafen. Detta är en av flera vanliga representationer av grafer för användning i datorprogram.
Implementeringsdetaljer
| Grafen på bilden ovan har den här representationen för närstående lista: | ||
| a | intill | före Kristus |
| b | intill | a, c |
| c | intill | a, b |
En representation för en närliggande lista för en graf associerar varje toppunkt i grafen med samlingen av dess närliggande hörn eller kanter. Det finns många varianter av denna grundidé, som skiljer sig åt i detaljerna om hur de implementerar sambandet mellan hörn och samlingar, hur de implementerar samlingarna, om de inkluderar både hörn och kanter eller bara hörn som förstklassiga objekt och i vad typer av objekt används för att representera hörn och kanter.
- En implementering som föreslogs av Guido van Rossum använder en hashtabell för att associera varje toppunkt i en graf med en uppsättning intilliggande hörn. I denna representation kan en toppunkt representeras av vilket hashbart objekt som helst. Det finns ingen tydlig representation av kanter som objekt.
- Cormen et al. föreslå en implementering där hörnen representeras av indexnummer. Deras representation använder en array som indexeras med vertexnummer, där arraycellen för varje vertex pekar på en enstaka länkad lista över de närliggande hörnen i den vertexen. I denna representation kan noderna i den enskilt länkade listan tolkas som kantobjekt; de lagrar dock inte fullständig information om varje kant (de lagrar bara en av de två slutpunkterna i kanten) och i oriktade grafer kommer det att finnas två olika länkade listnoder för varje kant (en i listorna för var och en av de två ändpunkter på kanten).
- Den objektorienterade incidenslistestrukturen som föreslås av Goodrich och Tamassia har speciella klasser av toppunktsobjekt och kantobjekt. Varje vertex -objekt har en instansvariabel som pekar på ett samlingsobjekt som listar de närliggande kantobjekten. Varje kantobjekt pekar i sin tur på de två toppunktsobjekten vid dess slutpunkter. Den här versionen av angränsningslistan använder mer minne än den version där angränsande hörn listas direkt, men förekomsten av uttryckliga kantobjekt gör det extra flexibelt att lagra ytterligare information om kanter.
Operationer
Huvudoperationen som utförs av datastrukturen för angränsningslistan är att rapportera en lista över grannarna till en viss hörnpunkt. Med hjälp av någon av de ovan beskrivna implementeringarna kan detta utföras i konstant tid per granne. Med andra ord är den totala tiden för att rapportera alla grannar till en toppunkt v proportionell mot graden av v
Det är också möjligt, men inte lika effektivt, att använda adjacenslistor för att testa om det finns en kant eller inte mellan två angivna hörn. I en angränsningslista där grannarna till varje hörn är osorterade kan testning av förekomsten av en kant utföras i tid som är proportionell mot minimigraden av de två givna hörnen, med hjälp av en sekventiell sökning genom grannarna till denna hörn. Om grannarna representeras som en sorterad array kan binär sökning användas istället, vilket tar tid som är proportionell mot logaritmen för graden.
Avvägningar
Huvudalternativet till adjacenslistan är adjacensmatrisen , en matris vars rader och kolumner indexeras av hörn och vars celler innehåller ett booleskt värde som anger om det finns en kant mellan hörnen som motsvarar cellens rad och kolumn. För en gles graf (en där de flesta hörnpar inte är anslutna med kanter) är en angränsningslista betydligt mer utrymmeseffektiv än en angränsningsmatris (lagrad som en tvådimensionell matris): utrymmesanvändningen för angränsningslistan är proportionell till antalet kanter och hörn i grafen, medan för en närliggande matris lagrad på detta sätt är utrymmet proportionellt mot kvadraten för antalet hörn. Det är emellertid möjligt att lagra angränsningsmatriser mer rymdeffektivt, vilket matchar den linjära rymdanvändningen för en angränsningslista, genom att använda en hashtabell som indexeras av par av hörn snarare än en array.
Den andra signifikanta skillnaden mellan adjacenslistor och adjacensmatriser är effektiviteten i de operationer de utför. I en angränsningslista kan grannarna till varje hörn listas effektivt, i tid proportionellt mot hörnets grad. I en adjacensmatris tar denna operation tid som är proportionell mot antalet hörn i grafen, vilket kan vara betydligt högre än graden. Å andra sidan tillåter adjacensmatrisen att testa om två hörn ligger intill varandra i konstant tid; adjacency listan är långsammare för att stödja denna operation.
Data struktur
För användning som en datastruktur är det främsta alternativet till angränsningslistan adjacensmatrisen. Eftersom varje post i adjacensmatrisen bara kräver en bit, kan den representeras på ett mycket kompakt sätt, som bara upptar | V | 2 /8 byte sammanhängande utrymme, där | V | är antalet hörn i grafen. Förutom att undvika slöseri med utrymme, uppmuntrar denna kompakthet till referensplats .
För en gles graf kräver dock anslutningslistor mindre utrymme, eftersom de inte slösar bort något utrymme för att representera kanter som inte finns. Med hjälp av en naiv matrisimplementering på en 32-bitars dator kräver en närliggande lista för en ostyrd graf cirka 2⋅ (32/8) | E | = 8 | E | byte av rymden, där | E | är antalet kanter på grafen.
Observera att en oriktad enkel graf högst kan ha (| V | 2 - | V |)/2 ≈ V 2 kanter, så att slingor kan göras, kan vi låta d = | E |/| V | 2 betecknar grafens densitet. Sedan, 8 | E | > | V | 2 /8 när | E |/| V | 2 > 1/64 , det vill säga närhetslistans representation upptar mer utrymme än adjacensmatrisrepresentationen när d > 1/64 . Således måste ett diagram vara tillräckligt sparsamt för att motivera en representation för närliggande listor.
Förutom rymdavvägningen underlättar de olika datastrukturerna också olika operationer. Att hitta alla hörn intill en viss hörnpunkt i en angränsningslista är lika enkelt som att läsa listan. Med en adjacensmatris måste en hel rad istället skannas, vilket tar O (| V |) tid. Huruvida det finns en kant mellan två givna hörn kan fastställas på en gång med en angränsningsmatris, samtidigt som det kräver tid som är proportionell mot minimigraden för de två hörnen med angränsningslistan.