Meilleur algorithme pour la détection de cycles dans un graphe orienté

Étant donné que c'est un calendrier des travaux, je pense qu'à un certain moment vous allez sorte dans un projet d'ordonnance d'exécution.

Si c'est le cas, alors un tri topologique la mise en œuvre pourrait, en tout cas, de détecter les cycles. UNIX tsort n'est certainement. Je pense qu'il est probable que c'est par conséquent plus efficace pour détecter les cycles en même temps que tsorting, plutôt que dans une étape distincte.

Donc, la question pourrait devenir, "comment puis-je la plus efficace de l'ordre de tsort", plutôt que "comment puis-je la plus efficace de détecter les boucles". La réponse est probablement "l'utilisation d'une bibliothèque", mais à défaut, à la suite de l'article de Wikipedia:

http://en.wikipedia.org/wiki/Topological_sorting

a le pseudo-code d'un algorithme, et une brève description de l'autre à partir de Tarjan. Les deux ont O(|V| + |E|) temps de la complexité.

La façon la plus simple de le faire est de faire un parcours en profondeur d'abord la traversée (DFT) du graphe.

Si le graphe a n sommets, c'est un O(n) complexité temporelle de l'algorithme. Depuis que vous avez à faire une DFT à partir de chaque sommet, de la complexité devient O(n^2).

Vous devez maintenir un pile contenant tous les sommets de la profondeur actuelle première traversée de, avec son premier élément du nœud racine. Si vous tombez sur un élément qui est déjà dans la pile lors de la DFT, alors vous avez un cycle.

Si vous ne pouvez pas ajouter un "visité" la propriété pour les nœuds, l'utilisation d'un ensemble (ou une carte) et ajoutez tous les nœuds visités à l'ensemble, sauf s'ils sont déjà dans le jeu. L'utilisation d'une clé unique ou de l'adresse des objets comme la "clé".

Cela vous donne aussi l'information sur la "racine" nœud de la dépendance cyclique qui va venir dans maniable quand un utilisateur doit résoudre le problème.

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

Même si cela peut sembler avoir une complexité de O(N*M) vous devez vous rappeler que la pile a une très faible profondeur (si N est petit) et que M est plus petit avec chaque dépendance que vous pouvez cocher que "exécuté" de plus, vous pouvez arrêter la recherche lorsque vous avez trouvé une feuille (de sorte que vous jamais vérifier chaque noeud -> M sera petite, trop).

Dans MetaMake, j'ai créé le graphique, sous forme d'une liste de listes, puis supprimés chaque nœud comme je l'ai exécuté qui, naturellement, de couper le volume de recherche. Je n'ai jamais vraiment eu à exécuter un contrôle indépendant, tout s'est fait automatiquement lors de l'exécution normale.

Si vous avez besoin d'un "test " seulement" mode, il suffit d'ajouter un "dry-run" drapeau qui désactive l'exécution de l'emploi.

D'après le Lemme 22.11 de Cormen et coll., Introduction aux Algorithmes (PLC):

Un graphe orienté G est acyclique si et seulement si la profondeur d'abord la recherche de G ne donne aucun retour bords.

Cela a été mentionné dans plusieurs réponses, là je vais également fournir un exemple de code basé sur le chapitre 22 des PLC. L'exemple de graphique est illustrée ci-dessous.

CLR " pseudo-code pour depth-first search lit:

Dans l'exemple de la CLR de la Figure 22.4, le graphique se compose de deux DFS arbres: l'un composé de nœuds u, v, x, et y, et l'autre de nœuds w et z. Chaque arbre contient un bord arrière: l'un de x à v et l'autre à partir de z à z (une auto-loop).

La clé de la réalisation, c'est que le bord est rencontré lorsque, dans le DFS-VISIT fonction, lors de l'itération sur les voisins v de u, un nœud est rencontré avec le GRAY couleur.

Le code Python suivant est une adaptation des PLC' pseudo avec un if clause 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])
        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]:
        # Detect cycles
        if v in discovered:
            print(f"Cycle detected: found a back edge from {u} to {v}.")

        # Recurse into DFS tree
        if v not in discovered and 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)

Notez que dans cet exemple, le time en CLRS' pseudo n'est pas capturé, parce que nous sommes uniquement intéressés à la détection de cycles. Il y a aussi du code réutilisable pour la construction de la représentation des listes d'adjacence d'un graphe à partir d'une liste d'arêtes.

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

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

Ce sont exactement les bords arrières dans l'exemple de la CLR de la Figure 22.4.

Si DFS trouve un avantage à un déjà-sommet visité, vous avez un cycle.

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length J'aime cette solution la meilleure spécialement pour les 4 longueur:)

Aussi phys assistant, dit-u doivent faire O(V^2). Je crois que nous avons besoin seulement O(V)/O(V+E).
Si le graphe est connecté, alors DFS va visiter tous les nœuds. Si le graphique est connecté sous graphes à chaque fois que nous organisons un DFS sur un sommet de ce sous-graphe, nous allons trouver les connectés des sommets et que vous n'avez pas à tenir compte de ces pour la prochaine course de la DFS. Par conséquent, la possibilité de courir pour chaque sommet est incorrect.

Si un graphe satisfaire cette propriété

|e| > |v| - 1

alors le graphe contient au moins sur le cycle.