Traversal of cyclic direct graph

Question

Ho un grafico ciclico diretto. Partendo dalle foglie, desidero propagare i dati collegati a ciascun nodo a valle a tutti i nodi raggiungibili da quel nodo. In particolare, ho bisogno di continuare a spingere i dati attorno a tutti i cicli che vengono raggiunti fino a quando i cicli si stabilizzano.

Sono assolutamente sicuro che si tratti di un problema di attraversamento del grafico azionario. Tuttavia, sto avendo un bel po 'di difficoltà nel cercare di trovare un algoritmo adatto --- Penso che manchi alcune parole chiave cruciali per la ricerca.

Prima di tentare di scrivere il mio algoritmo O (n^3) semi-assente, qualcuno può indicarmi una soluzione adeguata? E cosa è chiamato ?

Answer 1

Poiché il grafico è ciclico (vale a dire può contenere cicli), vorrei prima scomporlo in componenti fortemente connessi. Un strongly connected component di un grafo orientato è un sottografo in cui ogni nodo è raggiungibile da ogni altro nodo nello stesso sottografo. Ciò produrrebbe una serie di sottografi. Si noti che un componente fortemente connesso di più di un nodo è effettivamente un ciclo.

Ora, in ogni componente, qualsiasi informazione in un nodo finirà per finire in ogni altro nodo del grafico (dato che sono tutti raggiungibili). Quindi per ogni sottografo possiamo semplicemente prendere tutti i dati da tutti i nodi in esso e fare in modo che ogni nodo abbia lo stesso insieme di dati. Non c'è bisogno di continuare a superare i cicli. Inoltre, alla fine di questo passaggio, tutti i nodi nello stesso componente contengono esattamente gli stessi dati.

Il prossimo passo sarebbe quello di collassare ogni componente fortemente connesso in un singolo nodo. Poiché i nodi all'interno dello stesso componente hanno tutti gli stessi dati e sono quindi fondamentalmente gli stessi, questa operazione non modifica realmente il grafico. Il "super nodo" appena creato erediterà tutti i bordi che escono o entrano nei nodi del componente da nodi esterni al 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 messi in stesso componente in primo luogo). Il grafico risultante ora è un Directed Acyclic Graph. Non ci sono cicli e una semplice prima attraversamento di profondità da tutti i nodi con indegree = 0 (cioè nodi che non hanno bordi in entrata), la propagazione dei dati da ciascun nodo ai nodi adiacenti (cioè i suoi "figli"), dovrebbe portare a termine il lavoro .