この記事の例では、Java が幅優先トラバーサル (BFS) を実装して最短パスを計算する方法について説明します。皆さんの参考に共有してください。具体的な分析は次のとおりです。
文字列を使用してグラフの頂点を表し、学校内の教室、広場、トイレ、食堂、南門、北門の位置をシミュレートし、任意の 2 点間の最短経路を計算します。
以下に示すように:
たとえば、北門から食堂に行きたい場合、プログラムの出力は次のようになります。
BFS：【北門】から【食堂】：北門広場食堂
まず、アルゴリズム インターフェイス アルゴリズムを定義します。
public Interface Algorithm { /** * アルゴリズムを実行*/ void Perform(Graph g, String sourceVertex) /** * パスを取得*/ Map<String, String> getPath();}次に、グラフを定義します。
/** * (無向)graph*/public class Graph { // グラフの開始点 private String firstVertax; // 隣接リスト private Map<String, List<String>> adj = new HashMap<>(); / / トラバーサル アルゴリズム private Algorithm アルゴリズム; public Graph(Algorithm アルゴリズム) { this.algorithm = アルゴリズム; } /** * アルゴリズムを実行します*/ public void doned() { Algorithm アルゴリズム (this, firstVertax); } /** * 開始点から {@code vertex} 点までの最短パスを取得します * @param vertex * @return */ public Stack<String> findPathTo(String vertex) { Stack<String> stack = new Stack< >() ; stack.add(vertex); Map<String, String> パス = Algorithm.getPath(); for (String location = path.get(vertex) ; false == location.equals(firstVertax) ; location = path.get(location)) { stack.push(location); } stack.push(firstVertax) } /** * エッジを追加します*/ public void addEdge(String fromVertex, String toVertex); if (firstVertax == null) { firstVertax = fromVertex; } adj.get(fromVertex).add(toVertex); } /** * 頂点を追加します*/ public void addVertex(String vertex) { adj.put(vertex, new ArrayList<>()) } public Map<String, List<String>> getAdj() { return adj; }}ここでは、戦略的デザイン パターンを使用してアルゴリズムを Graph クラスから分離し、Graph オブジェクトの構築時に Algorithm インターフェイスの実装を渡すことによって Graph のトラバーサル アルゴリズムを選択します。
public Graph(アルゴリズム アルゴリズム) { this.algorithm = アルゴリズム }無向グラフの格納構造は隣接リストです。ここでは、マップのキーは学校の場所 (String) で、値は場所のリスト (List<String>) です。場所に接続されています。
// 隣接リスト private Map<String, List<String>> adj = new HashMap<>();
次に、アルゴリズム インターフェイスの BFS 実装を作成します。
/** * BFS アルゴリズムをカプセル化します*/public class BroadFristSearchAlgorithm はアルゴリズムを実装します { // 訪問した場所を保存します 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<>(); // 開始点をマークします VisitVertex.add(sourceVertex) // 開始点をキューに入れます queue.add(sourceVertex); queue.isEmpty()) { String ver = queue.poll(); List<String> toBeVisitedVertex = g.getAdj().get(ver); for (String v : toBeVisitedVertex) { if (false == VisitedVertex.contains() v)) { 訪問済みVertex.add(v); } } }}このうちパスはMap型で、値からキーまでのパスを意味します。
BFS アルゴリズムの説明:
1. オリジンを訪問済みとしてマークし、キューに入れます。
2. キューから頂点を取得し、その頂点に接続されているすべての頂点を取得します。
3. これらの頂点をトラバースし、まず頂点が訪問済みかどうかを判断し、訪問済みでない場合はその点を訪問済みとしてマークし、現在のパスを記録し、現在の頂点をキューに入れます。
4. キューが空になるまでステップ 2 と 3 を繰り返します。
テストケース:
String[] vertex = {"北門", "南門", "教室", "広場", "トイレ", "食堂"}; Edge[]edges = { new Edge("北門", "教室" )、新しい Edge("北門"、"広場")、新しい Edge("教室"、"トイレ")、新しい Edge("広場"、"トイレ")、新しい Edge("広場"、 "食堂"), new Edge("トイレ", "南門"), new Edge("トイレ", "南門"), };@Test public void testBFS() { Graph g = new Graph(new BroadFristSearchAlgorithm( )); addVertex(g); g.done() 結果 = g.findPathTo("Canteen"); System.out.println("BFS: [北ゲート] から [食堂]:"); while (!result.isEmpty()) { System.out.println(result.pop());この記事が皆さんの Java プログラミングに役立つことを願っています。