grafi non connessi

[redcloud]

Salve. Se da un grafo connesso elimino un nodo, come faccio a capire se il grafo è ancora connesso o si è trasformato in due grafi separati (ognuno dei due connesso)?

[SergiusXP]

Scusa? oO

[redcloud]

Ho un grafo a forma di farfalla, in cui le due ali (composte da più nodi) sono collegate ad un unico nodo (il corpo). Il grafo è connesso ma se elimino il nodo centrale, il grafo non è più connesso e si è diviso in due grafi connessi. Questo è un caso semplice. Ma se invece voglio cancellare un nodo di un'ala, come faccio a capire sistematicamente che il grafo è ancora connesso e non si è diviso in più grafi?

[pallinopinco]

Se da un grafo connesso elimino un nodo, come faccio a capire se il grafo è ancora connesso o si è trasformato in due grafi separati (ognuno dei due connesso)?

Implementi un algoritmo BFS (Breadth-first search) o un DFS (Depth-first search).

[redcloud]

Originariamente inviato da pallinopinco
Implementi un algoritmo BFS (Breadth-first search) o un DFS (Depth-first search).

E come lo applico praticamente?

[pallinopinco]

E come lo applico praticamente?

Confronti il numero di nodi visitati da uno degli algoritmi citati con il numero di nodi che compongono il grafo non diretto. Se non riesci a visitare tutti i nodi il grafo non è connesso.

[redcloud]

Originariamente inviato da pallinopinco
Confronti il numero di nodi visitati da uno degli algoritmi citati con il numero di nodi che compongono il grafo non diretto. Se non riesci a visitare tutti i nodi il grafo non è connesso.

In realtà ho bisogno di identificare quali nuovi grafi si sono creati, non mi basta sapere che il grafo di partenza non è più connesso.

[pallinopinco]

...come faccio a capire se il grafo è ancora connesso o si è trasformato in due grafi separati

come faccio a capire sistematicamente che il grafo è ancora connesso e non si è diviso in più grafi?

...sono parole tue.

Spiega bene cosa significa "ho bisogno di identificare quali nuovi grafi si sono creati", come hai definito le strutture dati e quale linguaggio di programmazione usi.

[redcloud]

Originariamente inviato da pallinopinco
...sono parole tue.

Spiega bene cosa significa "ho bisogno di identificare quali nuovi grafi si sono creati", come hai definito le strutture dati e quale linguaggio di programmazione usi.

In effetti all'inizio pensavo mi bastasse solo sapere se il grafo era connesso. Mi serve il concetto comunque, è una cosa che esula dal linguaggio e da strutture dati particolari. Per "identificare" intendo tenere traccia di almeno 1 nodo per ogni nuovo grafo che si viene a creare.