Qual è il modo più efficiente per determinare se un grafo orientato è singolarmente collegato?

Question

Sto lavorando su un incarico dove uno dei problemi chiede per derivare un algoritmo per controllare se un grafo orientato G = (V, E) è singolarmente collegata (c'è al massimo un semplice percorso da u a v per tutte distinte vertici u, v V.

Naturalmente è possibile forza bruta controllare, che è quello che sto facendo adesso, ma voglio sapere se c'è un modo più efficiente. qualcuno mi potrebbe punto nella 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 nessuna ripetizione.

Answer 2

C'è una risposta migliore per questa domanda. si può fare a O (| V | ^ 2). e con più sforzo si può fare in tempo lineare.

Per prima cosa è trovare componenti fortemente connesse di G. in ogni componente forte, si cerca di trovare questi casi: 1) se v'è un bordo anteriore di questo componente, non è singolarmente collegato, 2) se v'è un bordo trasversale di questo componente, non è singolarmente collegato, Non 3) se ci sono almeno due bordi posteriori in albero radicato al vertice u, ai propri antenati di u, allora è singolarmente collegato.

questo può essere fatto in O (E). (Penso ad eccezione di casi 3. non ho potuto implementare bene !!).

Se nessuno dei casi di cui sopra si è verificato, si dovrebbe verificare se v'è un fronte trasversale o un bordo anteriore su G ^ SCC (grafo G, con forti componenti sostituiti con i nodi singoli), dal momento che non abbiamo backedges, si può essere svolto da DFS ricorrenti di ogni vertice di questo grafico a O (| V | ^ 2).

Answer 3

Leggi questo . Spiega molto bene.

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 anche, sintassi è DFS (G). Chiamiamo solo DFS per intero grafico non per ogni singolo vertice differenza BFS. Così qui, in questo caso secondo me dobbiamo controllare chiamando DFS once.If un vertice visitato si incontra ancora una volta, il grafico non è collegato singolarmente (sicuramente dobbiamo chiamarla per ogni componente scollegato ma già incluso nel codice ). SO complessità sarà O (V + E). Come qui E = V quindi complessità dovrebbe essere O (V).

Answer 5

ho pensato a questo: 1) Eseguire DFS da qualsiasi vertice, se tutti i vertici sono coperti in DFS senza bordi anteriori (non ci può essere croce come altro non sono coperti tutti i vertici), allora può essere un potenziale candidato.

2) Se un vertice (livello j) che si trova nella DFS ha un bordo posteriore di livello i allora nessun altro vertice trovato dopo che dovrebbe avere un bordo verso un vertice con livello inferiore j e ogni vertice molto essere raggiungibile alla radice (controllato con secondo DFS).

Questo fa in tempo lineare se questo è corretto.

Answer 6

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

Il seguente documento utilizza componente fortemente collegato per risolvere questo.

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

Answer 7

Esegui DFS una volta da ciascun vertice. Il grafico è singolarmente connesso se e solo se non vi sono bordi anteriori e non vi siano spigoli trasversali di un componente.

Complessità: O (V.E)