[数据结构与算法]图的深度优先遍历与广度优先遍历

思路

深度优先

1：访问初始顶点v,并设置为已访问
2：获取节点v的邻接节点 w
3：如果 w存在，则向下继续执行，否则结束算法
4：如果节点w没有访问过，对w进行DFS
5：获取节点v的下一个邻接节点，回到 步骤3

     private void DFS(boolean[] isVisited, int v){
         int w;//用来存储顶点v的邻接节点
         //访问初始顶点，并设置为已访问
         System.out.print(getVertexByIndex(v)+"->");
         isVisited[v] = true;
         //获取第一个邻接顶点
         w = getFirstNeighbor(v);
         while(w != -1){ //检测顶点v的所有邻接顶点
             if(!isVisited[w]){ //如果 w 未访问过
                 DFS(isVisited,w); //进行深度遍历
             }
             // 顶点 w 遍历过
             w = getNextNeighbor(v,w);//对下一个邻接节点进行访问
         }
     }

    /**
     * 对整个图进行深度遍历
     */
    public void DFS(){
         isVisited = new boolean[getNumOfVertexes()];
         for (int i = 0; i < getNumOfVertexes(); i++) {
             if(!isVisited[i]){
                 DFS(isVisited,i);
             }
         }
        System.out.println();
     }

广度优先

需要一个队列用来保持访问的顺序

1：访问初始节点v,并将v设置为已访问
2：将v加入队列
3：如果队列不为空，向下执行，否则结束算法
4：获取队头元素u
5：获取u邻接节点w
6：如果w为空，则返回步骤3，如果不为空则进行以下操作
   6.1：访问w,并将w设置为已访问
   6.2：将v入队
   6.3：获取v的下一个邻接节点，返回 步骤6

  private void BFS(boolean[] isVisited,int v){
         int u;//存放出队节点
         int w;//存放u的邻接节点
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.print(getVertexByIndex(v)+"=>\t");
        isVisited[v] = true;

        queue.addLast(v);

        while(!queue.isEmpty()){
            u = queue.removeFirst();
            w = getFirstNeighbor(u);
            while (w != -1){
                if(!isVisited[w]){
                    System.out.print(getVertexByIndex(w)+"=>\t");
                    isVisited[w] = true;
                    queue.addLast(w);
                    w = getNextNeighbor(u,w);
                }//如果已经被访问过了
                w = getNextNeighbor(u,w);
            }
        }
     }

    /**
     * 对整个图进行广度遍历
     */
    public void BFS(){
        isVisited = new boolean[getNumOfVertexes()];
         for (int i = 0; i < getNumOfVertexes(); i++) {
             if(!isVisited[i]){
                 BFS(isVisited,i);
             }
         }
        System.out.println();
    }

测试代码

class Graph{
    private ArrayList<String> vertexes; //顶点集
    private int[][] edges;      //存储改图的邻接矩阵
    private int  numOfEdges;    //边的数量
    private  boolean[] isVisited ;//标记节点是否别访问过的数组

    /**
     *  构造器，初始化图的节点集
     */
    public Graph(int n) {
        this.vertexes = new ArrayList<String>();
        edges = new int[n][n];
        numOfEdges = 0;
    }

    /**
     * 添加边
     * @param v1 顶点1
     * @param v2 顶点2
     * @param weight 边v1-v2的权值
     */
    public void  insertEdge(int v1,int v2, int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    /**
     * 添加顶点
     * @param vertex
     */
    public void insertVertex(String vertex){
        vertexes.add(vertex);
    }

    /**
     * 获取顶点数
     * @return 该图的顶点数目
     */
    public int getNumOfVertexes(){
        return  vertexes.size();
    }

    /**
     *  获取边的数目
     * @return 该图的边的数目
     */
    public int getNumOfEdges() {
        return numOfEdges;
    }

    /**
     * 获取节点的下标（值）
     * @param index
     * @return
     */
    public  String  getVertexByIndex(int index){
        return  vertexes.get(index);
    }

    /**
     * 获取边v1-v2的权值
     * @param v1 顶点v1
     * @param v2 顶点v2
     * @return v1-v2的权值
     */
    public int getWeight(int v1,int v2){
        return  edges[v1][v2];
    }

    /**
     * 打印改图的邻接矩阵
     */
    public void showGraph(){
        for (int[] row: edges) {
            for (int edg: row) {
                System.out.printf("%d\t",edg);
            }
            System.out.println();
        }
    }

    /**
     *  获取节点v的邻接节点
     * @param v 顶点v的下标值
     * @return  返回-1说明不存在邻接节点，反之为顶点v的第一个邻接节点的下标值
     */
    public int  getFirstNeighbor(int v){
        for (int i = 0; i < numOfEdges; i++) {
            if(edges[v][i] != 0){
                return  i;
            }
        }
        return -1;
    }

    /**
     *  获取顶点v1的继邻接节点v2之后的下一个邻接节点
     * @param v1 顶点v1
     * @param v2 顶点v1的邻接顶点v2
     * @return 返回-1说明不存在下一个邻接节点，反之为连接这两个顶点的权值
     */
    public int getNextNeighbor(int v1,int v2){
        for (int i = v2 + 1; i < numOfEdges; i++) {
            if(edges[v1][i] != 0){
                return i;
            }
        }
        return  -1;
    }

    /**
     * 针对单节点的深度优先（DFS）
     * 1.访问初始顶点v，并设置为已访问
     * 2.获取初始顶点v的邻接顶点w，
     * 3.如果w存在，对w进行DFS，如果w不存在，将v顶点的下一个顶点设为初始节点，重新执行1，2，3步
     * 4.查找节点v的继w邻接节点的下一个邻接节点，然后执行3
     * @param isVisited 记录每个节点是否访问过的数组
     * @param v 初始节点
     */
     private void DFS(boolean[] isVisited, int v){
         int w;//用来存储顶点v的邻接节点
         //访问初始顶点，并设置为已访问
         System.out.print(getVertexByIndex(v)+"->");
         isVisited[v] = true;
         //获取第一个邻接顶点
         w = getFirstNeighbor(v);
         while(w != -1){ //检测顶点v的所有邻接顶点
             if(!isVisited[w]){ //如果 w 未访问过
                 DFS(isVisited,w); //进行深度遍历
             }
             // 顶点 w 遍历过
             w = getNextNeighbor(v,w);//对下一个邻接节点进行访问
         }
     }

    /**
     * 对整个图进行深度遍历
     */
    public void DFS(){
         isVisited = new boolean[getNumOfVertexes()];
         for (int i = 0; i < getNumOfVertexes(); i++) {
             if(!isVisited[i]){
                 DFS(isVisited,i);
             }
         }
        System.out.println();
     }

    /**
     * 对单个顶点的广度优先(BFS)  需要一个队列以保持访问过的节点的顺序
     * 1.访问初始顶点v,并标记为已访问
     * 2.将节点v入队
     * 3.当队列不为空时，取得队头节点u,并继续向下执行，反之为空时结束算法
     * 4.查找u的第一个邻接节点w
     * 5.判断w节点是否存在，如果w节点不存在，跳到第三步，如果w存在则执行下三个步骤
     *  5.1 如果顶点w未被访问，则访问顶点w，并标记为已访问
     *  5.2 节点 w入队
     *  5.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤5。
     * @param isVisited 标记各顶点是否被访问的数组
     * @param v 初始顶点
     */
    private void BFS(boolean[] isVisited,int v){
         int u;//存放出队节点
         int w;//存放u的邻接节点
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.print(getVertexByIndex(v)+"=>\t");
        isVisited[v] = true;

        queue.addLast(v);

        while(!queue.isEmpty()){
            u = queue.removeFirst();
            w = getFirstNeighbor(u);
            while (w != -1){
                if(!isVisited[w]){
                    System.out.print(getVertexByIndex(w)+"=>\t");
                    isVisited[w] = true;
                    queue.addLast(w);
                    w = getNextNeighbor(u,w);
                }//如果已经被访问过了
                w = getNextNeighbor(u,w);
            }
        }
     }

    /**
     * 对整个图进行广度遍历
     */
    public void BFS(){
        isVisited = new boolean[getNumOfVertexes()];
         for (int i = 0; i < getNumOfVertexes(); i++) {
             if(!isVisited[i]){
                 BFS(isVisited,i);
             }
         }
        System.out.println();
    }
}