数据结构与算法15 – 图

深度优先遍历代码
写法1

    //得到第一个邻接点的小标 - 找到返回W的小标，未找到返回-1 - 下一个小标的结点
    public int getFirstNeigbor(int index) {

        for(int j = 0; j <vertexs.size(); j++) {
            if(edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }
    
    
    //根据前一个邻结点的小标来获取一个邻接点- 找到返回新的W的小标，未找到返回-1
    public int getNextNeigbor(int index, int w) {

        for(int j = w+1; j<vertexs.size(); j++ ) {
            if(edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }
    

    //深度优先遍历
    public void dfs(boolean[] isVisited, int i) {

        System.out.println(vertexs.get(i));

        isVisited[i] = true;

        int w = getFirstNeigbor(i);

        while(w != -1) {
            if(!isVisited[w]) {
                dfs(isVisited, w);
            }

            w = getNextNeigbor(i, w);
        }
    }
    
    
    //重载深度优先算法
    public void dfs() {

        for(int i = 0; i<getVertexsNum(); i++) {

            //如果未访问过，则从该结点开始访问
            if(isVisable[i] == false) {
                dfs(i);
            }
        }
        
        //遍历完后修改回原来的状态
        for(int i = 0; i < isVisable.length; i++) {
            isVisable[i] = false;
        }        

    }

写法2

    //得到下一个邻接结点 - 寻找当前结点未被访问的邻接结点
    public int getNextNeigbor2(int index) {


        for(int j = 0; j<isVisable.length; j++) {

            if(edges[index][j] > 0 && isVisable[j] == false) {
                return j;
            }
        }
        return -1;

    }    
    
    
    //深度优先遍历2
    public void dfs2(int i) {

        System.out.println(vertexs.get(i));

        isVisable[i] = true;

        int w = getNextNeigbor2(i);

        while(w != -1) {
             dfs2(w);
            w = getNextNeigbor2(i);
        }
    }    
    
    //重载深度优先算法
    public void dfs2() {
           //图可能存在没有变得结点 - 故需要遍历所有结点
        for(int i = 0; i<getVertexsNum(); i++) {
            //如果未访问过，则从该结点开始访问
            if(isVisable[i] == false) {
                dfs2(i);
            }
        }
        
        //遍历完后修改回原来的状态
        for(int i = 0; i < isVisable.length; i++) {
            isVisable[i] = false;
        }

    }

测试

public static void main(String[] args) {

        //1， 结点信息
        String[] vertexs = {"v1", "v2", "v3", "v4"};
        Integer n = vertexs.length;

        // 2. 创建带5个结点的无序带权图
        UndirectedWeightGraph graph = new UndirectedWeightGraph(n);

        // 3. 添加结点
        for (String vertex : vertexs) {
            graph.insertVertex(vertex);
        }

        // 4. 添加结点之间的权值 - 这里的权值1仅表示两结点之间有连接关系
        graph.insertWeight(0, 1, 1);
        graph.insertWeight(0, 2, 1);
        graph.insertWeight(1, 2, 1);
        graph.insertWeight(1, 3, 1);


        // 5. 显示图的矩阵
        //System.out.println(graph.getGraph());
        graph.showGrpah();

        graph.dfs2();

}

流程讲解

1. 首先dfs2( 0 )  打印V1

2. 寻找与V1相邻并且未访问过的邻结点   找到V2即 1

3. 进入递归     dfs(1)   打印V2

4. 寻找与V2相邻并且未访问过的邻结点   找到V3即 2

5. 进入递归     dfs(2)   打印V3

6. 寻找与V3相邻并且未访问过的邻结点   未找到  退出dfs(2)这个递归  返回到dfs(1)这个递归

7. 寻找与V2相邻并且未访问过的邻结点   找到V4即 3

8. 进入递归     dfs(3)   打印V4

9. 寻找与V4相邻并且未访问过的邻结点   未找到  退出dfs(3)这个递归  返回到dfs(1)这个递归

10. 寻找与V2相邻并且未访问过的邻结点  未找到  退出dfs(1)这个递归  返回到dfs(0)这个递归

11. 寻找与V1相邻并且未访问过的邻结点   未找到   退出dfs(0)    结束函数

2.1.2.2 广度优先遍历（BFS）- 分层搜索

BFS思想：从队列弹出的结点为基准，访问该结点的所有未被访问的邻结节点，并将其放入队列中。如果该弹出的结点所有邻接结点被访问完，则从队列弹出一个结点，重复前者动作

    
    //得到下一个邻接结点
    public int getNextNeigbor2(int index) {


        for (int j = 0; j < isVisable.length; j++) {

            if (edges[index][j] > 0 && isVisable[j] == false) {
                return j;
            }
        }
        return -1;

    }    
    
    public void bfs(int i) {

        // 创建队列
        LinkedList<Integer> queue = new LinkedList();

        //将i入队
        queue.addLast(i);

        //从队列中获取头结点
        int u = queue.removeFirst();
        // 打印并输出结点信息
        System.out.println(this.getVertexByIndex(i));
        isVisable[u] = true;


        //以弹出结点读出所有该结点的邻接结点
        while(true) {
            
            //获取u的未被访问的邻接结点
            int w = getNextNeigbor2(u);
            if(w != -1) {
                //打印邻接结点并将其放入队列中，并标记已经被访问
                System.out.println(getVertexByIndex(w));
                isVisable[w] = true;
                queue.addLast(w);
                //如果当前结点已经遍历过所有其邻接结点，则从队列中弹出一个结点，并访问该结点所有邻接结点
            }else {
                // 如果队列无元素可弹，结束循环
                if(queue.size() == 0) {
                    break;
                }
                u = queue.removeFirst();
            }
        }





    }

    //重载广度优先遍历
    public void bfs() {

        //所有结点必须遍历 - 因为存在没有边的结点
       for(int i = 0; i < getVertexsNum(); i++) {

            if( isVisable[i] == false) {
                bfs(i);
            }

        }

        //恢复遍历前的状态
        for(int i = 0; i < isVisable.length; i++) {
            isVisable[i] = false;
        }
    }

2.1.2.3 案例讲解

#深度优先遍历DFS
1 -> 2 -> 4 -> 8 -> 5 -> 3 -> 6 -> 7

#广度优先遍历BFS
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

小半

0 0

生成海报 微信扫码分享