Panoramica

In questo tutorial, discuteremo il concetto di componenti collegati in un grafico non orientato.

Esamineremo alcuni semplici esempi per ottenere una comprensione di base, quindi elencheremo le proprietà dei componenti collegati.

Connected Component Definition

Un componente connesso o semplicemente componente di un grafico non orientato è un sottografo in cui ogni coppia di nodi è connessa tra loro tramite un percorso.

Proviamo a semplificarlo ulteriormente, però. Un insieme di nodi forma un componente connesso in un grafico non orientato se un nodo dall’insieme di nodi può raggiungere qualsiasi altro nodo attraversando i bordi. Il punto principale qui è la raggiungibilità.

Nei componenti collegati, tutti i nodi sono sempre raggiungibili l’uno dall’altro.

Alcuni esempi

In questa sezione, discuteremo un paio di semplici esempi. Cercheremo di mettere in relazione gli esempi con la definizione sopra riportata.

3.1. Un componente connesso

In questo esempio, il grafico non orientato specificato ha un componente connesso:

Diamo un nome a questo grafico. Qui indica il set di vertici e indica il set di bordi di . Il grafico ha un componente connesso, chiamiamolo, che contiene tutti i vertici di. Ora controlliamo se il set tiene alla definizione o meno.

Secondo la definizione, i vertici nel set dovrebbero raggiungere l’un l’altro tramite un percorso. Siamo la scelta casuale dei vertici e :

• è raggiungibile in via:
• è raggiungibile in via:

I vertici e soddisfatto la definizione, e si potrebbe fare lo stesso con il vertice di coppie così.

3.2. Più di un componente connesso

In questo esempio, il grafico non orientato ha tre componenti collegati:

Let’s name this graph as , where , and . The graph has 3 connected components: and .

Ora, vediamo se i componenti collegati e soddisfano la definizione o meno. Sceglieremo a caso una coppia da ogni e set.

Dal set, scegliamo i verticie.

• è raggiungibile a tramite:
• è raggiungibile in via:

Ora prendiamo i vertici e dal .

• is reachable to
• is reachable to

Finally, let’s pick the vertices and from the set .

• is reachable to
• è raggiungibile in

Così, da queste semplici dimostrazioni, è chiaro che il e seguire il componente collegato definizione.

Proprietà

Come abbiamo già discusso la definizione e dimostrato un paio di esempi dei componenti collegati, è un buon momento per elencare alcune delle proprietà importanti che connected component detiene sempre.

Prima di tutto, il set di componenti connesso è sempre non vuoto.

Inoltre, se c’è più di un componente connesso per un dato grafico, l’unione dei componenti collegati darà l’insieme di tutti i vertici del grafico dato.

Per esempio :

Infine, i set di componenti collegati sono disgiunti a coppie. Ciò significa che se prendiamo l’intersezione tra due diversi set di componenti collegati, l’intersezione sarà uguale a un set vuoto o un set nullo.

Consideriamo di nuovo i componenti collegati del grafico. In , controlliamo questa proprietà:

Trovare componenti collegati

Dato un grafico non orientato, è importante scoprire il numero di componenti collegati per analizzare la struttura del grafico – ha molte applicazioni reali. Possiamo usare DFS o BFS per questa attività.

In questa sezione, discuteremo un algoritmo basato su DFS che ci fornisce il numero di componenti collegati per un dato grafico non orientato:

La variabile Component_Count restituisce il numero di componenti collegati nel grafico specificato.

Iniziamo inizializzando tutti i vertici al flag non visitato. Quindi scegliamo qualsiasi vertice casuale da avviare e controlliamo se abbiamo visitato il vertice o meno. Se non lo facessimo, chiamiamo la funzione DFS.

Una volta che tutti i vertici contrassegnati come visitati, l’algoritmo termina e stampa il numero dei componenti collegati.

Nella funzione DFS, gli argomenti che passiamo sono un set di vertici contenente tutti i vertici del grafico dato e un particolare vertice che deve appartenere al set di vertici.

Per prima cosa, contrassegniamo il particolare vertice di input come visitato. Quindi calcoliamo i vertici adiacenti del dato particolare vertice di input. Per ogni vertice adiacente, controlliamo se li abbiamo visitati o meno. In caso contrario, chiamiamo la funzione DFS ricorsivamente finché non contrassegniamo tutti i vertici adiacenti come visitati.

Il punto chiave da osservare nell’algoritmo è che il numero di componenti collegati è uguale al numero di chiamate di funzioni DFS indipendenti. La variabile Component_Count conta il numero di chiamate. Naturalmente, questo non include le chiamate che vengono effettuate sotto la funzione DFS() in modo ricorsivo.

Test Run

Eseguiamo l’algoritmo su un grafico di esempio:

Dato un grafico undirected , dove e .

Il primo passo dell’algoritmo è inizializzare tutti i vertici e contrassegnarli come non visitati.

Il vertice rosso indica che non è visitato. Il vertice verde indica che è visitato dall’algoritmo:

Possiamo scegliere qualsiasi vertice dall’elenco dei vertici per avviare l’algoritmo. Scegli .

L’algoritmo controlla se è visitato o meno. In questo caso, non viene visitato. Quindi chiama .

All’interno di DFS(), innanzitutto, etichetta il vertice come visitato e cerca i vertici adiacenti di . Anche tutti i vertici adiacenti sono contrassegnati come visitati. Quando DFS termina di visitare tutti i vertici adiacenti di , Component_Count diventa 1 e lo stato dei vertici viene aggiornato:

Ancora una volta, l’algoritmo sceglie qualsiasi vertice casuale. Selezioniamo questa volta.

Controlla se è già visitato o meno. Poiché non viene visitato, l’algoritmo chiama . Ancora una volta l’algoritmo contrassegna il vertice come visitato, e DFS cerca i suoi vertici adiacenti e li contrassegna come visitati. Ora Component_Count diventa 2 e lo stato dell’elenco dei vertici viene nuovamente aggiornato:

L’algoritmo continua e sceglie, controlla lo stato e chiama. Il vertice e i suoi vertici adiacenti sono etichettati come visitati e il Component_Count aumenta a 3. L’algoritmo aggiorna lo stato della lista dei vertici:

Infine, l’algoritmo sceglie, chiama e rende come visitato. Il vertice non ha vertici adiacenti, quindi DFS restituisce e Component_Count aumenta a 4. Infine, l’algoritmo aggiorna lo stato del vertice di listino:

Come l’algoritmo finito l’attraversamento di tutti i vertici del grafo termina e restituisce il valore di Component_Count che equivale al numero di componenti connesse in . In questo caso, gli algoritmi trovano quattro componenti collegati in :

Abbiamo utilizzato quattro differenti colori per illustrare le componenti connesse in , vale a dire: .

Analisi della complessità temporale

L’algoritmo che abbiamo appena visto per trovare componenti collegati in un dato grafico non orientato utilizza la ricerca DFS e conta il numero di chiamate alla funzione DFS. Se il grafico è rappresentato dall’elenco delle adiacenze, la ricerca DFS visita tutti i vertici una volta e ogni bordo due volte nel caso di un grafico non orientato. Il controllo dello stato del vertice richiede tempo. Quindi in totale, il nostro algoritmo richiederà tempo.

Nel caso in cui il grafico sia rappresentato dalla matrice di adiacenza, la ricerca DFS richiede tempo in cui deve attraversare l’intera riga per valutare i vertici vicini. Il controllo dello stato del vertice richiede nuovamente tempo. Quindi dandoci un totale di tempo.

Conclusione

In questo articolo, abbiamo discusso una semplice definizione di componente connesso seguita da un paio di esempi semplici e facili da capire. Inoltre, abbiamo elencato alcune proprietà comuni ma importanti dei componenti collegati.

Poi, abbiamo discusso un algoritmo basato su ricerca DFS per trovare il numero di componenti collegati in un dato grafico. Abbiamo dimostrato l’algoritmo con l’aiuto di un grafico di esempio. Infine, abbiamo analizzato la complessità temporale dell’algoritmo.