Java实现图：邻接矩阵表示、深度优先搜索、广度优先搜索、无向图的最小生成树

程序中用到的栈和队列实现请参见另外的博文。

package test2;

class Vertex{
	private char vertexName;
	public boolean wasVisited;
	
	public Vertex(char name){
		vertexName = name;
		wasVisited = false;
	}
	public void displayVertexName(){
		System.out.println(" name:"+vertexName);
	}
}
public class Graph {
	private int MAX_VERTEX;
	private Vertex[] vertexList;
	private Stack stack;
	private queue que;
	private int adjMatrix[][];
	private int nVertex;
	
	public Graph(int max){
		MAX_VERTEX = max;
		vertexList = new Vertex[MAX_VERTEX];
		stack = new Stack(MAX_VERTEX);//深度遍历使用
		que = new queue(MAX_VERTEX);//广度遍历使用
		adjMatrix = new int[MAX_VERTEX][MAX_VERTEX];
		nVertex = 0;
		for(int i = 0; i < MAX_VERTEX; i++){
			for(int j = 0; j< MAX_VERTEX ; j++){
				adjMatrix[i][j] = 0;
			}
		}
		
	}
	public boolean addVertex(char name){
		if(nVertex < MAX_VERTEX){
			vertexList[nVertex++] = new Vertex(name);;
			return true;
		}
		else{
			return false;
		}
	}
	public boolean addEdge(int startVertex, int endVertex){
		if(startVertex < nVertex && endVertex < nVertex){
			adjMatrix[startVertex][endVertex] = 1;
			adjMatrix[endVertex][startVertex] = 1;
			return true;
		}else{
			return false;
		}
	}
	public int getUnvisitedVertex(int j){//获取与该顶点邻接的未访问顶点
		for(int i = 0; i < nVertex ; i++){
			if(adjMatrix[j][i] == 1 && vertexList[i].wasVisited == false){//可达，又未被访问过
				return i;
			}
		}
		return -1;
	}
	<span style="color:#FF0000;">public void depthFirstSearch(){</span>
		stack.push(0);//首先将第0个元素入栈；
		//vertexList[0].displayVertexName();<span style="color:#FF0000;">//******若要输出该图的最小生成树，则删掉这行代码；</span>
		vertexList[0].wasVisited = true;//标识为已访问
		while(!stack.isEmpty()){//若栈不空
			int unvisitedVer = getUnvisitedVertex(stack.getTopValue());//获取一个与该顶点邻接的未访问顶点
			if(unvisitedVer != -1){ //存在与这个点相连的未访问顶点；
				vertexList[stack.getTopValue()].displayVertexName();<span style="color:#FF0000;">//******若要输出该图的最小生成树，则加上这行代码；</span>
				vertexList[unvisitedVer].displayVertexName();//访问它，并标识为已访问
				vertexList[unvisitedVer].wasVisited = true;
				System.out.println(" ");
				stack.push(unvisitedVer);//入栈
			}else{//与该顶点相连的所有顶点均被访问过，将该顶点出栈；
				stack.pop();
			}
		}//
		for(int i = 0; i< nVertex; i++){//重置顶点均未被访问过，保证下次遍历能进行。
			vertexList[i].wasVisited = false;
		}
	}
	<span style="color:#FF0000;">public void breadthFirstSearch(){</span>
		que.insert(0);
		vertexList[0].displayVertexName();
		vertexList[0].wasVisited = true;
		while(!que.isEmpty()){
			int unvisit = getUnvisitedVertex(que.getFrontElement());
			if(unvisit != -1){
				vertexList[unvisit].displayVertexName();
				vertexList[unvisit].wasVisited = true;
				que.insert(unvisit);
			}else{
				que.remove();
			}
		}
		for(int i=0; i< nVertex ; i++){
			vertexList[i].wasVisited = false;
		}
	}
}
class GraphApp{
	public static void main(String args[]){
		Graph g = new Graph(9);
		g.addVertex('A');
		g.addVertex('B');
		g.addVertex('C');
		g.addVertex('D');
		g.addVertex('E');
		g.addVertex('F');
		
		g.addEdge(0, 1);
		g.addEdge(1, 2);
		//g.addEdge(2, 3);
		g.addEdge(3, 4);
		g.addEdge(4, 5);
		g.addEdge(1, 4);
		g.addEdge(1, 5);
		g.addEdge(3, 5);
		
		//g.breadthFirstSearch();
		g.depthFirstSearch();
	}
}

最小生成树运行结果：

 name:A
 name:B
 
 name:B
 name:C
 
 name:B
 name:E
 
 name:E
 name:D
 
 name:D
 name:F