Trovare tutti sottografi disconnesse in un grafico

Question

Ho un grafico che contiene un numero imprecisato di sottografi scollegati. Che cosa è un buon algoritmo (o libreria Java) per trovare tutti?

Answer 1

Credo che quello che state cercando è generalmente chiamato Riempimento . Spetta a te decidere se attraversare il grafico attraverso una BFS o un DFS.

Fondamentalmente si prende un nodo non marcato (AKA incolori) e assegna una nuova etichetta ad esso. Si assegna la stessa etichetta a tutti i nodi adiacenti a quello, e così via per tutti i nodi raggiungibili da tale nodo.

Quando nessun nodo più raggiungibili possono essere etichettati, si ricomincia da capo con la scelta di un altro nodo senza etichetta. Si noti che il fatto che questo nuovo nodo è senza etichetta implica che non è raggiungibile dal nostro precedente nodo ed è quindi in una diversa componente scollegato.

Quando non ci sono più nodi senza etichetta, il numero di etichette distinte si doveva utilizzare è il numero di componenti del grafico. L'etichetta per ogni nodo indica quale nodo è parte del quale componente.

Answer 2

Non è un'implementazione Java, ma forse sarà utile per qualcuno, ecco come farlo in Python:

import networkx as nx
g = nx.Graph()
# add nodes/edges to graph
d = list(nx.connected_component_subgraphs(g))
# d contains disconnected subgraphs
# d[0] contains the biggest subgraph

Maggiori informazioni qui .

Answer 3

Ci sono molte sfaccettature di questa domanda che non sono pienamente spiegato, così ho intenzione di dare una risposta in qualche modo esaustivo. La mia tendenza per pubblicare pareti-di-text in deroga. :. / Si noti inoltre che sto assumendo questo è una domanda compiti a casa o di auto-educazione domanda, quindi non ho intenzione di dare una risposta diretta-up

I due algoritmi di base per rilevare la connettività di un grafico è ricerca in profondità e < a href = "http://en.wikipedia.org/wiki/Breadth-first_search" rel = "noreferrer"> ricerca in ampiezza . Questi sono davvero i 2 punti di partenza che si desidera guardare. Entrambi ti porterà alla soluzione, ma in modi diversi, e la sua difficile sostenere che è "meglio", senza considerare alcuni aspetti piuttosto di approfondimento del problema. Ma andiamo avanti.

Come ho detto prima, è lasciato fuori alcuni dettagli importanti, e io tocco su alcune possibilità qui.

È il vostro grafo orientato o non orientato? e consideri la connettività in senso "forte" (in questo caso, vedere la risposta di oggy), o la connettività nel senso "debole"? A seconda della risposta, si dovrà affrontare il vostro algoritmo in un modo leggermente diverso. Si noti che, per un grafo non orientato, connettività deboli e forti sono equivalenti, in modo che sia bello. Ma si dovrà mantenere la struttura del grafico in mente a prescindere, durante l'implementazione o la ricerca di un algoritmo.

Inoltre, v'è la questione di che cosa si intende per "trovando le sottografi" (parafrasare). Di solito la connettività grafo è un problema decisionale - semplicemente "c'è un grafo connesso" o "ci sono due o più sotto-grafici (alias, è scollegato)". Avere un algoritmo per che richiede la minor quantità di bruco di biblioteca, che è bello. :) Il passo successivo sarebbe la count di grafici, letteralmente il numero di essi, e che bruco di biblioteca inoltre, non è poi così male. Penultimately, può essere utile una lista di nodi in ogni sub-grafico. Infine, si consiglia di copiare letteralmente fuori le sotto-grafici, spigoli e tutti (in modo che il tipo di ritorno sarebbe un elenco di grafici, suppongo, con un invariante implicita che ogni grafico è collegato). Nessuno di questi diversi tipi di risultato-richiederebbe un algoritmo diverso, ma sicuramente richiedono un approccio diverso al bruco di biblioteca.

Tutto questo può sembrare una quantità ridicola di eccessivo per quello che è una domanda piuttosto semplice, ma ho pensato solo evidenziare tutti gli aspetti coinvolti nella nemmeno come una semplice domanda grafico. Come una sorta di colpo di scena, si noti come niente di tutto questo ancora nemmeno tocca fase di esecuzione o l'utilizzo di memoria! :) - Agor

Answer 4

JGraphT è una bella libreria grafica open source rilasciato sotto licenza LGPL. Ho usato in passato per trattare con grafici e cicli di rilevamento all'interno dei grafici. E 'anche abbastanza facile da usare, ed è possibile utilizzare Jgraph di visualizzare i grafici.

Answer 5

sto supponendo che si desidera trovare tutti i componenti (fortemente) collegati? Per questo si può utilizzare di Tarjan algoritmo (una variante di DFS)

Answer 6

Che dire di una ricerca in ampiezza per trovare tutti i nodi collegati? Una volta che avete l'elenco dei nodi collegati, si sottrae a questa lista dalla lista di tutti i nodi. Si finisce con una lista di nodi disconnessi

Answer 7

Ho incontrato un problema simile in cui ho voluto tutte le sottografi debolmente connesse di un grafo orientato. Ho bloggato su di esso qui . Ho usato il JUNG API e confrontare due approcci. Il mio primo approccio potrebbe essere utilizzato come modello per risolvere il problema.