Comment puis-je concevoir un algorithme en utilisant des algorithmes 1) initialiser tous les sommets comme non visités.
2) Faites une traversée DFS de graphique à partir de n'importe quel sommet vontex arbitraire.
Si TRAVERSAL DFS ne visitent pas tous les sommets, retournez FALSE.
3) Inversez tous les arcs (ou trouvez Transpose ou Reverse du graphique)
4) Marquez tous les sommets comme non visités dans un graphique inversé.
5) Faites une traversée DFS du graphe inversé à partir du même sommet V
(Comme l'étape 2). Si DFS Traverse ne visitent pas tous les sommets, alors
retourne faux. Sinon retourne vrai.
L'idée est que chaque nœud puisse être atteint d'un sommet V, et chaque
Le nœud peut atteindre V, puis le graphique est fortement connecté. À l'étape 2, nous
Vérifiez si tous les sommets sont accessibles à partir de v. À l'étape 4, nous vérifions si tous
Les sommets peuvent atteindre V (dans un graphique inversé, si tous les sommets sont accessibles
de V, alors tous les sommets peuvent atteindre V dans le graphique original).
Une idée de comment améliorer cette solution?
4 Réponses :
Du
sommets = entrée
- let
résultats = Liste vide
- Bien qu'il y a des sommets dans
sommets :
- Créer un ensemble
s
- Choisissez un sommet arbitraire inexploré et mettez-le dans
s .
- Exécutez BFS / DFS à partir de ce sommet, et avec chaque sommet trouvé, retirez-le de
sommets et ajoutez-le à s . .
- Ajouter
s à résultats
- retour
résultats
Lorsque cela complète, vous aurez une liste d'ensembles de sommets, où chaque ensemble a été effectué à partir de la recherche de graphique à partir de certains sommets (rendant les sommets dans chaque ensemble connecté). En supposant un graphique non dirigé, cela devrait fonctionner correctement (hors top de ma tête).
Quelle est la complexité de cette approche?
Une approche standard de résolution de ce problème consiste à exécuter DFS à partir de chaque nœud.
Commencez par étiqueter tous les nœuds comme non visionnés. Ensuite, itérale sur les nœuds dans n'importe quel ordre. Pour chaque nœud, s'il n'est pas déjà étiqueté comme étant dans un composant connecté, exécutez DFS de ce nœud et marquez tous les nœuds accessibles comme étant dans le même CC. Si le nœud était déjà marqué, passez-le. Cela découvre ensuite tous les CC du graphique un cc à la fois.
En outre, c'est très efficace. S'il y a des bords et n nœuds, le temps d'exécution est O (n) pour la première étape (marquage de tous les nœuds comme non visionnés) et O (m + n) pour la seconde, car chaque nœud et bord sont visités au plus deux fois. Ainsi, le temps d'exécution global est O (M + N).
J'espère que cela vous aide!
Mais comment identifiez-vous l'ensemble de nœuds dans chaque CC après?
Une option consiste à maintenir un ensemble de nœuds lorsque vous faites chaque DFS. Vous commencez par un ensemble vide puis ajoutez chaque noeud tel qu'il est découvert.
Étant donné que vous semblez travailler avec un graphique dirigé et que vous souhaitez trouver les composants connectés (pas fortement connectés), vous devez convertir votre graphique en un graphique non dirigé. Donc, pour chaque sommet, ajoutez un sommet temporaire dans la direction opposée. Ensuite, vous pouvez utiliser un simple DFS à partir de chaque sommet qui n'a pas encore été visité pour trouver les composants connectés. Enfin, vous pouvez supprimer les sommets temporaires.
Ceci peut être fait facilement à l'aide de BFS ou de DFS dans la complexité de temps de O (V + E).
// CC 1: 0 1 2 3 4 // CC 2: 5 // CC 3: 6 7 8
Vous recherchez composants connectés ou des composants fortement connectés ? Votre approche est très similaire (sinon identique) pour trouver des composants ultra-fortement connectés maximaux dans un graphique, mais si vous n'avez besoin que de composants connectés, cela peut être fait plus facile avec un seul BFS / DFS.
Voulez-vous que les composants connectés d'un graphique dirigé ou du SCC d'un graphique non dirigé?
J'ai besoin de déterminer les composants connectés donnés à un graphe connecté, im une semaine bloquée avec cette tâche.
Que diriez-vous: 1 Commencez à n'importe quel noeud arbitraire du graphique, G 2.Procevez à partir de ce nœud à l'aide de la première fois à la première ou à la largeur, en comptant tous les nœuds atteints. 3. Une fois que le graphique est entièrement traversé, si le nombre de nœuds comptabilisés est égal au nombre de nœuds de g, le graphique est connecté; Sinon, il est déconnecté.
Si le graphique est dirigé, vous pouvez exploiter ce fait pour atteindre des résultats plus rapides. En outre, toute autre structure connue spécifique pourrait potentiellement être utilisée (Ex: Avons-nous des nœuds racines? Les feuilles sont-elles connues dans une liste? Et ainsi de suite)