数据结构java语言描述第（一）篇---图的遍历

图的遍历，所谓遍历，即是对结点的访问。一般有两种访问策略：深度优先遍历，广度优先遍历。

一、深度优先遍历

1、主要思想

首先使用一个未走到过的顶点作为起始顶点，比如V0定点作为起始顶点，沿着V0定点的边访问其他未走到过的定点，首先发现V1(第一个邻接结点)还没有走到过，那么来到V1顶点，再以V1顶点作为起始顶点尝试访问其他未走到过的顶点，以此类推，当发现有一个定点不能访问到其他顶点了，需要回到上一次顶点，按照这个方法，最终遍历完整个图。显然深度优先遍历是沿着图的某一条分支遍历直到末端，然后回溯，再沿着另一条分支进行同样的访问。总结起来可以这样说：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。上图所访问的顺序是：V0–>V1–>V2–>V3–>V4–>V5–>V6–>V7–>V8

2、图的创建

通常图的存储需要用一个二维数组来存储。现在把上面的图创建出来。

            
                public
                
                    class
                    Graph {
                /**
     * 两个顶点之间不可达
     */
                private
                static
                final
                int MAX_WEIGHT=10000;

    /**
     * 顶点数量
     */privateint vertexSize;

    /**
     * 顶点数组
     */privateint []vertexs;

    privateint [][]matrix;

    /**
     * 标记一个定点是否访问过
     */privateboolean []book;


    publicvoidinit(int vertexSize) {
        this.vertexSize = vertexSize;
        this.vertexs=newint[vertexSize];
        this.matrix=newint [vertexSize][vertexSize];
        this.book=newboolean[vertexSize];
        for(int i=0;i<vertexSize;i++){
            vertexs[i]=i;
        }
    }

    publicstatic  Graph createGraph(int pVertexSize){
        Graph graph=new Graph();

        graph.init(pVertexSize);

        int [] a1 = newint[]{0,10,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,11,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
        int [] a2 = newint[]{10,0,18,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,16,MAX_WEIGHT,12};
        int [] a3 = newint[]{MAX_WEIGHT,MAX_WEIGHT,0,22,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,8};
        int [] a4 = newint[]{MAX_WEIGHT,MAX_WEIGHT,22,0,20,MAX_WEIGHT,MAX_WEIGHT,16,21};
        int [] a5 = newint[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,20,0,26,MAX_WEIGHT,7,MAX_WEIGHT};
        int [] a6 = newint[]{11,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,26,0,17,MAX_WEIGHT,MAX_WEIGHT};
        int [] a7 = newint[]{MAX_WEIGHT,16,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,17,0,19,MAX_WEIGHT};
        int [] a8 = newint[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,16,7,MAX_WEIGHT,19,0,MAX_WEIGHT};
        int [] a9 = newint[]{MAX_WEIGHT,12,8,21,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,0};

        graph.matrix[0] = a1;
        graph.matrix[1] = a2;
        graph.matrix[2] = a3;
        graph.matrix[3] = a4;
        graph.matrix[4] = a5;
        graph.matrix[5] = a6;
        graph.matrix[6] = a7;
        graph.matrix[7] = a8;
        graph.matrix[8] = a9;

        return graph;
    }
}
        

3、图的深度优先遍历

在真正遍历之前，要先写两个方法，用来获取某个顶点的第一个邻接点、根据前一个邻接点的下标来取得下一个邻接点

            
                /**
     * 获取某个顶点的第一个邻接点
     * @param pIndex
     * @return
     */
                public
                int
                getFirstNeighbor(int pIndex){
        //顶点pIndex到其他顶点时候可达for(int i=0;i<vertexSize;i++){
            if(matrix[pIndex][i]>0&&matrix[pIndex][i]<MAX_WEIGHT){
                return i;
            }
        }
        return -1;
    }
        

            /**
 * 根据前一个邻接点的下标来取得下一个邻接点
 * @param v 表示要找的顶点
 * @param index  表示该顶点相对于哪个邻接点去获取下一个邻接点
 * @return
 */
public int getNextNeighbor(int v,int index){
    for (int i = index+1; i < vertexSize; i++) {
        if(matrix[v][i]>0&&matrix[v][i]<MAX_WEIGHT){
            return i;
        }   
    }
    return -1;
}

        

            
                /**
     * 深度优先遍历算法
     * @param i
     */
                private
                void
                depthFirstSearch(int i){

        book[i]=true;

        int w = getFirstNeighbor(i);

        while(w!=-1){
            if(!book[w]){
                System.out.println("访问到了"+w+"定点");
                depthFirstSearch(w);
            }
            w=getNextNeighbor(i, w);
        }
    }


    /**
     * 对外公开的深度优先遍历
     */publicvoiddepthFirstSearch(){
        for (int i = 0; i <vertexSize; i++) {
           if(!book[i]){
              System.out.println("访问到了"+i+"顶点");
              depthFirstSearch(i);
           }    
        }   
    }

        

4、测试

            
                public
                static
                void
                main(String[] args) {
        Graph graph=createGraph(9);
        graph.depthFirstSearch();
    }
        

打印结果：
访问到了0顶点
访问到了1定点
访问到了2定点
访问到了3定点
访问到了4定点
访问到了5定点
访问到了6定点
访问到了7定点
访问到了8定点

一、广度优先遍历

类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。

1、主要思想

• 1、访问初始结点v并标记结点v为已访问。
• 2、结点v入队列
• 3、当队列非空时，继续执行，否则算法结束。
• 4、出队列，取得队头结点u。
• 5、查找结点u的第一个邻接结点w。
• 6、若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
  1). 若结点w尚未被访问，则访问结点w并标记为已访问。
  2). 结点w入队列
  3). 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

2、图的广度优先遍历

            
                public
                void
                broadFirstSearch(){
        book = newboolean[vertexSize];
        for(int i =0;i<vertexSize;i++){
            if(!book[i]){
                broadFirstSearch(i);
            }
        }
    }

    /**
     * 实现广度优先遍历
     * @param i
     */privatevoidbroadFirstSearch(int i) {
        int u,w;
        LinkedList<Integer> queue = new LinkedList<Integer>();
        System.out.println("访问到："+i+"顶点");
        book[i] = true;
        queue.add(i);//第一次把v0加到队列while(!queue.isEmpty()){
            u = (Integer)(queue.removeFirst()).intValue();
            w = getFirstNeighbor(u);
            while(w!=-1){
                if(!book[w]){
                    System.out.println("访问到了："+w+"顶点");
                    book[w] = true;
                    queue.add(w);
                }
                w = getNextNeighbor(u, w);
            }
        }
    }

        

4、测试

            
                public
                static
                void
                main(String[] args) {
        Graph graph=createGraph(9);
        graph.broadFirstSearch();
    }
        

打印结果：
访问到了：0顶点
访问到了：1顶点
访问到了：5顶点
访问到了：2顶点
访问到了：6顶点
访问到了：8顶点
访问到了：4顶点
访问到了：3顶点
访问到了：7顶点