この記事では、Java ベースのグラフの幅優先走査アルゴリズムの実装方法を例の形式で説明します。
隣接行列を使用してグラフ メソッドを保存します。
1. グラフの頂点と辺の数を決定します。
2. 入力された頂点情報は 1 次元配列の頂点に格納されます
3. 隣接行列を初期化します。
4. 各エッジを順番に入力し、隣接行列の円弧に保存します。
エッジにアタッチされた 2 つの頂点のシリアル番号 i と j を入力します。
隣接行列の i 行 j 列の要素値を 1 に設定します。
隣接行列の j 行 i 列の要素値を 1 に設定します。
幅優先トラバーサルの実装:
1. キューQを初期化する
2. 頂点 v を訪問; 頂点 v をキュー Q に追加します。
3.while (キュー Q は空ではありません)
v= キュー Q の先頭要素がデキューされます。
w = 頂点 v の最初に隣接する点
while(w が存在する)
w が訪問されていない場合、訪問頂点 w はキュー Q に入れられます。
w=頂点 v の次に隣接する点
実装コードは次のとおりです。
package com.teradata.lsw.sort;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;public class BFS {//ストレージ ノード情報 private Object[] vertices;//ストレージエッジ情報配列 private int[][] arcs;//エッジ数 private int vexnum;// i 番目のノードが訪問されたかどうかを記録します private boolean[] Visited;// 移動されたノードを保存するための一時的なリンク リストを構築します private List<Object> temp = new ArrayList<Object>();/*** @param args* * @author TD_LSW*/public static void main(String[] args) {// TODO 自動生成メソッド stubBFS g = new BFS(8);Character[] vertices = { 'A'、'B'、'C'、'D'、'E'、'F'、'G'、'H' };g.addVertex(頂点);g.addEdge(0, 1);g .addEdge(0, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(3, 5);g.addEdge(4, 5);g.addEdge(2, 6);g.addEdge(2, 7);System.out.println("グラフの幅優先走査:");g.bfs();}//幅-最初のトラバーサル実装 private void bfs() {// TODO 自動生成メソッド stubfor (int i = 0; i < vexnum; i++) {visited[i] = false;}Queue<Integer> q = new LinkedList<Integer>();for (int i = 0; i < vexnum; i++) {if (!visited[i]) {visited[i] = true;visit(i );q.add(i);while (!q.isEmpty()) {int j = (整数) q.remove().intValue();//全ての走査が完了していればループする必要がないと判断 if (temp.size() == vexnum) {q.removeAll(q);return;}for ( int k = this .firstAdjVex(j); k >= 0; k = this.nextAdjVex(j, k)) {if (!visited[k]) {q.add(k);visited[k] = true;visit(k);}}}}}}// 次のノードを検索 public int firstAdjVex(int i) {for (int j = 0; j < vexnum ; j++) {if (arcs[i][j] > 0)return j;}return -1;}public int nextAdjVex(int i, int k) {for (int j = k + 1; j < vexnum; j++) {if (arcs[i][j] > 0)return j;}return -1;}//グラフのエッジを初期化 private void addEdge(int i, int j) {/ / TODO 自動生成メソッド stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}//グラフのノードを初期化します private void addVertex(Object[] object) {// TODO 自動生成メソッド stubthis.vertices = object;}// グラフを初期化します public BFS(int n) {// TODO 自動生成コンストラクター stubvexnum = n ;頂点 = new Object[n];arcs = new int[n][n];visited = new boolean[n];for (int i = 0; i < vexnum; i++) {for (int j = 0; j < vexnum; j++) {arcs[i][j] = 0;}}}private void visit(int i) {// TODO 自動生成メソッド stubtemp .add(頂点[i]);System.out.print(頂点[i] + " ");}}