Quel est le moyen le plus efficace de déterminer si un graphe dirigé est singulièrement connecté ?

Question

Je travaille sur un projet dont l'un des problèmes est de dériver un algorithme pour vérifier si un graphe dirigé G=(V,E) est singulièrement connecté (il y a au plus un chemin simple de u à v pour tous les sommets distincts u, v de V.).

Bien sûr, vous pouvez le vérifier par force brute, ce que je fais en ce moment, mais je veux savoir s'il existe une méthode plus efficace. Quelqu'un pourrait-il m'indiquer la bonne direction ?

Answer 1

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

D'abord on trouve des composantes fortement connectées de G. Dans chaque composante forte, on cherche à trouver ces cas : 1) s'il y a une arête avant dans cette composante, elle n'est pas singulièrement connectée, 2) s'il y a une arête transversale dans cette composante, elle n'est pas singulièrement connexe, 3) s'il y a au moins deux arêtes arrière dans l'arbre enraciné au sommet u, vers des ancêtres propres de u, alors il n'est pas singulièrement connecté.

cela peut être fait en O(E). ( Je pense que sauf pour le cas 3, je n'ai pas pu l'implémenter correctement !!).

Si aucun des cas ci-dessus ne s'est produit, vous devriez vérifier s'il y a une arête transversale ou une arête vers l'avant sur G^SCC ( graphe G, avec les composantes fortes remplacées par des noeuds simples), puisque nous n'avons pas de backedges, cela peut être fait en répétant dfs sur chaque sommet de ce graphe en O(|V|^2).

Answer 2

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 car pas de répétition.

Answer 3

Lire celui-ci . Il explique vraiment bien.

Answer 4

Si vous pouvez faire une copie de l'ensemble du graphe (sommets plus arêtes), vous pouvez choisir un sommet, exécuter DFS comme décrit par Neeraj, et s'il semble singulièrement connecté à partir de là, vous pouvez réduire tous les sommets visités en un seul sommet (faites-le avec une table de hachage). Ensuite, vous trouvez un autre sommet non connecté et vous recommencez. Vous devriez être capable de faire cela en O(V+E). Dans un graphe simplement connecté, E

Si le graphe est déconnecté, cette méthode vous indiquera également le nombre de sous-graphes disjoints. (Comptez combien de mappings distincts restent dans votre table de hachage à la fin).

Answer 5

Je ne suis pas d'accord avec le fait que sa complexité sera O(V^2), car dans DFS, nous ne l'appelons pas pour chaque sommet, comme on peut le voir dans le livre Introduction to algorithm également, la syntaxe est DFS(G). Nous n'appelons DFS que pour le graphe entier et non pour un seul sommet, contrairement à BFS. Si un sommet visité est rencontré à nouveau, le graphe n'est pas singulièrement connecté (nous devons certainement l'appeler pour chaque composant déconnecté mais c'est déjà inclus dans le code). Donc la complexité sera O(V+E). Comme ici E=V, la complexité devrait être O(V).