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

深度优先遍历

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

因为需要保证一个节点只能访问一次,所以我们需要一个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 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

#define和typedef的用法与区别及面试问题

在C/C++语言中,typedef常用来定义一个标识符及关键字的别名,它是语言编译过程的一部分,但它并不实际分配内存空间,实例像:

1351
来自专栏小勇DW3

java设计模式之模板模式以及钩子方法使用

  模板方法模式是通过把不变行为搬到超类,去除子类里面的重复代码提现它的优势,它提供了一个很好的代码复用平台。当不可变和可变的方法在子类中混合在一起的时候,

1124
来自专栏Java架构

Java 8简明教程

1795
来自专栏用户2442861的专栏

Python 递归函数

递归函数 在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 举个例子,我们来计算阶乘 n! = 1 * 2 * 3 * ...

412
来自专栏老马说编程

(92) 函数式数据处理 (上) / 计算机程序的思维逻辑

上节我们介绍了Lambda表达式和函数式接口,本节探讨它们的应用,函数式数据处理,针对常见的集合数据处理,Java 8引入了一套新的类库,位于包java.uti...

1716
来自专栏程序员与猫

[译]C#和.NET中的字符串

原文地址:Jon Skeet:Strings in C# and .NET System.String 类型(在C#语言中对应的别名是string)是.NET最...

19610
来自专栏云霄雨霁

词法分析程序

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

第12章 元编程与注解、反射第12章 元编程与注解、反射

反射(Reflection)是在运行时获取类的函数(方法)、属性、父类、接口、注解元数据、泛型信息等类的内部信息的机制。这些信息我们称之为 RTTI(Run-T...

762
来自专栏冰霜之地

Objc 对象的今生今世

在面向对象编程中,我们每天都在创建对象,用对象描述着整个世界,然而对象是如何从孕育到销毁的呢?

781
来自专栏开发与安全

从零开始学C++之模板(三):缺省模板参数(借助标准模板容器实现Stack模板)、成员模板、关键字typename

一、缺省模板参数 回顾前面的文章,都是自己管理stack的内存,无论是链栈还是数组栈,能否借助标准模板容器管理呢?答案是肯定的,只需要多传一个模板参数即可,而且...

1960

扫码关注云+社区