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

李家酒馆酒保

发布于 2017-12-28 10:53:58

1.4K0

发布于 2017-12-28 10:53:58

文章被收录于专栏：李家的小酒馆

深度优先遍历

图的深度优先遍历类似于树的先序遍历，首先通过一个指定的节点开始遍历，然后访问第一个邻接点，然后切换到这个节点判断是否是否有邻接点，如果有，判断是否被访问过，如果没有被访问过，则访问这个节点，切换到这个节点重复上面的操作，如果没有，会返回上一个节点进行判断。直到所有的节点都访问完成。

因为需要保证一个节点只能访问一次，所以我们需要一个Tag数组，这个数组为boolean型，因为节点都是存储在一个一维数组中，所以我们可以得到节点数组的下标去获取对应标记数组中的值来判断这个节点是否被访问过。

在邻接表中，先去判断这个节点的第一个邻接点，切换到邻接点，然后再去判断这个邻接点的第一个邻接点，如果没有，则会去上一层去判断下一个邻接点（如果有的话）知道所有节点都被遍历完成。

如下图的邻接表

首先从A开始访问，然后第一个邻接点为B，切换到B节点，B节点的第一个节点为A，A已经访问完成，所以会返回B，B也会返回A，A就会继续遍历下一个邻接点，即C，最后遍历结果为A-B-D-C-E

代码：

public class DFS {
    boolean tag[];

    public void dfsTraverse(AlGraph alGraph) {
        VNode[] list = alGraph.getNodeList();
        tag = new boolean[list.length];

        for (int i = 0; i < list.length; i++) {
            if (!tag[i]) {
                dfs(alGraph, i);
            }
        }
        System.out.println();
    }

    public void dfs(AlGraph alGraph, int v) {
        tag[v] = true;
        VNode[] list = alGraph.getNodeList();
        System.out.print(list[v].getData() + "  ");
        ArcNode arc = list[v].getFirstArc();
        while (arc != null) {
            if (!tag[arc.getAdjVex()])
                dfs(alGraph, arc.getAdjVex());
            arc = arc.getNextArc();
        }
    }

}

广度优先遍历

图的广度优先遍历类似于数的层次遍历，首先选定一个节点，然后把这个节点的邻接点全部访问，然后再判断下一个节点是否存在邻接点，同时这个邻接点没有被访问，遍历这个节点的所有邻接点，依次循环直到所有节点都被遍历完毕。

同时广度遍历也需要一个标志数组来判断节点是否被访问，标志数组的原理和深度优先遍历相同。

上图的邻接表进行广度优先遍历的时候，借助了队列来实现，先访问A然后访问A的同时会将BC入队，访问完了A以后会访问B，此时，也会将B的邻接点入队，余下节点依次访问，如果节点访问过则不访问，结果为A-B-C-D-E这样就实现了表的广度优先遍历。

代码

public class BreadthSearch {
    boolean tag[];

    public void bfs(AlGraph alGraph) {
        LinkedList<VNode> q = new LinkedList<>();
        VNode[] list = alGraph.getNodeList();
        tag = new boolean[list.length];

        for (int i = 0; i < tag.length; i++) {
            // 广度遍历
            if (!tag[i]) {
                tag[i] = true;
                VNode n = new VNode();
                q.add(list[i]);

                while (!q.isEmpty()) {
                    n = q.poll();
                    System.out.print(n.getData()+"  ");
                    ArcNode arc = n.getFirstArc();
                    while (arc != null) {
                        if (!tag[arc.getAdjVex()]) {
                            tag[arc.getAdjVex()] = true;
                            q.add(list[arc.getAdjVex()]);
                        }
                        arc = arc.getNextArc();
                    }
                }
            }
        }
        System.out.println();

    }

}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-11-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度