adjacensuppsättning:Representera grafrelationer
En adjacency set är ett sätt att representera en grafs struktur. För varje toppunkt (nod) i diagrammet innehåller adjacensuppsättningen alla vertikaler som den är direkt ansluten till (dess grannar). Med andra ord, det är en uppsättning som innehåller alla vertikaler intill ett givet toppunkt.
Formell definition:
För en graf g =(v, e), där v är uppsättningen av vertikaler och e är uppsättningen av kanter, definieras den adjacensuppsättningen för en toppunkt * v * ∈ V, betecknad som adj (v), som:
Adj (v) ={u ∈ V | (v, u) ∈ E}
Exempel:
Tänk på en enkel inriktad graf med toppar A, B, C och D och kanter:
* (A, B)
* (A, C)
* (B, C)
* (C, D)
Adjacency -uppsättningarna för varje toppunkt skulle vara:
* Adj (a) ={b, c}
* Adj (b) ={a, c}
* Adj (c) ={a, b, d}
* Adj (d) ={c}
Anställningsuppsättning kontra adjacenslista:
Även om det liknar konceptet är det avgörande att skilja en adjacensuppsättning från en adjacenslista.
* Anpassningsset: Använder en set Datastruktur för varje toppunkt, vilket innebär ingen ordning bland grannarna och säkerställer att varje granne visas en gång. Detta är idealiskt när ordningen inte är viktig och du vill ha effektiv medlemstest (t.ex. att kontrollera om toppunktet 'x' är en granne till 'y'). Du kan inte lagra flera kanter mellan samma två vertikaler (multigraf).
* Anställningslista: Använder en -lista Datastruktur för varje toppunkt, vilket gör att grannar kan beställas och potentiellt visas flera gånger (representerar flera kanter mellan samma toppar). Det är mer flexibelt men kanske inte är lika effektivt för medlemstest om du behöver undvika duplikat.
Fördelar med att använda adjacensuppsättningar:
* Effektiv testning av medlemskap: Kontroll om en toppunkt * u * är en granne till toppunkt * V * (dvs om * u * ∈ ADJ (V)) är vanligtvis o (1) i genomsnitt med hjälp av en hashuppsättning implementering.
* enkel representation: Lätt att förstå och implementera.
* Inga duplicerade kanter: Per definition kan en uppsättning inte innehålla duplicerade element.
Nackdelar med att använda justitensuppsättningar:
* beställ inte bevarad: Den ordning som grannar lagras är inte garanterad.
* Rymdkomplexitet: Kan använda mer utrymme än alternativa representationer som adjacensmatriser, särskilt för glesa grafer. I värsta fall (komplett graf) är rymdkomplexiteten O (| V | * | V |).
* inte lämpligt för multigrafer: Kan inte representera flera kanter mellan samma två vertikaler.
relation till nätverksanslutning
Anställningsuppsättningar spelar en viktig roll för att bestämma nätverksanslutning eftersom de uttryckligen definierar de direkta anslutningarna mellan vertikaler. Baserat på dessa anslutningar kan vi dra slutsatsen om olika anslutningsegenskaper:
1. Bestämma anslutna komponenter: Genom att korsa diagrammet med hjälp av justeringsuppsättningarna kan vi identifiera anslutna komponenter. En ansluten komponent är en subgraf där varje toppunkt kan nås från alla andra toppunktioner inom den subgrafen. Algoritmer som DEPTH-First Search (DFS) eller bredd-första sökning (BFS) kan implementeras effektivt med hjälp av adjacensuppsättningar för att utforska grafen och identifiera dessa komponenter. Om en graf bara har en ansluten komponent betyder det att grafen är ansluten.
2. Beräkna kortaste vägar: Algoritmer som Dijkstras algoritm eller BFS kan användas med adjacensuppsättningar för att hitta de kortaste vägarna mellan två vertikaler. Dessa algoritmer förlitar sig på att utforska grannarna till ett toppunkt (tillhandahållet av justitensuppsättningen) för att upptäcka vägarna.
3. Detekterande cykler: DF:er kan användas med adjacensuppsättningar för att detektera cykler i en graf. Genom att spåra topparna för närvarande i rekursionsstacken kan vi identifiera bakkanter, som indikerar närvaron av cykler.
4. Kontrollera för tvåparten: Vi kan använda justitensuppsättningar i samband med graffärgalgoritmer (t.ex. med DFS eller BF) för att bestämma om en graf är tvåpartit. En tvåpartsgraf är en där vertikalerna kan delas upp i två osammanhängande uppsättningar så att varje kant ansluter ett toppunkt i en uppsättning till ett toppunkt i den andra uppsättningen.
5. Bedömning av robusthet/motståndskraft: Anitningsuppsättningarna tillåter oss att analysera hur borttagning av vissa vertikaler eller kanter påverkar nätverkets anslutning. Vi kan simulera dessa borttagningar och sedan beräkna anslutna komponenter för att se om nätverket blir fragmenterat.
Sammanfattningsvis:
Adjacensuppsättningar ger ett grundläggande sätt att representera grafrelationer. Deras effektivitet i grannuppslag gör dem till ett värdefullt verktyg för olika grafalgoritmer som är avgörande för att förstå och analysera nätverksanslutning. De tillåter oss att avgöra om hörn kan nås från varandra, hitta vägar mellan toppar, identifiera anslutna komponenter och bedöma en nätverks totala anslutning och motståndskraft. Medan de har begränsningar för multigrafer och potentiell rymdanvändning, förblir de en kraftfull och allmänt använt representation för många grafrelaterade problem.
