图形的遍历

图形的遍历一个图形G=(V,E),存在某一顶点v,希望从v开始,通过此顶点相邻的顶点而去访问G中其他顶点直达全部的顶点遍历完毕。在遍历的过程中可能会重复经过某些顶点及边线,经由图形的遍历可以判断该图形是否连通,并找出连通单元和路径。图形遍历有两种方法:深度优先搜索Deep-First-Search广度优先搜索Breadth-First-Search一、深度优先搜索从图形的某一顶点开始遍历,被访问过的

大家好,又见面了,我是你们的朋友全栈君。

一个图形G=(V,E),存在某一顶点v,希望从v开始,通过此顶点相邻的顶点而去访问G中其他顶点直达全部的顶点遍历完毕。在遍历的过程中可能会重复经过某些顶点及边线,经由图形的遍历可以判断该图形是否连通,并找出连通单元和路径。
图形遍历有两种方法:

  • 深度优先搜索Deep-First-Search
  • 广度优先搜索Breadth-First-Search

一、深度优先搜索

从图形的某一顶点开始遍历,被访问过的顶点做上已访问的标记,接着从与此顶点相邻且未访问过的顶点中选择任意一个顶点,并做上已访问的记号,再以该顶点为新的起点进行深度优先搜索遍历。

我们以下图为例进行代码实现:
这里写图片描述

定义public static void DFS(int current)实现深度优先搜索,定义数组run[]来标记顶点的遍历情况,1表示已遍历,0表示未遍历。图使用邻接表进行存放,从选定顶点的链表的头结点进行判断,若该顶点未遍历,则递归调用该函数从该节点开始进行深度优先遍历,否则指针后移寻找该顶点未被遍历的顶点。

public static void DFS(int current)代码如下:

    public static void DFS(int current) {
        run[current]=1;                                        //改顶点设为已遍历
        System.out.print("["+current+"]");                     //打印顶点

        while(head[current].first!=null) {                     //从链表头结点开始
            if(run[head[current].first.data]==0)               //若该顶点未遍历就进行DFS递归调用
                DFS(head[current].first.data);
            head[current].first=head[current].first.next;      //否则指针后移
        }
    }

主要代码如下:(Node类和GraphLink类的定义见博客图表示法中的邻接表法
http://blog.csdn.net/zd454909951/article/details/78896793

public class Test {
    //静态变量可全局使用
    public static int[] run=new int[9];                     //判断顶点是否已遍历,1代表遍历,0代表未遍历
    public static GraphLink[] head=new GraphLink[9];        //声明链接表数组

    public static void main(String[] args) {
        int data[][]= {
  
  {
  
  1,2},{
  
  2,1},{
  
  1,3},{
  
  3,1},{
  
  2,4},{
  
  4,2},{
  
  2,5},{
  
  5,2},{
  
  3,6},{
  
  6,3},{
  
  3,7},{
  
  7,3},{
  
  4,5},{
  
  5,4},{
  
  6,7},{
  
  7,6},{
  
  5,8},{
  
  8,5},{
  
  6,8},{
  
  8,6}};
        System.out.println("图形的邻接表的内容:");
        for(int i=1;i<9;i++) {

            run[i]=0;
            head[i]=new GraphLink();
            System.out.print("顶点"+i+"=>");
            for(int j=0;j<data.length;j++) {
                if(data[j][0]==i)
                    head[i].insert(data[j][1]);
            }
            head[i].print();
        }
        System.out.println("深度优先遍历顶点:");
        DFS(1);    //从顶点1开始遍历
        System.out.println();
    }

程序运行结果如下:
这里写图片描述

递归函数DFS具体运行过程如下:
这里写图片描述

这里写图片描述

二、广度优先搜索

从图中的某一顶点开始遍历,然后访问所有与其相邻的顶点,最后访问所有与这些顶点相邻的顶点。
代码中需要用到队列,选择一个顶点入队,然后将其所有相邻的未被访问的顶点都入队,依次对队列中的顶点进行上述操作直到队列为空。

public static void BFS(int current)代码如下:

    /*广度优先搜索函数*/
    public static void BFS(int current) {
        Node tempNode;
        enqueue(current);                                         //将第一个顶点存入队列
        run[current]=1;                                           //将遍历过的顶点设为1
        System.out.print("["+current+"]");                        //打印该遍历过的顶点
        while(front!=rear) {                                      //判断队列是否为空
            current=dequeue();                                    //从队列中取出顶点
            tempNode=head[current].first;                         //记录目前顶点的链表的表头

            while(tempNode!=null) {                               //判断该顶点的链表是否为空,即遍历所有与该顶点相邻的顶点
                if(run[tempNode.data]==0) {                       //相邻的顶点未遍历
                    enqueue(tempNode.data);                       //访问该顶点并存入队列
                    run[tempNode.data]=1;                         //将该顶点标记为已遍历
                    System.out.print("["+tempNode.data+"]");      //打印该顶点
                }
                tempNode=tempNode.next;                           //指针后移,继续遍历出队列顶点的链表
            }
        }
    }

    /*入队*/
    public static void enqueue(int value) {
        if(rear>=MAXSIZE)                                         //队列已满
            return;
        rear++;
        queue[rear]=value;
    }

    /*出队*/
    public static int dequeue() {
        if(front==rear)                                           //队列为空
            return -1;
        front++;
        return queue[front];
    }

主要代码如下:(Node类和GraphLink类的定义见博客图表示法中的邻接表法
http://blog.csdn.net/zd454909951/article/details/78896793

public class Test {
    public static int[] run=new int[9];                          //用来记录各顶点是否遍历过
    public static GraphLink[] head=new GraphLink[9];
    public final static int MAXSIZE=10;                          //定义队列的最大容量
    static int[] queue=new int[MAXSIZE];                         //队列数组的声明
    static int front=-1,rear=-1;                                 //定义队列的头指针和尾指针

    public static void main(String[] args) {
        int data[][]= {
  
  {
  
  1,2},{
  
  2,1},{
  
  1,3},{
  
  3,1},{
  
  2,4},{
  
  4,2},{
  
  2,5},{
  
  5,2},{
  
  3,6},{
  
  6,3},{
  
  3,7},{
  
  7,3},{
  
  4,5},{
  
  5,4},{
  
  6,7},{
  
  7,6},{
  
  5,8},{
  
  8,5},{
  
  6,8},{
  
  8,6}};
        System.out.println("图形的邻接表的内容:");
        for(int i=1;i<9;i++) {
            run[i]=0;
            head[i]=new GraphLink();
            System.out.print("顶点"+i+"=>");
            for(int j=0;j<data.length;j++) {
                if(data[j][0]==i)
                    head[i].insert(data[j][1]);
            }
            head[i].print();
        }
        System.out.println("深度优先遍历顶点:");
        BFS(1);  //调用广度优先搜索函数,从顶点1开始访问
        System.out.println();
    }
}

程序运行结果如下:

这里写图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/133639.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 差分进化算法之Matlab实现「建议收藏」

    差分进化算法之Matlab实现「建议收藏」一、介绍差分进化算法是模拟自然界生物种群以“优胜劣汰,适者生存”为原则的进化发展规律而形成的一种随机启发式搜索算法。其保留了基于种群的全局搜索策略,采用实数编码,基于差分的简单变异操作和一对一的竞争生存策略,比遗传算法更简单。同时,差分进化算法独特的记忆能力使其可以动态的跟踪当前的搜索情况,及时调整搜索测量,因此具有较强的全局收敛能力。目前为止,差分进化算法已经成为一种求解非线性,不可微,多极…

    2022年10月24日
  • 图像去色算法_matlab去雾算法

    图像去色算法_matlab去雾算法先上图看一些算法效果                                           上图中从左到右依次是原图、photoshop去色结果、Matlab的rgb2gray函数处理效果、取rgb均值的效果、使用香港中文大学论文(见下)的结果、Glundland论文(见下)的结果。还有

  • 用Java 写一个冒泡排序

    用Java 写一个冒泡排序冒泡排序几乎是个程序员都写得出来,但是面试的时候如何写一个逼格高的冒泡排序却不是每个人都能做到,下面提供一个参考代码:importjava.util.Comparator;/***排序器接口(策略模式:将算法封装到具有共同接口的独立的类中使得它们可以相互替换)*/publicinterfaceSorter{ /** *排序 *@paramlist待排序的数组 */ public<TextendsComparable<T>>voids

  • mysql卸载教程5.5_centos卸载mysql

    mysql卸载教程5.5_centos卸载mysql完整卸载MySQL数据库1、关掉mysql服务直接搜索服务或者右键“我的电脑”,选择“管理”,打开计算机管理,选择“服务”右键MySQL服务,选择“停止”2、卸载mysql程序开始菜单->控制面板->程序和功能3、删除计算机上的残留文件(1)删除C盘-》programData->mysql文件夹,programData文件夹为隐藏文件夹//这一步很重要(2)删除mysql的安装目录4、删除注册表信息往往我们进行完上面的两个步骤,我们计算机上的mysql就已

  • linux嵌入式系统的缺点,arm嵌入式主板的优缺点

    嵌入式主板是嵌入在设备里面做控制、数据处理使用的CPU板,常见的有两类,即基于X86的嵌入式主板和基于RISC的ARM嵌入式主板。今天我们就来认识arm嵌入式主板,arm嵌入式主板就是一个嵌入在设备里面做控制、数据处理使用的CPU板。一般作为工控主板使用。ARM处理器是一种16/32位的嵌入式RISC微处理器,具有低成本、高性能、低功耗的特点。ARM9系列微处理器具有以下特点:支持32位ARM…

  • map遍历的几种方式分别是什么「建议收藏」

    map遍历的几种方式分别是什么「建议收藏」map遍历的方式有4种1、使用for循环遍历map;2、使用迭代遍历map;3、使用keySet迭代遍历map;4、使用entrySet遍历map。java代码:Map<string

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号