我的BFS遞歸調用不停止

我有以下代碼來查找開始和結束節點之間的所有路徑。我的BFS遞歸調用不停止

Graph.java

import java.util.HashMap; 
import java.util.LinkedHashSet; 
import java.util.LinkedList; 
import java.util.Map; 
import java.util.Set; 

public class Graph { 
private Map<String, LinkedHashSet<String>> map = new HashMap(); 

public void addEdge(String node1, String node2) { 
    LinkedHashSet<String> adjacent = map.get(node1); 
    if(adjacent==null) { 
     adjacent = new LinkedHashSet(); 
     map.put(node1, adjacent); 
    } 
    adjacent.add(node2); 
} 

public void addTwoWayVertex(String node1, String node2) { 
    addEdge(node1, node2); 
    addEdge(node2, node1); 
} 

public boolean isConnected(String node1, String node2) { 
    Set adjacent = map.get(node1); 
    if(adjacent==null) { 
     return false; 
    } 
    return adjacent.contains(node2); 
} 

public LinkedList<String> adjacentNodes(String last) { 
    LinkedHashSet<String> adjacent = map.get(last); 
    if(adjacent==null) { 
     return new LinkedList(); 
    } 
    return new LinkedList<String>(adjacent); 
}

}

和 Search.java

import java.util.LinkedList; 

public class Search { 

private static final String START = "D"; 
private static final String END = "E"; 

public static void main(String[] args) { 
    // this graph is directional 
    Graph graph = new Graph(); 
    graph.addEdge("A", "B"); 
    graph.addEdge("A", "C"); 
    graph.addEdge("B", "A"); 
    graph.addEdge("B", "D"); 
    graph.addEdge("B", "E"); // this is the only one-way connection 
    graph.addEdge("B", "F"); 
    graph.addEdge("C", "A"); 
    graph.addEdge("C", "E"); 
    graph.addEdge("C", "F"); 
    graph.addEdge("D", "B"); 
    graph.addEdge("E", "C"); 
    graph.addEdge("E", "F"); 
    graph.addEdge("F", "B"); 
    graph.addEdge("F", "C"); 
    graph.addEdge("F", "E"); 
    LinkedList<String> visited = new LinkedList(); 
    visited.add(START); 
    new Search().breadthFirst(graph, visited); 
} 

private void breadthFirst(Graph graph, LinkedList<String> visited) { 
    LinkedList<String> nodes = graph.adjacentNodes(visited.getLast()); 
    // examine adjacent nodes 
    for (String node : nodes) { 
     if (visited.contains(node)) { 
      continue; 
     } 
     if (node.equals(END)) { 
      visited.add(node); 
      printPath(visited); 
      visited.removeLast(); 
      return ; 
      //break; 
     } 
    } 
    // in breadth-first, recursion needs to come after visiting adjacent nodes 
    for (String node : nodes) { 
     if (visited.contains(node) || node.equals(END)) { 
      continue; 
     } 
     visited.addLast(node); 
     breadthFirst(graph, visited); 
     visited.removeLast(); 
    } 
} 

private void printPath(LinkedList<String> visited) { 
    for (String node : visited) { 
     System.out.print(node); 
     System.out.print(" "); 
    } 
    System.out.println(); 
} 
}

我想找到兩個節點之間的第一路徑後停止遞歸調用。 break語句之前的返回語句工作正常，但如果我添加許多無向邊，它不會停止打印兩個節點之間的所有路徑。

來源

2013-04-05 Hemant Singh

您的問題是？ – 2013-04-05 06:01:57