图论—深度优先和广度优先算法源码

最近由于项目需要，需要实现深度优先和广度优先算法，图论中的基础内容，源代码共享一下，希望对大家有用：

public class Graph {
	private final int MAX_VERT=500;
	private Node nodelist[];
	private int adjMat[][];
	private int nverts;
	private Stack theStack;
	private Queue theQuene;
	
	public Graph(){
		//顶点数组
		nodelist=new Node[MAX_VERT];
		//邻接矩阵
		adjMat = new int[MAX_VERT][MAX_VERT];
		nverts=0;
		for(int i=0;i<MAX_VERT;i++){
			for(int j=0;j<MAX_VERT;j++){
				adjMat[i][j]=0;
			}
		}
		theStack=new Stack();
		theQuene=new LinkedList();
		sortedArray = new BusSiteBean[MAX_VERT];
	}
	
	/**
	 * 增加一定点
	 * @param node
	 */
	public void addNode(Node node){
		nodelist[nverts++]=node;
	}
	
	/**
	 * 增加一边
	 * @param start
	 * @param end
	 */
	public void addEdge(int start,int end){
		adjMat[start][end]=1;
		//有向图
		//adjMat[end][start]=1;
	}
	
	public int getAdjUnVisited(int v){
		for(int j=0;j<nverts;j++){
			if(adjMat[v][j]==1&&nodelist[j].isWasVisited()==false){
				return j;
			}
		}
		return -1;
	}
	
	/**
	 * 深度优先搜索算法
	 */
	public void dfs(){
		nodelist[0].setWasVisited(true);
		displayNode(0);
		theStack.push(0);
		while(!theStack.isEmpty()){
			int v=((Integer)theStack.peek()).intValue();
			v=getAdjUnVisited(v);
			
			if(v==-1){
				theStack.pop();
			}else{
				nodelist[v].setWasVisited(true);
				displayNode(v);
				theStack.push(v);
			}
		}
		for(int j=0;j<nverts;j++){
			nodelist[j].setWasVisited(false);
		}
	}
	
	/**
	 * 广度优先搜索算法
	 */
	public void bfs(){
		this.nodelist[0].setWasVisited(true);
		this.displayNode(0);
		this.theQuene.add(0);
		int v2;
		while(!this.theQuene.isEmpty()){
			int v1=((Integer)this.theQuene.remove()).intValue();
			while((v2=this.getAdjUnVisited(v1))!=-1){
				this.nodelist[v2].setWasVisited(true);
				displayNode(v2);
				this.theQuene.add(v2);
			}
		}
		for(int j=0;j<nverts;j++){
			nodelist[j].setWasVisited(false);
		}		
	}
	
	private int noSuccessors(){
		boolean isEdge;
		for(int row=0;row<this.nverts;row++){
			isEdge=false;
			for(int col=0;col<this.nverts;col++){
				if(adjMat[row][col]>0){
					isEdge=true;
					break;
				}
			}
			if(!isEdge)
				return row;
		}
		return -1;
	}
	
	/**
	 * 有向图拓扑
	 */
	public void poto(){
		int orig_nverts=this.nverts;
		while(this.nverts>0){
			int currentNode=noSuccessors();
			if(currentNode==-1){
				System.out.println("Graph 有环");
				return;
			}
			sortedArray[this.nverts-1]=nodelist[currentNode].getBs();
			deleteNode(currentNode);
		}
		for(int j=0;j<orig_nverts;j++){
			System.out.print(sortedArray[j]);
		}
	}
	
	private void deleteNode(int delVert){
		if(delVert!=this.nverts-1){
			for(int j=delVert;j<this.nverts-1;j++)
				this.nodelist[j]=this.nodelist[j+1];
			for(int row=delVert;row<this.nverts-1;row++)
				moveRowUp(row,this.nverts);
			for(int col=delVert;col<this.nverts-1;col++)
				moveRowLeft(col,this.nverts-1);
		}
		this.nverts--;		
	}
	private void moveRowUp(int row,int length){
		for(int col=0;col<length;col++)
			adjMat[row][col]=adjMat[row+1][col];
	}
	
	private void moveRowLeft(int col,int length){
		for(int row=0;row<length;row++)
			adjMat[row][col]=adjMat[row][col+1];	
	}

	public void displayNode(int v){
		System.out.println(nodelist[v].getBs().toString());
	}
	
	public static void main(String[] args) {
		Graph g=new Graph();
		g.addNode(new Node(new BusSiteBean("A")));
		g.addNode(new Node(new BusSiteBean("B")));
		g.addNode(new Node(new BusSiteBean("C")));
		g.addNode(new Node(new BusSiteBean("D")));
		g.addNode(new Node(new BusSiteBean("E")));
		g.addNode(new Node(new BusSiteBean("F")));
		g.addNode(new Node(new BusSiteBean("G")));
		g.addNode(new Node(new BusSiteBean("H")));
		
		g.addEdge(0, 3);
		g.addEdge(0, 4);
		g.addEdge(1, 4);
		g.addEdge(2, 5);
		g.addEdge(3, 6);
		g.addEdge(4, 6);
		g.addEdge(5, 7);
		g.addEdge(6, 7);
		
		g.poto();
	}
}

 

评论

3 楼 kongshanxuelin 2008-10-07  

wuxuping 写道

你好 你是宁波的吗

是的

2 楼 wuxuping 2008-10-06  

你好 你是宁波的吗

1 楼 Element&lina 2008-10-06  

还不错，谢谢分享