Uso di Componente fortemente connesso Algo per verificare se un vertice è raggiungibile

Question

Vorrei vedere se un dato vertice, ad esempio V0, può essere raggiungibile da tutti gli altri vertici in un grafico G.
So che posso semplicemente attraversare ogni vertice nel grafico e fare BFS/DFS per vedere se V0 è raggiungibile.
Tuttavia, questo sembra essere molto inefficiente.

Mi chiedevo se faccio SCC algo sul grafico e se v0 è parte di tutti scc, allora posso tranquillamente concludere che v0 è raggiungibile con tutti i vertici? Questo sarebbe grandioso perché il costo di SCC è solo O (V + E) con Tarjan e il controllo per vedere se v0 fa parte di scc costerebbe anche un tempo lineare.

Penso che abbia senso perché SCC indica che i vertici sono raggiungibili. Qualche conferma a questa logica?

o un approccio efficace a questo?

Answer 1

V0 non può appartenere a SCC, ma è comunque raggiungibile da tutti gli altri vertici. Ad esempio, il vertice d sul diagramma è raggiungibile da tutti gli altri vertici, ma l'unico SCC non banale contiene i vertici a, , c e non contiene il vertice d.

Per controllare se V0 è raggiungibile da tutti gli altri vertici, è possibile invertire la direzione di ogni bordo (in tempo lineare), quindi utilizzare BFS/DFS, partendo da V0, per verificare se ogni altro vertice è raggiungibile da V0 (anche in tempo lineare).

Answer 2

Chiamiamo un vertice da cui tutti gli altri vertici sono raggiungibili, un vertice di vista. Se il grafico ha un vertice di vista, allora deve avere solo una sorgente SCC (poiché due SCC di origine non sono raggiungibili l'uno dall'altro), che deve contenere il vertice di vista (se è presente in qualsiasi altro SCO , non c'è alcun percorso dal vertice vista all'origine SCC). Inoltre, in questo caso ogni vertice nell'SCC di origine sarà un vertice di vista. L'algoritmo è quindi semplicemente un DFS che inizia da qualsiasi nodo e contrassegna il vertice con il tempo di finitura più elevato . Questo deve essere in una fonte SCC. Ora eseguiamo nuovamente un DFS da questo vertice per verificare se siamo in grado di raggiungere tutti i nodi. Poiché l'algoritmo utilizza solo la scomposizione in SCC e DFS , il tempo di esecuzione è lineare. Questo algoritmo è corretto. Si noti che un vertice di vista esisterà se e solo se è presente un solo SCC di origine . Qualsiasi vertice in un SCC di origine è raggiungibile solo da altri vertici nello stesso SCC, , quindi nessun vertice può raggiungere i vertici in due distinti SCC di origine. Inoltre, se c'è solo un SCC di origine, qualsiasi vertice in tale SCC è un vertice di vista in quanto tutti sono raggiungibili da ogni altro . Si noti che un DFS che inizia in un particolare SCC non finirà fino a quando tutti i SCC raggiungibili da esso siano stati esplorati. Ciò implica che l'ultimo nodo da finire si trova in un SCC che non è raggiungibile da nessun altro SCC, ad esempio un SCC di origine. Quindi nella prima parte del nostro algoritmo troviamo un nodo in un SCC di origine. Eseguendo DFS, determineremo correttamente indipendentemente dal fatto che si tratti o meno di un vertice della vista, e se non è un vertice di vista, sappiamo che nessuno esiste nel nostro grafico .