oversigt
i denne vejledning diskuterer vi begrebet tilsluttede komponenter i en ikke-rettet graf.
Vi gennemgår nogle enkle eksempler for at få en grundlæggende forståelse, og så viser vi egenskaberne for tilsluttede komponenter.
definition af tilsluttet komponent
en tilsluttet komponent eller simpelthen komponent i en ikke-rettet graf er en undergraf, hvor hvert par noder er forbundet med hinanden via en sti.
lad os prøve at forenkle det yderligere. Et sæt noder danner en tilsluttet komponent i en ikke-rettet graf, hvis en knude fra sættet af noder kan nå en hvilken som helst anden knude ved at krydse kanter. Hovedpunktet her er tilgængelighed.
i tilsluttede komponenter er alle knudepunkter altid tilgængelige fra hinanden.
få eksempler
i dette afsnit vil vi diskutere et par enkle eksempler. Vi vil forsøge at relatere eksemplerne med definitionen ovenfor.
3.1. En tilsluttet komponent
i dette eksempel har den givne ikke-rettede Graf en tilsluttet komponent:
lad os navngive denne graf 
. Her 
betegner toppunktssættet og 
betegner kantsættet 
. Grafen har en tilsluttet komponent, lad os navngive den 
, som indeholder alle hjørnerne af . Lad os nu kontrollere, om sættet holder fast ved definitionen eller ej.
ifølge definitionen skal hjørnerne i sættet nå hinanden via en sti. Vi vælger to tilfældige hjørner 
og 
:
- kan nås til via:
- kan nås til via:
hjørnerne og opfyldte definitionen, og vi kunne gøre det samme med andre toppunktpar i også.
3.2. Mere end en tilsluttet komponent
i dette eksempel har den ikke-rettede graf tre tilsluttede komponenter:
Let’s name this graph as 
, where 
, and 
. The graph 
has 3 connected components: 
and 
.
lad os nu se, om tilsluttede komponenter
og
opfylder definitionen eller ej. Vi vælger tilfældigt et par fra hver og set.
fra sættet, lad os vælge hjørnerne
og.
-
kan nås til via:
- kan nås til via:
lad os nu vælge hjørnerne 
og 
fra sættet .
- is reachable to
- is reachable to
Finally, let’s pick the vertices 
and 
from the set .
- is reachable to
- kan nås til
så fra disse enkle demonstrationer er det klart, at og følg den tilsluttede komponentdefinition.
egenskaber
da vi allerede har diskuteret definitionen og demonstreret et par eksempler på de tilsluttede komponenter, er det et godt tidspunkt at liste nogle af de vigtige egenskaber, som den tilsluttede komponent altid har.
først og fremmest er det tilsluttede komponentsæt altid ikke tomt.
desuden, hvis der er mere end en tilsluttet komponent til en given graf, vil foreningen af tilsluttede komponenter give sættet med alle hjørner i den givne graf.
for eksempel :
endelig er tilsluttede komponentsæt parvis uensartede. Det betyder, at hvis vi tager krydset mellem to forskellige tilsluttede komponentsæt, vil krydset være lig med et tomt sæt eller et null-sæt.
lad os overveje de tilsluttede komponenter i graf igen. I , lad os tjekke denne ejendom:
find tilsluttede komponenter
i betragtning af en ikke – rettet graf er det vigtigt at finde ud af antallet af tilsluttede komponenter for at analysere grafens struktur-den har mange virkelige applikationer. Vi kan bruge enten DFS eller BFS til denne opgave.
i dette afsnit diskuterer vi en DFS-baseret algoritme, der giver os antallet af tilsluttede komponenter til en given ikke-rettet graf:
.com
variablen Component_Count Returnerer antallet af tilsluttede komponenter i den givne graf.
Vi starter med at initialisere alle hjørner til det flag, der ikke er besøgt. Vi vælger derefter et tilfældigt toppunkt for at starte og kontrollere, om vi har besøgt toppunktet eller ej. Hvis vi ikke gjorde det, kalder vi DFS-funktionen.
når alle de hjørner, der er markeret som besøgt, afslutter algoritmen og udskriver nummeret på de tilsluttede komponenter.
i DFS-funktionen er de argumenter, vi passerer, et toppunktsæt, der indeholder alle hjørnerne i den givne graf og et bestemt toppunkt, der skal tilhøre toppunktssættet.
først markerer vi det bestemte inputpunkt som besøgt. Derefter beregner vi de tilstødende hjørner af det givne bestemte inputpunkt. For hvert tilstødende toppunkt kontrollerer vi, om vi besøgte dem eller ej. Hvis ikke, kalder vi DFS-funktionen rekursivt, indtil vi markerer alle de tilstødende hjørner som besøgt.
nøglepunktet at observere i algoritmen er, at antallet af tilsluttede komponenter er lig med antallet af uafhængige DFS-funktionsopkald. Variablen Component_Count tæller antallet af opkald. Selvfølgelig omfatter dette ikke de opkald, der foretages under DFS () – funktionen rekursivt.
testkørsel
lad os køre algoritmen på en prøvegraf:
givet en ikke-rettet graf 
, hvor 
og 
.
det første trin i algoritmen er at initialisere alle hjørnerne og markere dem som ikke besøgt.
det røde toppunkt angiver, at det ikke er besøgt. Det grønne toppunkt angiver, at det besøges af algoritmen:
Vi kan vælge ethvert toppunkt fra toppunktlisten for at starte algoritmen. Lad os vælge .
algoritmen kontrollerer, om den er besøgt eller ej. I dette tilfælde er ikke besøgt. Så det kalder 
.
inden for DFS () mærker den først toppunktet som besøgt og søger efter de tilstødende hjørner af . Alle de tilstødende hjørner er også markeret som besøgt. Når DFS er færdig med at besøge alle de tilstødende hjørner af , bliver Component_Count 1, og status for hjørner opdateres:
igen vælger algoritmen ethvert tilfældigt toppunkt. Lad os vælge denne gang.
det kontrollerer, om allerede er besøgt eller ej. Da det ikke er besøgt, kalder algoritmen 
. Igen markerer algoritmen toppunktet Marker som besøgt, og DFS søger efter dets tilstødende hjørner og markerer dem som besøgt. Nu bliver Component_Count 2, og status for toppunktlisten opdateres igen:
algoritmen fortsætter og vælger, kontrollerer status og kalder
. Toppunktet og dets tilstødende hjørner er mærket som besøgt, og Component_Count øges til 3. Algoritmen opdaterer toppunktlistestatus:
endelig vælger algoritmen, kalder
og gør som besøgt. Toppunktet har ingen tilstødende hjørner, så DFS vender tilbage, og Component_Count stiger til 4. Endelig opdaterer algoritmen status for toppunktlisten:
da algoritmen er færdig med at krydse alle grafens hjørner 
, afslutter den og returnerer værdien af Component_Count, som svarer til antallet af tilsluttede komponenter i div>. I dette tilfælde finder algoritmerne fire tilsluttede komponenter i :
Vi brugte fire forskellige farver til at illustrere de tilsluttede komponenter i , nemlig: 
.
Tidskompleksitetsanalyse
algoritmen, vi lige har set til at finde tilsluttede komponenter i en given ikke-rettet graf, bruger DFS-søgningen og tæller antallet af opkald til DFS-funktionen. Hvis grafen er repræsenteret af adjacency-listen, besøger DFS-søgningen alle hjørner en gang og hver kant to gange i tilfælde af en ikke-rettet graf. Kontrollen af toppunktstatus tager 
tid. Således i alt vil vores algoritme tage 
tid.
hvis grafen er repræsenteret af adjacency-matricen, tager DFS-søgningen 
tid, da den skal krydse hele rækken for at evaluere naboens hjørner. Kontrollen af toppunktstatus tager igen tid. Således giver os i alt 
tid.
konklusion
i denne artikel diskuterede vi en simpel definition af tilsluttet komponent efterfulgt af et par enkle og letforståelige eksempler. Vi har også nævnt nogle almindelige, men vigtige egenskaber ved tilsluttede komponenter.
derefter diskuterede vi en DFS-søgebaseret algoritme for at finde antallet af tilsluttede komponenter i en given graf. Vi demonstrerede algoritmen ved hjælp af en prøvegraf. Endelig analyserede vi algoritmens tidskompleksitet.