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

Commencez par un DFS : un cycle existe si et seulement si une arête arrière est découverte pendant le DFS. Cela est prouvé grâce au théorème du chemin blanc.

Answer 2

Si vous ne pouvez pas ajouter une propriété "visited" aux nœuds, utilisez un ensemble (ou une map) et ajoutez simplement tous les nœuds visités à l'ensemble sauf s'ils sont déjà dans l'ensemble. Utilisez une clé unique ou l'adresse des objets comme "clé".

Cela vous donne également des informations sur le nœud "racine" de la dépendance cyclique ce qui sera utile lorsque l'utilisateur devra résoudre le problème.

Une autre solution est d'essayer de trouver la prochaine dépendance à exécuter. Pour cela, vous devez avoir une pile où vous pouvez vous souvenir de où vous êtes maintenant et de ce que vous devez faire ensuite. Vérifiez si une dépendance est déjà sur cette pile avant de l'exécuter. Si c'est le cas, vous avez trouvé un cycle.

Alors que cela peut sembler avoir une complexité de O(N*M), vous devez vous rappeler que la pile a une profondeur très limitée (donc N est petit) et que M devient plus petit à chaque dépendance que vous pouvez cocher comme "exécutée" en plus vous pouvez arrêter la recherche lorsque vous trouvez une feuille (donc vous n'avez jamais à vérifier chaque nœud -> M sera également petit).

Dans MetaMake, j'ai créé le graphe comme une liste de listes puis j'ai supprimé chaque nœud au fur et à mesure que je les exécutais ce qui a naturellement réduit le volume de recherche. Je n'ai jamais eu besoin d'exécuter une vérification indépendante, tout s'est passé automatiquement pendant l'exécution normale.

Si vous avez besoin d'un mode "test uniquement", ajoutez simplement un indicateur "dry-run" qui désactive l'exécution des tâches réelles.