Quelles détections de cycle au sein d'un graphe dirigé sont plus efficaces que O(n^2) ?

Question

Existe-t-il un algorithme plus efficace en termes de temps que O(n^2) pour détecter les cycles au sein d'un graphe orienté?

J'ai un graphe orienté représentant un emploi du temps des tâches à exécuter, une tâche étant un noeud et une dépendance étant une arête. Je dois détecter le cas d'erreur d'un cycle au sein de ce graphe entraînant des dépendances cycliques.

Answer 1

L'algorithme des composantes fortement connexes de Tarjan a une complexité temporelle de O(|E| + |V|).

Pour d'autres algorithmes, voir Composantes fortement connexes sur Wikipedia.

Answer 2

Étant donné qu'il s'agit d'un planning de tâches, je soupçonne qu'à un moment donné vous allez les triez dans un ordre d'exécution proposé.

Si c'est le cas, alors une implémentation de tri topologique pourrait détecter des cycles. UNIX tsort le fait certainement. Je pense qu'il est donc probablement plus efficace de détecter les cycles en même temps que le tri topologique, plutôt que lors d'une étape séparée.

Donc la question pourrait être, "comment puis-je trier de la manière la plus efficace", plutôt que "comment détecter les boucles de la manière la plus efficace". La réponse est probablement "utiliser une bibliothèque", mais en cas d'échec l'article Wikipedia suivant:

http://fr.wikipedia.org/wiki/Tri_topologique

contient le pseudo-code d'un algorithme, et une brève description d'un autre de Tarjan. Les deux ont une complexité temporelle de O(|V| + |E|).

Answer 3

Selon le Lemme 22.11 de Cormen et al., Introduction to Algorithms (CLRS) :

Un graphe dirigé G est acyclique si et seulement si une recherche en profondeur de G ne produit pas de arêtes de retour.

Cela a été mentionné dans plusieurs réponses ; ici, je vais également fournir un exemple de code basé sur le chapitre 22 de CLRS. Le graphe exemple est illustré ci-dessous.

Le pseudo-code de CLRS pour la recherche en profondeur est le suivant :

Dans l'exemple de la Figure 22.4 de CLRS, le graphe se compose de deux arbres DFS : l'un composé des nœuds u, v, x et y, et l'autre des nœuds w et z. Chaque arbre contient une arête de retour : une de x à v et une autre de z à z (une boucle locale).

La clé de la réalisation est qu'une arête de retour est rencontrée lorsque, dans la fonction DFS-VISIT, en itérant sur les voisins v de u, un nœud avec la couleur GRAY est rencontré.

Le code Python suivant est une adaptation du pseudo-code de CLRS avec une clause if ajoutée qui détecte les cycles :

import collections

class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.adj = Graph._build_adjacency_list(edges)

    @staticmethod
    def _build_adjacency_list(edges):
        adj = collections.defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
            adj[edge[1]] # effets secondaires uniquement
        return adj

def dfs(G):
    discovered = set()
    finished = set()

    for u in G.adj:
        if u not in discovered and u not in finished:
            discovered, finished = dfs_visit(G, u, discovered, finished)

def dfs_visit(G, u, discovered, finished):
    discovered.add(u)

    for v in G.adj[u]:
        # Détecter les cycles
        if v in discovered:
            print(f"Cycle détecté : une arête de retour trouvée de {u} à {v}.")
            break

        # Récursivité dans l'arbre DFS
        if v not in finished:
            dfs_visit(G, v, discovered, finished)

    discovered.remove(u)
    finished.add(u)

    return discovered, finished

if __name__ == "__main__":
    G = Graph([
        ('u', 'v'),
        ('u', 'x'),
        ('v', 'y'),
        ('w', 'y'),
        ('w', 'z'),
        ('x', 'v'),
        ('y', 'x'),
        ('z', 'z')])

    dfs(G)

Remarquez que dans cet exemple, le time dans le pseudo-code de CLRS n'est pas capturé car nous nous intéressons uniquement à la détection des cycles. Il y a aussi un certain code de boilerplate pour construire la représentation de liste d'adjacence d'un graphe à partir d'une liste d'arêtes.

Lorsque ce script est exécuté, il imprime la sortie suivante :

Cycle détecté : une arête de retour trouvée de x à v.
Cycle détecté : une arête de retour trouvée de z à z.

Il s'agit exactement des arêtes de retour dans l'exemple de la Figure 22.4 de CLRS.

Answer 4

La manière la plus simple de le faire est de faire un parcours en profondeur (DFT) du graphe.

Si le graphe a n sommets, cela correspond à un algorithme de complexité temporelle O(n). Comme vous devrez potentiellement faire un DFT en partant de chaque sommet, la complexité totale devient O(n^2).

Vous devez maintenir une pile contenant tous les sommets de la traversée en profondeur actuelle, avec son premier élément étant le nœud racine. Si vous rencontrez un élément qui est déjà dans la pile pendant le DFT, alors vous avez un cycle.

Answer 5

À mon avis, l'algorithme le plus compréhensible pour détecter un cycle dans un graphe dirigé est l'algorithme de coloration de graphe.

Fondamentalement, l'algorithme de coloration de graphe parcourt le graphe de manière DFS (Depth First Search, ce qui signifie qu'il explore un chemin complètement avant d'explorer un autre chemin). Lorsqu'il trouve une arête arrière, il marque le graphe comme contenant une boucle.

Pour une explication approfondie de l'algorithme de coloration de graphe, veuillez lire cet article : http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

De plus, je fournis une implémentation de la coloration de graphe en JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js