算法学习(5)-图的遍历

目录

什么是深度和广度优先

图的深度优先遍历-城市地图

图的广度优先遍历-最少转机


什么是深度和广度优先

         使用深度优先搜索来遍历这个图的过程具体是:

  1. 首先从一个未走到过的顶点作为起始顶点, 比如以1号顶点作为起点。
  2. 沿1号顶点的边去尝试访问其它未走到过的顶点, 首先发现2 号顶点还没有走到过, 于是来到了2 号顶点。
  3. 再以2 号顶点作为出发点继续尝试访问其它未走到过的顶点, 这样又来到了4号顶点。
  4. 再以4 号顶点作为出发点继续尝试访问其它未走到过的顶点。
  5. 但是, 此时沿4号顶点的边, 已经不能访问到其它未走到过的顶点了, 所以要返回到2号顶点。
  6. 返回到2号顶点后, 发现沿2 号顶点的边也不能再访问到其它未走到过的顶点。因此还需要继续返回到1号顶点。
  7. 再继续沿1号顶点的边看看还能否访问到其它未走到过的顶点。
  8. 此时又会来到3号顶点, 再以3号顶点作为出发点继续访问其它未走到过的顶点, 千是又来到5号顶点。
  9. 到此, 所有顶点都走到过了, 遍历结束。

        深度优先遍历的主要思想就是:首先以一个未被访问过的顶点作为起始顶点,沿当前顶点的边走到未访问过的顶点;没有未访问过的顶点时, 则回到上一个顶点, 继续试探访问别的顶点, 直到所有的顶点都被访问过。

        显然, 深度优先遍历是沿着图的某一条分支遍历直到末端, 然后回溯, 再沿着另一条进行同样的遍历, 直到所有的顶点都被访问过为止。那这一过程如何用代码来实现呢?在讲代码实现之前我们先来解决如何存储一个图的问题。最常用的方法是使用一个二维数组e来存储, 如下。

 

        上图二维数组中第i行第j列表示的就是顶点 i 到顶点 j 是否有边。1表示有边, ∞表示
没有边, 这里我们将自己到自己(即i等于j)设为0。我们将这种存储图的方法称为图的邻
接矩阵存储法。
        注意观察会发现这个二维数组是沿主对角线对称的, 因为上面这个图是无向图。所谓无向阳指的就是图的边没有方向, 例如边1-5表示, 1号顶点可以到5号顶点, 5号顶点也可以到1号顶点。
        接下来要解决的问题就是如何用深度优先搜索来实现遍历了。 

void dfs(int cur) { // cur是当前所在的顶点编号
    printf("%d. ", cur);
    sum++; // 每访问一个顶点s就加1
    if (sum == n) return; // 所有的顶点都已经访问过则直接退出
    for (i = 1; i <= n; i++) { // 从1号顶点到n号顶点依次尝试,看哪些顶点与当前顶点cur有边相连
        // 判断当前顶点cur到顶点i是否有边,并判断顶点i是否已访问过
        if (e[cur][i] == 1 && book[i] == 0) {
            // 标记顶点i已经访问过
            book[i] = 1;
            // 从顶点i再出发继续遍历
            dfs(i);
        }
    }
    return;
}

        在上面的代码中变揽cur存储的是当前正在遍历的顶点, 二维数组e存储的就是图的边(邻接矩阵), 数组book用来记录哪些顶点已经访问过, 变揽sum用来记录已经访问过多少个顶点, 变证n存储的是图的顶点的总个数。完整代码如下。

#include <stdio.h>

int book[101], sum, n, e[101][101];

void dfs(int cur) { // cur是当前所在的顶点编号
    int i;
    printf("%d ", cur);
    sum++; // 每访问一个顶点,sum就加1
    if (sum == n) return; // 所有的顶点都已经访问过则直接退出
    for (i = 1; i <= n; i++) { // 从1号顶点到n号顶点依次尝试,看哪些顶点与当前顶点cur有边相连
        // 判断当前顶点cur到顶点i是否有边, 并判断顶点i是否已访问过
        if (e[cur][i] == 1 && book[i] == 0) {
            // 标记顶点i已经访问过
            book[i] = 1;
            // 从顶点i再出发继续遍历
            dfs(i);
        }
    }
    return;
}

int main() {
    int i, j, m, a, b;
    scanf("%d %d", &n, &m);
    // 初始化二维矩阵
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999; // 我们这里假设999999999为正无穷
        }
    }
    // 读入顶点之间的边
    for (i = 1; i <= m; i++) {
        scanf("%d %d", &a, &b);
        e[a][b] = 1;
        e[b][a] = 1; // 这里是无向图,所以需要将e[b][a]也赋为1
    }
    // 从1号城市出发
    book[1] = 1; // 标记1号顶点已访问
    dfs(1); // 从1号顶点开始遍历
    getchar();
    getchar();
    return 0;
}

        广度优先遍历的主要思想就是:首先以一个未被访问过的顶点作为起始顶点,访问其所有相邻的顶点, 然后对每个相邻的顶点,再访问它们相邻的未被访问过的顶点,直到所有顶点都被访问过, 遍历结束。

        代码实现如下:

#include <stdio.h>

int main() {
    int i, j, n, m, a, b, cur;
    int book[101] = {0}; // 使用数组初始化语法将book数组初始化为全0
    int e[101][101];
    int que[10001], head = 0, tail = 0; // 将队列初始化为0

    scanf("%d %d", &n, &m);

    // 初始化二维矩阵
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (i == j) {
                e[i][j] = 0;
            }
            else {
                e[i][j] = 99999999; // 假设999999999为正无穷
            }
        }
    }

    // 读入顶点之间的边
    for (i = 1; i <= m; i++) {
        scanf("%d %d", &a, &b);
        e[a][b] = 1;
        e[b][a] = 1; // 无向图,需要双向赋值
    }

    // 从1号顶点出发,将1号顶点加入队列
    que[tail] = 1;
    tail++;
    book[1] = 1; // 标记1号顶点已访问

    // 当队列不为空时循环
    while (head < tail) {
        cur = que[head]; // 当前正在访问的顶点编号
        // 从1~n依次尝试
        for (i = 1; i <= n; i++) {
            // 判断从顶点cur到顶点i是否有边,且顶点i是否已经访问过
            if (e[cur][i] == 1 && book[i] == 0) {
                // 如果从顶点cur到顶点i有边,并且顶点i没有被访问过,则将顶点i入队
                que[tail] = i;
                tail++;
                book[i] = 1; // 标记顶点i已访问
            }
        }
        // 如果tail大于n,则所有顶点都已经被访问过,退出循环
        if (tail > n) {
            break;
        }
        head++; // 顶点扩展结束后,head++,继续往下扩展
    }

    // 输出队列中的顶点编号
    for (i = 0; i < tail; i++) {
        printf("%d ", que[i]);
    }
    getchar();
    getchar();
    return 0;
}

图的深度优先遍历-城市地图

         我们可以创建一个5*5的邻接矩阵,如下图:

        用book数组记录哪些城市已经走过,用全局变量min来更新每次找到的路径的最小值,代码实现如下:

#include <stdio.h>
int min = 99999999, book[101], n, e[101][101]; // 我们这里假设999999999为正无穷

// cur是当前所在的城市编号,dis是当前已经走过的路程
void dfs(int cur, int dis) {
    int j;
    // 如果当前走过的路程已经大于之前找到的最短路,则没有必要再往下尝试了,立即返回
    if (dis > min)
        return;
    if (cur == n)  // 判断是否到达了目标城市
    {
        if (dis < min) {
            min = dis;  // 更新最小值
            return;
        }
    }
    for (j = 1; j <= n; j++) { // 从1号城市到n号城市依次尝试
        // 判断当前城市cur到城市j是否有路,并判断城市j是否在已走过的路径中
        if (e[cur][j] != 99999999 && book[j] == 0) {
            book[j] = 1;  // 标记城市j已经在路径中
            dfs(j, dis + e[cur][j]);  // 从城市j再出发,继续寻找目标城市
            book[j] = 0;  // 之前一步探索完毕之后,取消对城市j的标记
        }
    }
}

int main() {
    int i, j, m, a, b, c;
    scanf("%d %d", &n, &m);

    // 初始化二维矩阵
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999;

    // 读入城市之间的道路
    for (i = 1; i <= m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        e[a][b] = c;
    }

    // 从1号城市出发
    book[1] = 1;  // 标记1号城市已经在路径中
    dfs(1, 0);  // 1表示当前所在的城市编号,0表示当前已经走过的路程

    printf("%d\n", min);  // 打印1号城市到目标城市的最短路径
    getchar();
    getchar();
    return 0;
}


图的广度优先遍历-最少转机

 

#include <stdio.h>

struct note {
    int x;  // 城市编号
    int s;  // 转机次数
};

int main() {
    struct note que[2501];
    // 初始化
    int e[51][51] = {0}, book[51] = {0};
    int head, tail;
    int i, j, n, m, a, b, cur, start, end, flag = 0;
    scanf("%d %d %d %d", &n, &m, &start, &end);

    // 初始化二维矩阵
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999;
        }
    }

    // 读入城市之间的航班
    for (i = 1; i <= m; i++) {
        scanf("%d %d", &a, &b);
        // 注:这里是无向图
        e[a][b] = 1;
        e[b][a] = 1;
    }

    // 队列初始化
    head = 1;
    tail = 1;
    // 从start号城市出发,将start号城市加入队列
    que[tail].x = start;
    que[tail].s = 0;
    tail++;
    book[start] = 1;  // 标记start号城市已在队列中

    // 当队列不为空的时候循环
    while (head < tail) {
        cur = que[head].x;  // 当前队列中首城市的编号
        for (j = 1; j <= n; j++) {  // 从1~n依次尝试
            // 从城市cur到城市j是否有航班并且判断城市j是否已经在队列中
            if (e[cur][j] != 99999999 && book[j] == 0) {
                // 如果从城市cur到城市j有航班并且城市j不在队列中,则将城市j入队
                que[tail].x = j;
                que[tail].s = que[head].s + 1;  // 转机次数+1
                tail++;
                // 标记城市j已经在队列中
                book[j] = 1;
                // 如果到达目标城市,停止扩展,任务结束,退出循环
                if (que[tail].x == end) {
                    // 注意下面两句话的位置千万不要写颠倒了
                    flag = 1;
                    break;
                }
            }
        }
        if (flag == 1)
            break;
        head++;  // 注意这地方,千万不要忘记当一个点扩展结束后,head++才能继续扩展
    }

    // 打印队列中末尾最后一个(目标城市)的转机次数
    // 注意:tail是指向队列队尾(即最后一位)的下一个位置,所以这里要-1
    printf("%d\n", que[tail - 1].s);
    getchar();
    getchar();
    return 0;
}

         当然也可以使用深度优先搜索解决, 但是这里用广度优先搜索会更快。广度优先搜索更
加适用于所有边的权值相同的情况。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/581642.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

pycharm 安装“通义灵码“并测试

过程&#xff1a;“File>setting>Plugins” 提示&#xff1a; 翻译之后&#xff1a; 点击"接受"之后&#xff0c;提示一下图片&#xff0c;点击ok 安装完成&#xff1a; 安装完"通义灵码"之后&#xff0c;需要登陆&#xff0c;登陆后测试 参考…

NLP transformers - 文本分类

Text classification 文章目录 Text classification加载 IMDb 数据集Preprocess 预处理EvaluateTrainInference 本文翻译自&#xff1a;Text classification https://huggingface.co/docs/transformers/tasks/sequence_classification notebook : https://colab.research.googl…

FPGA高端项目:FPGA帧差算法多目标图像识别+目标跟踪,提供11套工程源码和技术支持

目录 1、前言免责声明 2、相关方案推荐FPGA帧差算法单个目标图像识别目标跟踪 3、详细设计方案设计原理框图运动目标检测原理OV5640摄像头配置与采集OV7725摄像头配置与采集RGB视频流转AXI4-StreamVDMA图像缓存多目标帧差算法图像识别目标跟踪模块视频输出Xilinx系列FPGA工程源…

STM32之HAL开发——ADC入门介绍

ADC简介 模数转换&#xff0c;即Analog-to-Digital Converter&#xff0c;常称ADC&#xff0c;是指将连续变量的模拟信号转换为离散的数字信号的器件&#xff0c;比如将模温度感器产生的电信号转为控制芯片能处理的数字信号0101&#xff0c;这样ADC就建立了模拟世界的传感器和…

机器学习每周挑战——百思买数据

最近由于比赛&#xff0c;断更了好久&#xff0c;从五一开始不会再断更了。这个每周挑战我分析的较为简单&#xff0c;有兴趣的可以将数据集下载下来试着分析一下&#xff0c;又不会的我们可以讨论一下。 这是数据集&#xff1a; import pandas as pd import numpy as np impo…

leetcode_38.外观数列

38. 外观数列 题目描述&#xff1a;给定一个正整数 n &#xff0c;输出外观数列的第 n 项。 「外观数列」是一个整数序列&#xff0c;从数字 1 开始&#xff0c;序列中的每一项都是对前一项的描述。 你可以将其视作是由递归公式定义的数字字符串序列&#xff1a; countAndSay(1…

bugku-ok

打开文件发现有很多ok的字符 转在线地址解码

基于3D机器视觉的注塑缺陷检测解决方案

注塑检测是对注塑生产过程中的产品缺陷进行识别和检测的过程。这些缺陷可能包括色差、料流痕、黑点&#xff08;包括杂质&#xff09;等&#xff0c;它们可能是由多种因素引起&#xff0c;如原料未搅拌均匀、烘料时间过长、工业温度局部偏高、模具等问题造成的。不仅影响产品的…

Stable Diffusion教程:文生图

最近几天AI绘画没有什么大动作&#xff0c;正好有时间总结下Stable Diffusion的一些基础知识&#xff0c;今天就给大家再唠叨一下文生图这个功能&#xff0c;会详细说明其中的各个参数。 文生图是Stable Diffusion的核心功能&#xff0c;它的核心能力就是根据提示词生成相应的…

【喜报】科大睿智为武汉博睿英特科技高质量通过CMMI3级评估咨询工作

武汉博睿英特科技有限公司是信息通信技术产品、建筑智慧工程服务提供商。其拥有专注于航空、政府、教育、金融等多行业领域的资深团队&#xff0c;及时掌握最新信息通信应用技术&#xff0c;深刻理解行业业务流程&#xff0c;擅于整合市场优质资源&#xff0c;积极保持与高校产…

redis ZRANGE 使用最详细文档

环境&#xff1a; redis_version:7.2.2 本文参考 redis 官方文档1 语法 ZRANGE key start stop [BYSCORE | BYLEX] [REV] [LIMIT offset count] [WITHSCORES]参数含义key是有序集合的键名start stop在不同语境下&#xff0c;可用值不一样BYSCORE | BYLEX按照分数查询 | 相…

【汇编】#6 80x86指令系统其二(串处理与控制转移与子函数)

文章目录 一、串处理指令1. 与 REP 协作的 MOVS / STOS / LODS的指令1.1 重复前缀指令REP1.2 字符串传送指令&#xff08;Move String Instruction&#xff09;1.2 存串指令&#xff08;Store String Instruction&#xff09;1.3 取字符串指令&#xff08;Load String Instruct…

[华为OD]给定一个 N*M 矩阵,请先找出 M 个该矩阵中每列元素的最大值 100

题目&#xff1a; 给定一个 N*M 矩阵&#xff0c;请先找出 M 个该矩阵中每列元素的最大值&#xff0c;然后输出这 M 个值中的 最小值 补充说明&#xff1a; N 和 M 的取值范围均为&#xff1a;[0, 100] 示例 1 输入&#xff1a; [[1,2],[3,4]] 输出&#xff1a; 3 说…

【UE5】数字人基础

这里主要记录一下自己在实现数字人得过程中涉及导XSens惯性动捕&#xff0c;视频动捕&#xff0c;LiveLinkFace表捕&#xff0c;GRoom物理头发等。 一、导入骨骼网格体 骨骼网格体即模型要在模型雕刻阶段就要雕刻好表捕所需的表情体(blendshape)&#xff0c;后面表捕的效果直…

机器学习:基于Sklearn框架,使用逻辑回归对由心脏病引发的死亡进行预测分析

前言 系列专栏&#xff1a;机器学习&#xff1a;高级应用与实践【项目实战100】【2024】✨︎ 在本专栏中不仅包含一些适合初学者的最新机器学习项目&#xff0c;每个项目都处理一组不同的问题&#xff0c;包括监督和无监督学习、分类、回归和聚类&#xff0c;而且涉及创建深度学…

数据分析-----方法论

什么是数据分析方法 数据分析方法&#xff1a;将零散的想法和经验整理成有条理的、系统的思路&#xff0c;从而快速地解决问题。 案例&#xff1a; 用户活跃度下降 想法&#xff1a; APP出现问题&#xff1f;去年也下降了吗&#xff1f;是所有的人群都在下降吗&#xff1f…

vscode中新建vue项目

vscode中新建vue项目 进入项目文件夹&#xff0c;打开终端 输入命令vue create 项目名 如vue create test 选择y 选择vue3 进入项目&#xff0c;运行vue项目 输入命令cd test和npm run serve

Spark RDD

Spark RDD操作 Spark执行流程 在上一讲中&#xff0c;我们知道了什么是Spark&#xff0c;什么是RDD、Spark的核心构成组件&#xff0c;以及Spark案例程序。在这一讲中&#xff0c;我们将继续需要Spark作业的执行过程&#xff0c;以及编程模型RDD的各种花式操作&#xff0c;首…

蓝桥杯ctf2024 部分wp

数据分析 1. packet 密码破解 1. cc 逆向分析 1. 欢乐时光 XXTEA #include<stdio.h> #include<stdint.h> #define DELTA 0x9e3779b9 #define MX (((z>>5^y<<2)(y>>3^z<<4))^((sum^y)(key[(p&3)^e]^z))) void btea(unsigned int* v…

【Python 对接QQ的接口】简单用接口查询【等级/昵称/头像/Q龄/当天在线时长/下一个等级升级需多少天】

文章日期&#xff1a;2024.04.28 使用工具&#xff1a;Python 类型&#xff1a;QQ接口 文章全程已做去敏处理&#xff01;&#xff01;&#xff01; 【需要做的可联系我】 AES解密处理&#xff08;直接解密即可&#xff09;&#xff08;crypto-js.js 标准算法&#xff09;&…
最新文章