Как обнаружить круглую ссылку в дереве?

Question

У меня есть класс Node следующим образом:

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

Мне нужно, чтобы пройти это дерево в почтовом порядке, и я использую Guava TreeTraverser для того же.

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

treeTraverser.postOrderTraversal(node); 

Улов в том, что существует вероятность того, что данное дерево может иметь круговые зависимости (означает, что это может быть циклический граф). Что было бы эффективным способом обнаружения круговых зависимостей?

Answer 1

По определению дерево - это связанный граф acyclic. Поэтому нет такой вещи, как дерево с круговыми зависимостями.

Вы можете найти циклы в графике, применяя обход глубины и поиск узлов, которые были посещены вниз. Если вы посещаете узел, который вы видели во время предыдущих шагов DFS, график равен , а не дерево.

См. Это Q&A для алгоритмов расширенного цикла обнаружения.

Answer 2

Простыми словами Tree is a non cyclic data structure, и когда есть циклы, это становится Graph.

Выше приведено пример графика. Вы можете представить его с помощью списка Adjacency или матрицы смежности. Вы можете обратиться к http://krishnalearnings.blogspot.in/2015/11/basics-of-graph-in-computer-science.html за основы графов.

На картинке выше мы можем представить ее ниже (В вашем вопросе вы использовали вид списка смежности).

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 представляет собой край от соответствующей строки с нумерованной вершиной до нумерованной колонки.

Мы можем написать простой способ обнаружения присутствия цикла и распечатать любой график на графике.

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]); 
    } 
} 

Вы можете легко преобразовать выше подход к списку смежности, если вы хотите, хотя представление не имеет большое значение (только список смежности может сэкономить пространство по сравнению с матрицей смежности)