Java完成應用廣度優先遍歷(BFS)盤算最短途徑的辦法

Java完成應用廣度優先遍歷(BFS)盤算最短途徑的辦法。本站提示廣大學習愛好者：（Java完成應用廣度優先遍歷(BFS)盤算最短途徑的辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是Java完成應用廣度優先遍歷(BFS)盤算最短途徑的辦法正文

本文實例講述了Java完成應用廣度優先遍歷(BFS)盤算最短途徑的辦法。分享給年夜家供年夜家參考。詳細剖析以下：

我們用字符串代表圖的極點(vertax)，來模仿黉捨中Classroom, Square, Toilet, Canteen, South Gate, North Gate幾個所在，然後盤算隨意率性兩點之間的最短途徑。

以下圖所示：

如，我想從North Gate去Canteen, 法式的輸入成果應為：

BFS: From [North Gate] to [Canteen]:
North Gate
Square
Canteen

起首界說一個算法接口Algorithm:

public interface Algorithm {
  /**
   * 履行算法
   */
  void perform(Graph g, String sourceVertex);
  /**
   * 獲得途徑
   */
  Map<String, String> getPath();
}

然後，界說圖:

/**
 * (無向)圖
 */
public class Graph {
  // 圖的終點
  private String firstVertax;
  // 鄰接表
  private Map<String, List<String>> adj = new HashMap<>();
  // 遍歷算法
  private Algorithm algorithm;
  public Graph(Algorithm algorithm) {
    this.algorithm = algorithm;
  }
  /**
   * 履行算法
   */
  public void done() {
    algorithm.perform(this, firstVertax);
  }
  /**
   * 獲得從終點到{@code vertex}點的最短途徑
   * @param vertex
   * @return
   */
  public Stack<String> findPathTo(String vertex) {
    Stack<String> stack = new Stack<>();
    stack.add(vertex);
    Map<String, String> path = algorithm.getPath();
    for (String location = path.get(vertex) ; false == location.equals(firstVertax) ; location = path.get(location)) {
      stack.push(location);
    }
    stack.push(firstVertax);
    return stack;
  }
  /**
   * 添加一條邊
   */
  public void addEdge(String fromVertex, String toVertex) {
    if (firstVertax == null) {
      firstVertax = fromVertex;
    }
    adj.get(fromVertex).add(toVertex);
    adj.get(toVertex).add(fromVertex);
  }
  /**
   * 添加一個極點
   */
  public void addVertex(String vertex) {
    adj.put(vertex, new ArrayList<>());
  }
  public Map<String, List<String>> getAdj() {
    return adj;
  }
}

這裡我們應用戰略設計形式，將算法與Graph類分別，經由過程在結構Graph對象時傳入一個Algorithm接口的完成來為Graph選擇遍歷算法。

public Graph(Algorithm algorithm) {
    this.algorithm = algorithm;
  }

無向圖的存儲構造為鄰接表，這裡用一個Map表現鄰接表，map的key是黉捨所在(String)，value是一個與該所在相連通的所在表(List<String>)。

// 鄰接表
  private Map<String, List<String>> adj = new HashMap<>();

然後，編寫Algorithm接口的BFS完成：

/**
 * 封裝BFS算法
 */
public class BroadFristSearchAlgorithm implements Algorithm {
  // 保留曾經拜訪過的所在
  private List<String> visitedVertex;
  // 保留最短途徑
  private Map<String, String> path;
  @Override
  public void perform(Graph g, String sourceVertex) {
    if (null == visitedVertex) {
      visitedVertex = new ArrayList<>();
    }
    if (null == path) {
      path = new HashMap<>();
    }
    BFS(g, sourceVertex);
  }
  @Override
  public Map<String, String> getPath() {
    return path;
  }
  private void BFS(Graph g, String sourceVertex) {
    Queue<String> queue = new LinkedList<>();
    // 標志終點
    visitedVertex.add(sourceVertex);
    // 終點出列
    queue.add(sourceVertex);
    while (false == queue.isEmpty()) {
      String ver = queue.poll();
      List<String> toBeVisitedVertex = g.getAdj().get(ver);
      for (String v : toBeVisitedVertex) {
        if (false == visitedVertex.contains(v)) {
          visitedVertex.add(v);
          path.put(v, ver);
          queue.add(v);
        }
      }
    }
  }
}

個中，path是Map類型，意為從 value 到 key 的一條途徑。

BFS算法描寫：

1. 將終點標志為已拜訪並放入隊列。
2. 從隊列中掏出一個極點，獲得與該極點相通的一切極點。
3. 遍歷這些極點，先斷定極點能否已被拜訪過，假如否，標志該點為已拜訪，記載以後途徑，並將以後極點出列。
4. 反復2、3，直到隊列為空。

測試用例：

String[] vertex = {"North Gate", "South Gate", "Classroom", "Square", "Toilet", "Canteen"};
  Edge[] edges = {
      new Edge("North Gate", "Classroom"),
      new Edge("North Gate", "Square"),
      new Edge("Classroom", "Toilet"),
      new Edge("Square", "Toilet"),
      new Edge("Square", "Canteen"),
      new Edge("Toilet", "South Gate"),
      new Edge("Toilet", "South Gate"),
  };
@Test
  public void testBFS() {
    Graph g = new Graph(new BroadFristSearchAlgorithm());
    addVertex(g);
    addEdge(g);
    g.done();
    Stack<String> result = g.findPathTo("Canteen");
    System.out.println("BFS: From [North Gate] to [Canteen]:");
    while (!result.isEmpty()) {
      System.out.println(result.pop());
    }
  }

願望本文所述對年夜家的java法式設計有所贊助。