使用BFS

Question

我的問題找到兩個節點之間的所有路徑是有點怪，但我有這個項目的學校，我需要找到兩個節點之間的所有路徑，並將它們保存在列表中。奇怪的部分是我必須以BFS順序遍歷圖形。我知道，有可能被更eficientlly用於我的問題，其他的算法，但我必須使用BFS。我將該圖表示爲一個鄰接矩陣，它是被稱重和無向的。任何人都可以幫助我一些想法請。

public class A { 
    private static int[][] adjacency = new int [5][5]; 
    static int n = 5; 

    public static void main(String[] args) { 
     for (int i=0;i<n;i++) 
      for (int j=0;j<n;j++) 
       adjacency[i][j] = 0;  
     adjacency[0][1] = 2; 
     adjacency[0][3] = 1; 
     adjacency[1][0] = 2; 
     adjacency[1][2] = 5; 
     adjacency[2][1] = 5; 
     adjacency[2][3] = 1; 
     adjacency[2][4] = 2; 
     adjacency[3][0] = 1; 
     adjacency[3][2] = 1; 
     adjacency[4][2] = 2; 

     List<Queue<Integer>> paths = findPath(0,2,adjacency); 
     System.out.println(paths); 
    } 

    public static List<Integer> getNeighbors(int node, int[][] a) { 
     List<Integer> list = new ArrayList<Integer>(); 
     for(int i=0;i<n;i++) 
      if (a[node][i] != 0) 
       list.add(i); 
     return list; 
    } 

    public static List<Queue<Integer>> findPath(int start, int end, int[][] a) { 
     List<Queue<Integer>> paths = new ArrayList<Queue<Integer>>(); 
     Queue<Integer> toVisit = new LinkedList<Integer>(); 
     Queue<Integer> visited = new LinkedList<Integer>(); 
     toVisit.add(start); 
     while(!toVisit.isEmpty()) { 
       int node = toVisit.remove(); 
       visited.add(node); 
       List<Integer> neighbors = new ArrayList<Integer>(); 
       neighbors = getNeighbors(node,a); 
     } 
      return paths; 
    } 
} 

Answer 1

public class GraphStructure { 
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); 
} 
} 

public class BFSImplementation{ 

public static int count; 
public static Hashtable hash; 
private static final String START = "B"; 
private static final String END = "E"; 

public BFSImplementation() { 
    hash=new Hashtable(); 
    count=0; 
} 
public static void main(String[] args) { 

    GraphStructure graph = new GraphStructure(); 

    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 BFSImplementation().breadthFirst(graph, visited); 
    }  
    public static void breadthFirst(GraphStructure graph, LinkedList<String> visited) { 
    LinkedList<String> nodes = graph.adjacentNodes(visited.getLast()); 

    for (String node : nodes) { 
     if (visited.contains(node)) { 
      continue; 
     } 
     if (node.equals(END)) { 
      count++; 
      visited.add(node); 
      printPath(count,visited); 
      visited.removeLast(); 
      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(); 
    } 
    } 
    public static void printPath(int count,LinkedList<String> visited) {  
    String temp=""; 
    for (String node : visited) { 
     temp=temp+node+",";    
     // System.out.print(node); 
     // System.out.print(" "); 
    } 
    System.out.println(); 
    System.out.println("Available Path "+count+": : : :"+ temp);  
    hash.put(count,temp); 
    //System.out.println("exp = " + hash.toString());  
    } 
    }