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

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

 

Java代码

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