cicli di spotting graph - spiegazione semplice

Question

cicli di spotting graph - spiegazione semplice

#1 da (6 voti)
#2 da (0 voti)

9

alcuni potrebbero aiutarmi, per favore, a capire come trovare i cicli nei grafici nei termini dei laici?

Ho letto altre domande, come This uno e anche alcune delle pagine di Wikipedia, ma sembrano discendere piuttosto rapidamente in gergo matematico.

Ho un modello del grafico in java, nei nodi di modellazione e nei bordi "in" e "out" - e il modello conosce i nodi collegati solo in una direzione, questo mi permette di trovare i nodi foglia come punto di partenza, il mio piano era di risalire il grafico da ciascuno di questi nodi foglia, per ogni "passeggiata", mantenendo un elenco di tutti gli altri nodi che ho trovato sul mio percorso. Se vedo qualcosa già nella lista in qualsiasi momento, saprò che ho trovato un ciclo nel grafico. Questo tuttavia sembra un po 'semplicistico.

Sono sicuro che questo è un problema risolto, sarebbe bello se potesse essere spiegato in termini semplici.

-Ace

graph

posta phatmanace 22.02.2013 - 00:49

fonte

2 risposte

0

Fondamentalmente, fai una larghezza prima ricerca sul grafico e tieni traccia di quali nodi hai visitato usando una hashmap.

In qualsiasi momento, se incontri un nodo che è già stato visitato (presente in hashmap), allora sai che c'è un ciclo nel grafico.

risposta data 22.02.2013 - 07:51

fonte

Leggi altre domande sui tag graph

Qual è stato l'impatto storico del Volo 501 di Ariane 5? Funzioni Macro e Statiche nell'intestazione

score 6 · Accepted Answer

Il modo più semplice che riesco a pensare per spiegare i cicli di spotting graph in parole povere, è qualcosa di simile a questo:

In primo luogo, presumo che tu conosca le basi di cosa sia un grafico e quali sono i nodi e i bordi. Questo esempio presuppone che tu abbia un grafico in cui tutti i bordi sono solo a senso unico.
Crea il tuo grafico e seleziona un nodo come punto di partenza.
Crea un oggetto contenitore di qualche tipo (un elenco o un hash funzionerebbe meglio). Chiamalo "Visitato".
Crea un secondo oggetto contenitore (una coda sarebbe ideale qui) e chiamala "Apri".
Aggiungi il nodo iniziale all'elenco Apri.
Ripeti mentre la lista aperta non è vuota:
- Rimuovi il primo elemento da Apri e chiamalo corrente
- Se Current esiste in Visited, hai un ciclo.
- In caso contrario, aggiungi Current to Visited, quindi aggiungi tutti i nodi che Current può raggiungere dai suoi bordi in uscita a Open.
Se Open finisce vuoto e non sono stati rilevati cicli, allora non hai cicli. (Almeno non nel set raggiungibile proveniente dal punto di partenza, che non è necessariamente la totalità del tuo grafico se hai delle isole nel tuo grafico.)