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

深度优先遍历

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

因为需要保证一个节点只能访问一次,所以我们需要一个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();

    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发与安全

数据结构:静态链表

首先我们让数组的元素都是由两个数据域组成,data和cur。也就是说,数组的每一个下标都对应一个data和一个cur。 数据域data用来存放数据元素,也就是通...

1956
来自专栏开发与安全

数据结构:线性表之顺序存储结构

线性表的数据对象集合为 {a1,a2,....an},每个元素的类型均为Datatype。其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后...

1738
来自专栏阮一峰的网络日志

Ramda 函数库参考教程

学习函数式编程的过程中,我接触到了 Ramda.js。 我发现,这是一个很重要的库,提供了许多有用的方法,每个 JavaScript 程序员都应该掌握这个工具。...

3816
来自专栏安恒网络空间安全讲武堂

堆栈基础(一)

1126
来自专栏Flutter入门

Kotlin中的函数

函数还可以用中缀表示法调用,当他们是成员函数或扩展函数,只有一个参数,用 infix关键字标注

884
来自专栏Albert陈凯

2018-06-13 关于Java集合的小抄

1223
来自专栏一个会写诗的程序员的博客

编译器中的 逃逸分析

在这个例子中,一共举了3种常见的指针逃逸场景。分别是 全局变量赋值,方法返回值,实例引用传递。

622
来自专栏二进制文集

JDK源码分析 Integer

对于JDK源码分析的文章,仅仅记录我认为重要的地方。源码的细节实在太多,不可能面面俱到地写清每个逻辑。所以我的JDK源码分析,着重在JDK的体系架构层面,具体源...

873
来自专栏Java爬坑系列

【Java入门提高篇】Day33 Java容器类详解(十五)PriorityQueue详解

 今天要介绍的是基础容器类(为了与并发容器类区分开来而命名的名字)中的另一个成员——PriorityQueue,它的大名叫做优先级队列,想必即使没有用过也该有所...

741
来自专栏LanceToBigData

Java集合源码分析(三)Vevtor和Stack

前言   前面写了一篇关于的是LinkedList的除了它的数据结构稍微有一点复杂之外,其他的都很好理解的。这一篇讲的可能大家在开发中很少去用到。但是有的时候也...

2376

扫码关注云+社区