鄰接鏈接列表週期檢測 - Java

Question

我有一些問題，檢查我的鄰接列表是否有周期。 我想做一個函數，檢查我的鄰接表是否有至少存在一個循環。

基於我的程序。首先，我必須輸入根節點，然後輸入許多節點，圖中的節點，邊的數量以及表示邊的邊的鄰接表。鄰接列表中的每個條目都包含一對節點。

樣品輸入：

Root node: "A" 
Number of nodes: 3 
Vertices/Nodes: 
A 
B 
C 
Number of edges: 3 
A 
B 
B 
C 
C 
A 

A --> B 
B --> C 
C --> A 

上面的示例輸入具有周期：A - >乙 - 「ç - >甲] 欲輸出是否具有是否循環。

這是我的計劃至今：

import java.util.Scanner; 

class Neighbor { 
public int vertexNum; 
public Neighbor next; 
public Neighbor(int vnum, Neighbor nbr) { 
     this.vertexNum = vnum; 
     next = nbr; 
    } 
} 

class Vertex { 
String name; 
Neighbor adjList; 
Vertex(String name, Neighbor neighbors) { 
     this.name = name; 
     this.adjList = neighbors; 
    } 
} 

public class DirectedCycle { 

Vertex[] adjLists; 

public DirectedCycle() { 

    Scanner sc = new Scanner(System.in); 
    //Root Node 
    System.out.print("Root node: "); 
    String rn = sc.nextLine(); 

    //Number of nodes 
    System.out.print("Number of vertices/nodes: "); 
    int nodes = sc.nextInt(); 
    adjLists = new Vertex[nodes]; 

    //List of nodes 
    System.out.println("Vertices:"); 
    for (int v=0; v < adjLists.length; v++) { 
     String letter = sc.next(); 
     adjLists[v] = new Vertex(letter, null); 
    } 
    //Number of edges 
    System.out.print("Number of edges: "); 
    int edges = sc.nextInt(); 
    System.out.println("<v1> <v2>"); 
    for(int i=0; i<edges; i++) { 

     int v1 = indexForName(sc.next()); 
     int v2 = indexForName(sc.next()); 

     adjLists[v1].adjList = new Neighbor(v2, adjLists[v1].adjList); 
    } 
} 

int indexForName(String name) { 
    for (int v=0; v < adjLists.length; v++) { 
     if (adjLists[v].name.equals(name)) { 
      return v; 
     } 
    } 
    return -1; 
} 

public void print() { 

    System.out.println(); 
    for (int v=0; v < adjLists.length; v++) { 
     System.out.print(adjLists[v].name); 
     for (Neighbor nbr=adjLists[v].adjList; nbr != null; nbr=nbr.next) { 
      String name = adjLists[nbr.vertexNum].name; 
      System.out.print(" --> " + name); 
     } 
     System.out.println("\n"); 
    } 
} 

public static void main(String[] args) { 
    DirectedCycle graph = new DirectedCycle(); 
    graph.print(); 
    } 
} 

我上面程序目前尚不具備，檢查週期，也是我想要實現的根節點的事情的功能。如果任何人都可以提高我上面的程序只是回答我，給我一些我可以信賴的代碼。謝謝！ （我是初學者！）

Answer 1

要檢查一個鏈表的循環，你需要使用兩個不同的指針進行迭代，一個遍歷列表的兩倍。如果有一個循環，它將最終使用這種方法進行檢測。另外，對於結束條件，您可以檢查是否已訪問過所有節點，如果是，則不存在循環。

Answer 2

在Floyd's Cycle detection algo.中檢測循環的最有效方法，它基本上是在鏈表上移動兩個指針，一個以正常的速度慢速移動一個指針，另一個以慢速指針的兩倍速度移動，即快速指針。

Java代碼相同。

boolean detectloop(Node list) { 
 
    if(list == null) 
 
     return false; 
 
    Node slow, fast; 
 
    slow = fast = list; 
 
    while(true) { 
 
     slow = slow.next;   
 
     if(fast.next != null) 
 
      fast = fast.next.next; 
 
     else 
 
      return false; 
 
     if(slow == null || fast == null) 
 
      return false; 
 
     if(slow == fast) 
 
      return true; 
 
    } 
 
}