図-広さ優先ループ

ここでの図の広さ優先遍歴アルゴリズムはキューを用いて実現した.
図の深さ遍歴の原則:
1可能であれば、すべての接続された未アクセスのノードにアクセスし、タグを付け、キューに入れます.
2ルール1が実行できない場合、ペアが空でない場合は、キューからヘッダ要素がポップアップされます.ルール1の再実行
3ルール1とルール2が実行できない場合は、ループが完了します.
コード内の図はGraphグラフ隣接行列法で表され、その他の表現はGraphグラフ隣接表法を参照してください.
コード中のQueueは,アクセスしたノードを記述するための補助構造である.キューの詳細については、Queueチーム2LinkedQueueチームを参照してください.
Vertexは、アクセス、アクセスするかどうか、アクセスフラグをクリアする方法を含む図のノードを表します.
Graph.main:簡単なテストを提供します.コードは、指定した下付きノードから広さ優先ループを開始できます.
Graphを除いてコードは簡単です.bsf(int i)広さ優先遍歴アルゴリズムの外にはあまり注釈がない.

class Queue {
	private int[] values;
	private int begin = -1;
	private int end = -1;
	Queue(int size) {
		values = new int[size];
	}
	void push(int value) { values[++begin] = value; }
	int pop() { return values[++end]; }
	boolean isEmpty() { return begin == end; }
}

class Vertex {
	private Object value;
	private boolean isVisited;
	Vertex(Object value) {
		this.value = value;
	}

	void visit() { isVisited = true; print(); }
	void clean() {	isVisited = false; }
	boolean isVisited() { return isVisited; }
	void print() { System.out.println(value); }
}

class Graph {
	private Vertex[] vertexs;
	private int[][] adjMat;
	private int pos = -1;

	Graph(int size) {
		vertexs = new Vertex[size];
		adjMat = new int[size][size];
	}

	void add(Object value) {
		assert pos < vertexs.length;
		vertexs[++pos] = new Vertex(value);
	}

	void connect(int from, int to) {
		adjMat[from][to] = 1;
		adjMat[to][from] = 1;
	}

	void disConnect(int from, int to) {
		adjMat[from][to] = 0;
		adjMat[to][from] = 0;
	}

	int findNeighbor(int index) {
		for(int i=0; i<=pos; i++) {
			if(adjMat[index][i] == 1 && !vertexs[i].isVisited()) return i;
		}
		return -1;
	}

	void bsf(int index) {	//                
		if(vertexs[index] == null) return;	//            ，   
		Queue q = new Queue(vertexs.length);	//            
		vertexs[index].visit(); //      
		q.push(index);	//        
		while(!q.isEmpty()) {	//           
			index = q.pop();	//    
			int i; 
			while((i=findNeighbor(index)) != -1) {	//            
				vertexs[i].visit();	//          
				q.push(i);	//     
			} 
		} 
	}

	void clean() { for(Vertex v: vertexs) if(v != null)v.clean(); }

	public static void main(String[] args) {
		Graph g = new Graph(20);
		g.add('a');
		g.add('b');
		g.add('c');
		g.add('d');
		g.add('e');
		g.connect(0,1);
		g.connect(1,2);
		g.connect(0,3);
		g.connect(3,4);
		g.bsf(0);
	}
}