graph-theory théorie - Meilleur algorithme pour détecter des cycles dans un graphe orienté





plus machines (13)


Comme vous l'avez dit, vous avez un ensemble d'emplois, il doit être exécuté dans un certain ordre. Topological sort vous donne l'ordre requis pour la planification des travaux (ou pour les problèmes de dépendance s'il s'agit d'un direct acyclic graph ). Exécutez dfs et maintenez une liste, et commencez à ajouter un noeud au début de la liste, et si vous avez rencontré un noeud déjà visité. Ensuite, vous avez trouvé un cycle dans le graphique donné.

Quel est l'algorithme le plus efficace pour détecter tous les cycles dans un graphe orienté?

J'ai un graphique orienté représentant une planification des travaux qui doivent être exécutés, un travail étant un nœud et une dépendance étant un bord. J'ai besoin de détecter le cas d'erreur d'un cycle dans ce graphique menant à des dépendances cycliques.




Étant donné qu'il s'agit d'une liste d'emplois, je soupçonne qu'à un moment donné, vous allez les classer dans un ordre d'exécution proposé.

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

Donc, la question pourrait devenir: «Comment puis-je le plus efficacement tsort», plutôt que «comment puis-je détecter le plus efficacement les boucles». Pour lequel la réponse est probablement "utiliser une bibliothèque", mais à défaut, l'article suivant de Wikipédia:

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

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




Si un graphique satisfait cette propriété

|e| > |v| - 1

alors le graphique contient au moins un cycle.




Si DFS trouve une arête qui pointe vers un sommet déjà visité, vous y avez un cycle.




Commencer avec un DFS: un cycle existe si et seulement si un back-edge est découvert pendant DFS . Ceci est prouvé à la suite du théorème de la voie blanche.




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

Aussi le magicien de la nature dit que nous devons faire O (V ^ 2). Je crois que nous avons seulement besoin de O (V) / O (V + E). Si le graphique est connecté, DFS visitera tous les nœuds. Si le graphe a des sous-graphes connectés, alors chaque fois que nous exécutons un DFS sur un sommet de ce sous-graphe, nous trouverons les sommets connectés et nous n'aurons pas à les considérer pour la prochaine exécution du DFS. Par conséquent, la possibilité de courir pour chaque sommet est incorrecte.




//this is better solution in java- 

`

class Package{
    private List<Package> dep;
    private String name;
    boolean visited;
    List<Package> getDependencies(){
        return this.dep;
    }
    String getName(){}


     public void getBuildOrder(Package p){
         p.visited=true;
         if(p.getDependencies.size()==0) syso(p.getName());
        for( Package p1 : p.getDependencies){
            if(p1.visited) {
                syso("cyclic dependency");
                return;
            }
            getBuildOrder(p1);

        }

    }
     main(){
         Package p = new Package();
         // this p  i having all infor
         getBuildOrder(p);
     }
 }


`



La manière la plus simple de le faire est de faire une première traversée en profondeur (DFT) du graphe .

Si le graphe a n sommets, il s'agit d'un algorithme de complexité temporelle O(n) . Puisque vous devrez éventuellement faire une DFT à partir de chaque sommet, la complexité totale devient O(n^2) .

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




La façon dont je le fais est de faire un tri topologique, en comptant le nombre de sommets visités. Si ce nombre est inférieur au nombre total de sommets dans le groupe de disponibilité de base de données, vous avez un cycle.




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

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

Pour une explication détaillée de l'algorithme de coloration du graphique, veuillez lire cet article: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

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







J'avais implémenté ce problème dans sml (programmation impérative). Voici le contour. Trouver tous les nœuds qui ont soit un indegree ou un outdegree de 0. De tels nœuds ne peuvent pas faire partie d'un cycle (donc supprimez-les). Ensuite, supprimez tous les bords entrants ou sortants de ces nœuds. Appliquez récursivement ce processus au graphique résultant. Si à la fin vous ne vous trouvez avec aucun nœud ou bord, le graphique n'a aucun cycle, sinon il l'a fait.




Que diriez-vous d'une structure d' interval-tree personnalisée? Vous devrez le modifier un petit peu pour définir ce que signifie que deux intervalles se chevauchent dans votre domaine.

Cette question peut vous aider à trouver une implémentation d'arborescence d'intervalle standard en C #.





algorithm graph-theory directed-graph