Quel est le moyen le plus efficace pour déterminer si un graphe orienté Singly est connecté?

Question

Je travaille sur une mission où l'un des problèmes demande de dériver un algorithme pour vérifier si un graphe orienté G = (V, E) est individuellement connecté (il y a au plus un simple chemin de u à v pour tous distincts sommets u, v de V.

Bien sûr, vous pouvez vérifier la force brutale, ce qui est ce que je fais en ce moment, mais je veux savoir s'il y a un moyen plus efficace. Quelqu'un pourrait-il me diriger dans la bonne direction?

Answer 1

Avez-vous essayé 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.

Complexité O (v ^ 2), o (v) dfs que pas de répétition.

Answer 2

Il y a une meilleure réponse à cette question. vous pouvez le faire en O (| V | ^ 2). et avec plus d'effort que vous pouvez le faire dans le temps linéaire.

D'abord, vous trouverez des composants fortement connectés de G. dans chaque composante forte, vous effectuez une recherche pour trouver ce cas: 1) s'il y a un bord avant de ce composant, il n'a pas été connecté individuellement, 2) s'il y a un bord transversal de ce composant, il n'a pas été connecté individuellement, 3) s'il y a au moins deux bords arrière dans l'arbre dont la racine est à sommet u, ancêtres propres de u, alors il n'a pas été connecté séparément.

cela peut être fait en O (E). (Je pense à l'exception des cas 3. Je ne pouvais pas le mettre en œuvre bien !!).

Si aucun des cas ci-dessus eu lieu, vous devez vérifier s'il y a un bord transversal ou un bord avant sur G ^ SCC (graphique G, avec des composants solides remplacés par des nœuds simples), étant donné que nous n'avons pas backedges, il peut être effectuée par la répétition dfs sur chaque sommet de ce graphe en O (| V | ^ 2).

Answer 3

Lire celui-ci . Il explique très bien.

Answer 4

Je ne suis pas d'accord que sa complexité sera O (V ^ 2), comme dans DFS nous le faisons pas appel à tous les sommets que voir dans l'introduction à l'algorithme Ègalement, la syntaxe est DFS (G). Nous lançons un appel que DFS pour le graphique entier ne pour tout seul sommet à la différence BFS. Voici donc dans ce cas, selon moi, nous devons vérifier en appelant DFS once.If un sommet visité est rencontré à nouveau, le graphique n'est pas seul connecté (certainement nous devons l'appeler pour chaque composant déconnecté mais déjà inclus dans le code ). SO la complexité sera O (V + E). Comme ici E = V donc la complexité doit être O (V).

Answer 5

Je pensais à ceci: 1) Exécuter DFS de tout sommet, si tous les sommets sont couverts dans le DFS sans bords avant (il n'y a aucune croix comme autre tous les sommets seront couverts), il peut être un candidat potentiel.

2) Si un sommet (niveau j) qui se trouve dans le DFS a un bord arrière au niveau i alors aucun autre sommet trouvé après il devrait avoir un bord en arrière vers un sommet avec un niveau inférieur à j et tous les sommets bien être accessible à la racine (vérifiée par seconde DFS).

Ce qu'il fait en temps linéaire si cela est correct.

Answer 6

Jetez un oeil à la définition de chemin simple. Un graphe cyclique peut être relié individuellement. DFS ne fonctionnera pas pour A->B, B->A, qui est connecté séparément.

Le présent document utilise le composant fortement connecté pour résoudre ce problème.

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

Answer 7

Exécuter DFS une fois de chaque sommet. Le graphique est individuellement connecté si et seulement s'il n'y a pas des bords avant et il n'y a pas des bords croisés dans un composant.

Complexité: O (V.E)