JAva実現dfs及びbfsアルゴリズム

dfs(深さ優先探索アルゴリズム)は主にスタック方式で実現され,主な規則は

初期頂点を選択し、可能であれば(存在する場合)、その頂点の隣接する頂点にアクセスし、マークし、スタックに入れます.

最初のステップが実行できない場合(元の頂点にはアクセスされていない隣接する頂点は存在しません)、スタックが空でない場合、スタックから頂点がポップアップされます.

は、第1のステップ、第2のステップをループし、スタックが空の場合、検索プロセス全体が完了する.

bfs(広さ優先探索アルゴリズム)は主にキューによって実現され、その主なルールは:

は、開始点のすべての隣接点を巡回し、マーク、エンキューする.

すべての隣接点がエンキューされた後、すなわちマークされていない隣接点が存在しない場合、キューヘッダから頂点を1つ取り、現在の頂点とする.最初のステップ、2番目のステップを繰り返します.

キューが空であるため、第2のステップを実行できないまで、検索は終了する.

スタックの操作クラス:

//---------------------    
class stackX{
	private final int size = 20;
	private int[] st;
	private int top;
	
	public stackX(){
		st = new int[size];
		top = -1;
	}
	
	public void push(int i){
		st[++top] = i;
	}
	
	public int pop(){
		return st[top--];
	}
	
	public int peek(){
		return st[top];
	}
	
	public boolean isEmpty(){
		return (top==-1);
	}
}

 キュー操作クラス:

//---------------     
class Queue{
	private final int size = 20;
	private int[] queArray;
	private int front;
	private int rear;
	
	public Queue(){
		queArray = new int[size];
		front = 0;
		rear = -1;
	}
	
	public void insert(int i){
		if(rear == size-1)
			rear = -1;
		queArray[++rear] = i;
	}
	
	public int remove(){
		int temp = queArray[front++];
		if(front==size)
			front = 0;
		return temp;
	}
	
	public boolean isEmpty(){
		return (rear+1==front || front+size-1==rear);
	}	
}//end class Queue

 【dfs、bfs】具体的な実装コード:
図クラス(bfs、dfsアルゴリズムを含む)

//---------------------   
class Vertex{
	public char label;//        
	public boolean wasVisited;//          
	
	public Vertex(char lab){
		label = lab;
		wasVisited = false;//       -     
	}
}

class Graph{
	private final int max_verts = 20;//     
	private Vertex vertexList[];//    --Vertex 
	private int adjMat[][];//    
	private int nVerts;//vertexList[]  ，      
	private stackX theStack;//  dfs       
	
	public Graph(){
		vertexList = new Vertex[max_verts];
		adjMat = new int [max_verts][max_verts];
		nVerts = 0;// 0  
		for(int j=0; j

 
テストクラス:

public class Main{
	public static void main(String[] args){
		Graph theGraph = new Graph();
		theGraph.addVertex('A');
		theGraph.addVertex('B');
		theGraph.addVertex('C');
		theGraph.addVertex('D');
		theGraph.addVertex('E');
		
		theGraph.addEdge(0, 1);
		theGraph.addEdge(1, 2);
		theGraph.addEdge(0, 3);
		theGraph.addEdge(3, 4);
		
		System.out.print("Visits: ");
		theGraph.dfs();
		System.out.println();
	}//end main;
}//end class Main