Adjacency Set:Repræsenterer grafforhold
Et adjacency sæt er en måde at repræsentere en grafs struktur på. For hvert toppunkt (node) i grafen indeholder adjacency -sættet alle de vertikater, som det er direkte tilsluttet (dens naboer). Med andre ord er det et sæt, der indeholder alle vertikater, der støder op til et givet toppunkt.
formel definition:
For en graf g =(v, e), hvor v er sæt af vertikater, og e er sæt kanter, er det adjacency -sæt af et toppunkt * v * ∈ V, betegnet som adj (v), defineret som:
Adj (v) ={u ∈ V | (v, u) ∈ E}
Eksempel:
Overvej en simpel ikke -rettet graf med vertices A, B, C og D og kanter:
* (A, b)
* (A, c)
* (B, c)
* (C, d)
Adjacency -indstillingen for hvert toppunkt ville være:
* Adj (a) ={b, c}
* Adj (b) ={a, c}
* Adj (c) ={a, b, d}
* Adj (d) ={c}
Adjacency Set vs. Adjacency List:
Mens det er lignende i konceptet, er det vigtigt at differentiere et adjacency -sæt fra en adjacency -liste.
* Adjacency Set: Bruger et sæt Datastruktur for hvert toppunkt, der ikke indebærer nogen orden blandt naboer og sikrer, at hver nabo kun vises én gang. Dette er ideelt, når orden ikke er vigtig, og du ønsker effektiv medlemskabstest (f.eks. Kontrol af, om Vertex 'X' er en nabo til 'Y'). Du kan ikke opbevare flere kanter mellem de samme to hjørner (multigraf).
* Adjacency -liste: Bruger en liste Datastruktur for hvert toppunkt, der gør det muligt at bestille naboer og potentielt vises flere gange (repræsenterer flere kanter mellem de samme vertikater). Det er mere fleksibelt, men er måske ikke så effektivt til medlemskabstest, hvis du har brug for at undgå duplikater.
Fordele ved at bruge adjacency -sæt:
* Effektiv medlemskabstest: Kontrol af, om et toppunkt * u * er en nabo til toppunkt * V * (dvs. hvis * u * ∈ Adj (v)) er typisk o (1) i gennemsnit ved hjælp af en hash -sæt -implementering.
* Enkel repræsentation: Let at forstå og implementere.
* Ingen duplikatkanter: Per definition kan et sæt ikke indeholde duplikatelementer.
Ulemper ved at bruge adjacency -sæt:
* Bestil ikke bevaret: Den rækkefølge, som naboer opbevares, garanteres ikke.
* Rumkompleksitet: Kan bruge mere plads end alternative repræsentationer som adjacency -matrixer, især til sparsomme grafer. I værste tilfælde (komplet graf) er rumkompleksiteten O (| V | * | V |).
* ikke egnet til multigrafer: Kan ikke repræsentere flere kanter mellem de samme to hjørner.
relation til netværksforbindelse
Adjacency -sæt spiller en betydelig rolle i bestemmelsen af netværksforbindelse, fordi de eksplicit definerer de direkte forbindelser mellem vertices. Baseret på disse forbindelser kan vi udlede forskellige forbindelsesegenskaber:
1. Bestemmelse af tilsluttede komponenter: Ved at krydse grafen ved hjælp af adjacency -sæt, kan vi identificere tilsluttede komponenter. En tilsluttet komponent er en undergraf, hvor hvert toppunkt kan nås fra alle andre toppunkt inden for denne undergraf. Algoritmer som dybde-første søgning (DFS) eller bredde-første søgning (BFS) kan implementeres effektivt ved hjælp af adjacency-sæt til at udforske grafen og identificere disse komponenter. Hvis en graf kun har en tilsluttet komponent, betyder det, at grafen er tilsluttet.
2. Beregning af korteste stier: Algoritmer som Dijkstra's algoritme eller BFS kan bruges med adjacency -sæt til at finde de korteste stier mellem to hjørner. Disse algoritmer er afhængige af at udforske naboerne i et toppunkt (leveret af adjacency -sættet) for at opdage stierne.
3. detektering af cyklusser: DFS kan anvendes med adjacency -sæt til at detektere cyklusser i en graf. Ved at spore de toppunkt, der i øjeblikket er i rekursionsstakken, kan vi identificere rygkanter, som angiver tilstedeværelsen af cykler.
4. Kontrol af bipartititet: Vi kan bruge adjacency -sæt i forbindelse med graffarvelægningsalgoritmer (f.eks. Brug af DFS eller BFS) til at bestemme, om en graf er bipartit. En bipartitgraf er en, hvor hjørnetierne kan opdeles i to disjoint -sæt, således at hver kant forbinder et toppunkt i det ene sæt til et toppunkt i det andet sæt.
5. vurdering af robusthed/modstandsdygtighed: Adjacency -sæt giver os mulighed for at analysere, hvordan fjernelse af visse vertikater eller kanter påvirker netværkets tilslutning. Vi kan simulere disse fjernelser og derefter beregne sammenkoblede tilsluttede komponenter for at se, om netværket bliver fragmenteret.
Kortfattet:
Adjacency -sæt giver en grundlæggende måde at repræsentere grafforhold på. Deres effektivitet i naboopslag gør dem til et værdifuldt værktøj til forskellige grafalgoritmer, der er afgørende for forståelse og analyse af netværksforbindelse. De giver os mulighed for at bestemme, om vertices kan nås fra hinanden, finde stier mellem vertices, identificere tilsluttede komponenter og vurdere et netværks samlede tilslutning og modstandsdygtighed. Mens de har begrænsninger med hensyn til multigrafer og potentiel pladsforbrug, forbliver de en kraftig og vidt anvendt repræsentation for mange grafrelaterede problemer.
