Come posso trovare tutti i vertici in un grafico direttotale che ogni altro vertice è raggiungibile da questo? Ora posso "inventare" solo O (| V | ^ 3) algo - un DFS / BFS da ogni vertice, ma sono sicuro che esiste un modo più veloce per risolverlo.
Grazie!
risposte:
4 per risposta № 1Esegui a Algoritmo dei componenti fortemente connesso per comprimere il grafico in a grafico aciclico diretto delle sue componenti fortemente connesse. Ci deve essere almeno un componente fortemente connesso senza bordi in entrata. Se ce n'è esattamente uno, i nodi di quel componente sono quelli che stai cercando.Se ci sono più componenti fortemente connessi senza bordi in entrata, non ci sono nodi da cui tutti gli altri nodi sono raggiungibili.
0 per risposta № 2
EDIT: vedi i commenti qui sotto!
A volte è tutto sulla terminologia: qui la parola magica è raggiungibilità (vedi Wikipedia). Sfortunatamente, non credo ti piacciano i risultati.
- Se non tutte le risposte sono necessarie, l'esecuzione di BFS / DFS è effettivamente raccomandata.
- Altrimenti, usa l'algoritmo di Floyd-Warshall. Funziona ancora in O (| V |3).
- Alcuni algoritmi ottimizzati esistono per casi speciali - vedi Wikipedia per maggiori dettagli.
Quindi probabilmente non è quello che volevi sentire.