Un sommet mère dans un graphe orienté G = (V, E) est un sommet v tel que tous les autres sommets G peuvent être atteints par un chemin dirigé à partir de v Donner un algorithme O (n + m) pour tester si le graphe G contient un sommet mère.Comment trouver le sommet mère dans un graphe orienté dans O (n + m)?
(c) du manuel Skiena
Trouvé seulement O (n (n + m)) façon
Quand googler, j'ai trouvé la réponse here. Si c'est devoirs, vous devriez réfléchir à deux fois avant de jeter un coup d'oeil :)
J'ai vu la solution. Je ne pense pas que nous devons trouver SCC. Faites simplement un DFS à partir d'un sommet aléatoire, puis faites le DFS à partir du sommet avec la dernière heure de fin. S'il y a un sommet mère alors ça doit être ça.
étape1. Faire un tri topologique des sommets du graphe orienté.
étape2. Vérifiez maintenant si nous pouvons atteindre tous les sommets de premier sommet des sommets classés topologiquement à l'étape 1.
Pour effectuer une étape 2, encore une fois l'initialisation tableau découvert [i] false et faire DSF Startin du premier noeud topologiquement sommets triés.
Si tous les sommets peuvent être atteints, alors le graphe a un sommet mère et le sommet mère sera le premier des sommets triés topologiquement.
complexité temporelle: Etape 1 prend O(n + m), l'étape 2 prend O(n + m) si totale O(n+m) + O(n+m) = O(n+m)
algorithme de
a) faire DFS/BFS du graphique et de garder la trace du dernier sommet fini 'X' .
b) S'il existe un sommet mère, alors 'x' en fait partie. Vérifiez si 'x' est un sommet mère en faisant DFS/BFS à partir du sommet 'x'.
Complexité O (n + m) + O (n + m) = O (n + m)
cela fonctionnera pour le graphique suivant, si je commence à partir de B comme sommet au hasard? A-> B B-> A A-> C A-> D – learner