邻接链接列表周期检测 - Java

我有一些问题，检查我的邻接列表是否有周期。我想做一个函数，检查我的邻接表是否有至少存在一个循环。邻接链接列表周期检测 - Java

基于我的程序。首先，我必须输入根节点，然后输入许多节点，图中的节点，边的数量以及表示边的边的邻接表。邻接列表中的每个条目都包含一对节点。

样品输入：

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

我上面程序目前尚不具备，检查周期，也是我想要实现的根节点的事情的功能。如果任何人都可以提高我上面的程序只是回答我，给我一些我可以信赖的代码。谢谢！（我是初学者！）

来源

2015-01-06 aldrich19

你做得很好！这不是一个人们为你编写代码的网站，所以你可能会遇到一些社区消极情绪。祝你好运！ –

http://stackoverflow.com/questions/2663115/how-to-detect-a-loop-in-a-linked-list –

要检查一个链表的循环，你需要使用两个不同的指针进行迭代，一个遍历列表的两倍。如果有一个循环，它将最终使用这种方法进行检测。另外，对于结束条件，您可以检查是否已访问过所有节点，如果是，则不存在循环。

来源

2015-01-06 04:48:56 holtc

在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; 
 
    } 
 
}

来源

2015-01-06 05:10:51 Odin

邻接链接列表周期检测 - Java

回答

相关问题