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

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

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();}}

? 1 楼 Element&lina 2008-10-06 还不错，谢谢分享 2 楼 wuxuping 2008-10-06 你好 你是宁波的吗 3 楼 kongshanxuelin 2008-10-07 wuxuping 写道
你好 你是宁波的吗

是的