欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的深度优先遍历与广度优先遍历

程序员文章站 2022-05-21 23:22:07
...

思路

深度优先

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