Algorithme pour vérifier si le graphe dirigé est fortement connecté

StackOverflow https://stackoverflow.com/questions/1434787

Question

Je dois vérifier si un graphe dirigé est fortement connecté ou, en d'autres termes, si tous les nœuds peuvent être atteints par un autre nœud (pas nécessairement par le bord direct).

L’une des façons de procéder consiste à exécuter un système de fichiers DFS et un système de fichiers BFS sur chaque nœud et à voir que tous les autres sont toujours accessibles.

Existe-t-il une meilleure approche pour le faire?

Était-ce utile?

La solution

algorithme de Tarjan à composants fortement connectés (ou Variation de Gabow suffira bien sûr; s'il n'y a qu'un seul composant fortement connecté, le graphique est fortement connecté.

Les deux sont du temps linéaire.

Comme avec une première recherche de profondeur normale, vous suivez le statut de chaque nœud: nouveau, vu mais toujours ouvert (il se trouve dans la pile d’appel), puis vu et terminé. En outre, vous stockez la profondeur lorsque vous atteignez un nœud pour la première fois, et la profondeur la plus basse pouvant être atteinte à partir du nœud (vous le savez lorsque vous avez terminé un nœud). Un nœud est la racine d'un composant fortement connecté si la profondeur la plus basse accessible est égale à sa propre profondeur. Cela fonctionne même si la profondeur à laquelle vous atteignez un nœud à partir de la racine n'est pas le minimum possible.

Pour vérifier si le graphe entier est un seul SCC, lancez le dfs à partir de n'importe quel nœud. Lorsque vous avez terminé, si la profondeur la plus basse est 0, et que chaque nœud a été visité, le graphe entier est alors affiché. fortement connecté.

Autres conseils

Considérez l'algorithme suivant.

  1. Commencez à un sommet aléatoire v du graphique G, puis exécutez une DFS(G, v).

    • Si u ne parvient pas à atteindre tous les sommets du graphe DFS, il existe un sommet O(n + m), de sorte qu'il n'y a pas de chemin dirigé de O(2(n + m)) = O(n + m) à <=>, et donc <=> n'est pas fortement connecté .

    • S'il atteint tous les sommets, il existe un chemin dirigé de <=> à tous les autres sommets du graphique <=>.

  2. Inverse la direction de toutes les arêtes du graphe orienté <=> .

  3. Exécutez à nouveau un <=> à partir de <=>.

    • Si le DFS ne parvient pas à atteindre chaque sommet, il existe un sommet <=>, tel que dans le graphique d'origine, il n'y a pas de chemin dirigé de <=> à <=>.

    • Par contre, s'il atteint tous les sommets, le graphe d'origine contient un chemin dirigé de chaque sommet <=> à <=> .

Ainsi, si G " passe " les deux DFS, il est fortement connecté. De plus, puisqu'un DFS s'exécute dans un <=> temps, cet algorithme s'exécute dans un <=> temps, car il nécessite 2 traversées DFS.

Pour vérifier si chaque nœud a les deux chemins d'accès vers et depuis tous les autres nœuds d'un graphe donné:

1. DFS / BFS de tous les nœuds:

L'algorithme de Tarjan suppose que chaque nœud a une profondeur d[i]. Initialement, la racine a la plus petite profondeur. Et nous faisons les mises à jour DFS post-commande d[i] = min(d[j]) pour tout voisin j de i. En fait, BFS fonctionne également bien avec la règle de réduction u ici. 

function dfs(i)
    d[i] = i
    mark i as visited
    for each neighbor j of i: 
        if j is not visited then dfs(j)
        d[i] = min(d[i], d[j])

S'il existe un chemin de transfert de v à d[u] <= d[v], alors d[v] <= d[u] <= d[v]. Dans le SCC, <=> tous les nœuds du SCC auront donc la même profondeur. Pour savoir si un graphique est un SCC, nous vérifions si tous les nœuds ont le même <=>.

2. Deux DFS / BFS à partir du noeud unique:

C’est une version simplifiée de l’ l'algorithme de Kosaraju & # 8217; . À partir de la racine, nous vérifions si chaque nœud peut être atteint par DFS / BFS. Ensuite, inversez la direction de chaque bord. Nous vérifions si chaque nœud peut être atteint à partir de la même racine à nouveau. Voir le code C ++ .

Vous pouvez calculer le chemin le plus court entre toutes les paires et voir s'il en existe une infinie. .

L'algorithme de Tarjan a déjà été mentionné. Mais je trouve généralement l'algorithme de Kosaraju , même s'il nécessite deux traversées du graphe . IIRC, il est également très bien expliqué dans CLRS. 

test-connected(G)
{
    choose a vertex x
    make a list L of vertices reachable from x,
    and another list K of vertices to be explored.
    initially, L = K = x.

    while K is nonempty
    find and remove some vertex y in K
    for each edge (y, z)
    if (z is not in L)
    add z to both L and K

    if L has fewer than n items
    return disconnected
    else return connected
}

Une façon de procéder consiste à générer la matrice laplacienne pour le graphique, puis calculer les valeurs propres et enfin compter le nombre de zéros. Le graphique est fortement connecté s'il n'existe qu'une seule valeur propre égale à zéro.

Remarque: faites attention à la méthode légèrement différente de création de la matrice laplacienne pour les graphes dirigés.

Vous pouvez utiliser l'algorithme simple basé sur DFS de Kosaraju & # 8217; qui effectue deux traversées de graphes DFS:

L'idée est que si chaque nœud peut être atteint à partir d'un sommet v et que chaque nœud peut atteindre v, le graphe est fortement connecté. À l'étape 2 de l'algorithme, nous vérifions si tous les sommets sont accessibles à partir de v. À l'étape 4, nous vérifions si tous les sommets peuvent atteindre v (Dans le graphe inversé, si tous les sommets sont accessibles à partir de v, ils peuvent tous atteindre v dans l'original. graphique).

Algorithme: 1) Initialisez tous les sommets comme non visités.

2) Effectuez une traversée DFS du graphe à partir de tout sommet arbitraire v. Si la traversée DFS ne & # 8217; t visite tous les sommets, puis renvoie false.

3) Inverser tous les arcs (ou trouver la transposition ou l'inverse du graphique)

4) Marquez tous les sommets comme non visités dans le graphe inversé.

5) Faites un parcours DFS de graphe inversé à partir du même sommet v (Identique à l’étape 2). Si la traversée DFS ne & # 8217; t ne visite pas tous les sommets, renvoie la valeur false. Sinon, renvoyer true.

Complexité temporelle: la complexité temporelle de l'implémentation ci-dessus est identique à celle de la recherche en profondeur d'abord qui est O (V + E) si le graphique est représenté à l'aide de la représentation par liste de contiguïté.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top