Wie erkennt man eine Zirkelreferenz in einem Baum?

Question

Ich habe eine Node-Klasse wie folgt:

public class Node{ 
    Object data; 
    List<Node> children; 
} 

Ich brauche diesen Baum in der Post, um zu durchqueren, und ich bin mit Guava TreeTraverser für für das gleiche.

TreeTraverser<Node> treeTraverser = new TreeTraverser<Node>() { 
       @Override 
       public Iterable<Node> children(Node node) { 
        return node.children; 
       } 
      }; 

treeTraverser.postOrderTraversal(node); 

Der Haken ist, dass die Chancen, dass die gegebene Baum zirkuläre Abhängigkeiten haben könnte (Mittel könnte es sich um ein zyklisches Graph). Was wäre ein effizienter Weg, um zirkuläre Abhängigkeiten zu erkennen?

Answer 1

Per Definition ist ein Baum ein acyclic verbundener Graph. Daher gibt es keinen Baum mit zirkulären Abhängigkeiten.

Sie können Zyklen in einem Diagramm finden, indem Sie die Tiefe zuerst anwenden und nach Knoten suchen, die den Weg nach unten gefunden haben. Wenn Sie einen Knoten besuchen, den Sie während vorheriger Schritte von DFS gesehen haben, ist das Diagramm nicht ein Baum.

Siehe Q&A für erweiterte Zyklusdetektionsalgorithmen.

Answer 2

In einfachen Worten Tree is a non cyclic data structure und wenn es Zyklen gibt, dann wird es ein Graph.

Oben ist ein Beispiel eines Graphen. Sie können es mit Adjazenzliste oder Adjazenzmatrix darstellen. Sie können sich auf http://krishnalearnings.blogspot.in/2015/11/basics-of-graph-in-computer-science.html für Grundlagen von Graphen beziehen.

In dem Bild oben können wir es wie folgt darstellen (In Ihrer Frage haben Sie eine Art der Darstellung der Adjazenzliste verwendet).

int[][] graph = { {0,1,0,0,0,0}, 
        {0,0,1,0,0,0}, 
        {0,0,0,1,1,0}, 
        {0,0,0,0,0,0}, 
        {0,0,0,0,0,1}, 
        {0,1,0,0,0,0}, 
       }; 

1 steht für eine Kante vom entsprechenden nummerierten Scheitelpunkt bis zum nummerierten Scheitelpunkt.

Wir können eine einfache Methode schreiben, um das Vorhandensein eines Zyklus zu erkennen und einen beliebigen Zyklus im Graphen zu drucken.

static int[] cycleElements; 
static int cycleElementIndex = 0; 
static boolean cycleFound = false; 
static final int NEW = 0; 
static final int PUSHED = 1; 
static final int POPPED = 2; 
public static int findCycle(int[][] graph,int N, int u, int[] states){ 
    for(int v = 0; v < N; v++){ 
     if(graph[u][v] == 1){ 
      if(states[v] == PUSHED){ 
       // cycle found 
       cycleFound = true; 
       return v; 
      }else if(states[v] == NEW){ 
       states[v] = PUSHED; 
       int poppedVertex = findCycle(graph, N, v, states); 
       states[v] = POPPED; 
       if(cycleFound){ 
        if(poppedVertex == u){ 
         cycleElements[cycleElementIndex++] = v; 
         cycleElements[cycleElementIndex++] = u; 
         cycleFound = false; 
        }else{ 
         cycleElements[cycleElementIndex++] = v; 
         return poppedVertex; 
        } 
       } 
      } 
     } 
    } 
    return -1; 
} 
public static void main(String[] args) { 
    int N = 6; 
    int[][] graph = { {0,1,0,0,0,0}, 
         {0,0,1,0,0,0}, 
         {0,0,0,1,1,0}, 
         {0,0,0,0,0,0}, 
         {0,0,0,0,0,1}, 
         {0,1,0,0,0,0}, 
        }; 
    cycleElements = new int[N]; 
    int[] states = new int[N]; 
    states[0] = PUSHED; 
    findCycle(graph,N,0,states); 
    for(int i = 0; i < cycleElementIndex; i++){ 
     System.out.println(cycleElements[i]); 
    } 
} 

Sie oben Ansatz Adjazenzliste leicht umwandeln können, wenn Sie wollen, obwohl Darstellung nicht viel tut (nur Liste adjacency Ihren Raum zu Adjazenzmatrix im Vergleich sparen kann) tritt