0

node の開始と終了の間のすべてのパスを見つけるための次のコードがあります。

グラフ.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();
}
}

2 つのノード間の最初のパスを見つけた後、再帰呼び出しを停止したいと考えています。break ステートメントの前の return ステートメントは正常に機能しますが、多くの無向エッジを追加すると、2 つのノード間のすべてのパスの出力が停止しません。

4

1 に答える 1

0

BFS では、ノードに「色」を付けて、既にアクセスしたかどうかを確認する必要があります。

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm

進行状況を追跡するために、幅優先探索で各頂点に色を付けます。グラフの各頂点は、次の 3 つの状態のいずれかになります。

  1. 未発見;
  2. 発見されましたが、完全には調査されていません。と
  3. 完全に調査しました。

頂点 u の状態は、次のように色変数に格納されます。

  1. color[u] = White - 「未発見」状態の場合、
  2. color [u] = 灰色 - 「発見されたが完全には調査されていない」状態、および
  3. color [u] = 黒 - 「完全に探索された」状態。
于 2013-04-05T06:02:16.487 に答える