PDA

Visualizza la versione completa : grafi non connessi


redcloud
17-06-2008, 20:11
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
17-06-2008, 23:15
Scusa? oO

redcloud
18-06-2008, 01:41
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
18-06-2008, 01:59
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
18-06-2008, 12:03
Originariamente inviato da pallinopinco
Implementi un algoritmo BFS (Breadth-first search) o un DFS (Depth-first search).
E come lo applico praticamente?

pallinopinco
18-06-2008, 13:26
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
18-06-2008, 13:56
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
18-06-2008, 20:26
...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
18-06-2008, 20:49
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.

Loading