Qual è il modo più efficace per determinare se un grafico diretto è collegato singolarmente?

Question

Sto lavorando su un compito in cui uno dei problemi richiede di derivare un algoritmo per verificare se un grafo diretto G = (V, E) è collegato singolarmente (esiste al massimo un percorso semplice da u a v per tutti i vertici distinti u, v di V.

Ovviamente è possibile controllare la forza bruta, che è quello che sto facendo in questo momento, ma voglio sapere se c'è un modo più efficiente. Qualcuno potrebbe indicarmi la giusta direzione?

Answer 1

hai provato DFS.

Run DFS for every vertex in the graph as source 
    If a visited vertex is encountered again, the graph is not singly connected 
repeat for every unvisited vertex. 
The graph is singly connected. 

complessità O (V^2), o (v) DFS come nessun rappresentante etition.

Answer 2

C'è una risposta migliore per questa domanda. puoi farlo in O (| V |^2). e con più impegno puoi farlo in tempo lineare.

Per prima cosa è trovare fortemente componenti di G. connessi in ogni componente forte, si cerca di trovare questi casi: 1) se v'è un bordo di andata di questa componente, non è singolarmente collegato, 2) se non v'è un cross-edge in questo componente, non è collegato singolarmente, 3) se ci sono almeno due bordi posteriori nell'albero radicato al vertice u, ai propri antenati di u, quindi non è collegato singolarmente.

questo può essere fatto in O (E). (Penso che tranne per il caso 3. Non potrei implementarlo bene !!).

Se non si è verificato alcuno dei casi precedenti, è necessario verificare se vi è un bordo o un fronte in avanti su G^SCC (grafico G, con componenti forti sostituiti con nodi singoli), poiché non abbiamo backedge, può essere fatto ripetendo dfs su ogni vertice di questo grafico in O (| V |^2).

Answer 3

Esegui DFS una volta da ciascun vertice. Il grafico è collegato singolarmente se e solo se non ci sono bordi in avanti e non vi sono bordi trasversali all'interno di un componente .

Complessità: O (VE)

Answer 4

non sono d'accordo che la sua complessità sarà O (V^2), come in DFS non chiamiamo per ogni vertice, come vedere nella Introduzione all'algoritmo libro inoltre, la sintassi è DFS (G). Chiamiamo DFS solo per l'intero grafico, non per ogni singolo vertice, a differenza di BFS. Quindi qui in questo caso secondo me dobbiamo controllarlo chiamando DFS una volta. Se un vertice visitato viene incontrato di nuovo, il grafico non è collegato singolarmente (sicuramente dobbiamo chiamarlo per ogni componente disconnesso ma è già incluso nel codice). SO la complessità sarà O (V + E). Come qui E = V quindi la complessità dovrebbe essere O (V).

Answer 5

Ho pensato a questo: 1) Esegui DFS da qualsiasi vertice, se tutti i vertici sono coperti nel DFS senza bordi in avanti un potenziale candidato.

2) Se un vertice (livello j) che si trova nel DFS ha un margine posteriore al livello i, allora nessun altro vertice trovato dopo deve avere un margine posteriore verso qualsiasi vertice con livello inferiore a j e ogni vertice molto essere raggiungibile alla radice (controllato con secondo DFS).

Questo lo fa in tempo lineare se questo è corretto.

Answer 6

Leggi this one. Lo spiega davvero bene.

Answer 7

Dai un'occhiata alla definizione di percorso semplice.Un grafico ciclico può essere collegato singolarmente. DFS non funzionerà per A->B, B->A, che è collegato singolarmente.

Il seguente documento utilizza un componente fortemente connesso per risolvere questo problema.

https://www.cs.umd.edu/~samir/grant/khuller99.ps