Attraversamento del grafo orientato ciclico

Question

Ho un grafo ciclico diretto. Partendo le foglie, desidero dati Propaga collegati a ciascun nodo downstream a tutti i nodi raggiungibili da tale nodo. In particolare, ho bisogno di continuare a spingere dati circa eventuali cicli che si raggiungono fino i cicli stabilizzano.

Sono completamente sicuro che questo è un problema di attraversamento stock graph. Tuttavia, sto avendo un po 'di difficoltà cercando di trovare un algoritmo adatto --- penso che mi manca qualche cruciali parole chiave di ricerca.

Prima tento di scrivere il mio algoritmo assed O (n ^ 3), qualcuno può punto me in una soluzione adeguata? E che è questo problema particolare chiamato?

Answer 1

Poiché il grafico è ciclica (cioè può contenere cicli), innanzi scomposizione in componenti fortemente connesse. Un fortemente connesso componente di un grafo orientato è un sottografo dove ogni nodo è raggiungibile da ogni altro nodo lo stesso sottografo. Ciò comporterebbe una serie di sottografi. Si noti che un componente fortemente connessa di più di un nodo è effettivamente un ciclo.

Ora, in ogni componente, le informazioni in un nodo alla fine arriverà in ogni altro nodo del grafo (poiché sono tutti raggiungibili). Quindi per ogni sottografo possiamo semplicemente prendere tutti i dati da tutti i nodi in esso e rendere ogni nodo ha lo stesso insieme di dati. Non c'è bisogno di andare avanti attraverso i cicli. Inoltre, al termine di questa fase, tutti i nodi della stessa componente contiene esattamente gli stessi dati.

Il passo successivo consiste nel comprimere ciascun componente fortemente connessa in un unico nodo. Poiché i nodi all'interno dello stesso componente hanno tutti gli stessi dati, e sono quindi sostanzialmente la stessa, questa operazione non cambia il grafico. La nuova creazione "nodo super" erediterà tutti i bordi uscire o entrare in nodi del componente dai nodi al di fuori del componente.

Poiché abbiamo collassato componenti tutti fortemente collegati, non ci saranno cicli nel grafico risultante (perché? Perché se ci fosse stato un ciclo formata dai nodi derivano, sarebbero tutti sono stati collocati nello stesso componente nel primo posto ). Il grafico risultante è ora un Aciclica grafo diretto . Non ci sono cicli, ed una profondità semplice primo attraversamento da tutti i nodi con indegree = 0 (cioè i nodi che hanno bordi entranti), la propagazione dei dati da ogni nodo per i nodi adiacenti (cioè suoi "figli"), dovrebbe ottenere il lavoro fatto .