第2关:图的深度遍历

  • 任务要求
  • 参考答案
  • 评论2
  • 任务描述
  • 相关知识
  • 编程要求
  • 测试说明

任务描述

本关任务:以邻接表存储图,要求编写程序实现图的深度优先遍历。

相关知识

图的深度优先遍历类似于树的先序遍历, 是树的先序遍历的推广,其基本思想如下:

  1. 访问顶点v;
  2. 选择一个与顶点v相邻且没被访问过的顶点w,从w出发深度优先遍历。
  3. 直到图中与v相邻的所有顶点都被访问过为止

在程序里完成遍历需要在函数体外定义全局访问标志数组,记录顶点是否被访问过,初始时,所有元素均为0,表示所有顶点未被访问过:

int visited[MAX_VERTEX_NUM] = {0};

访问每个顶点时,定义输出顶点数据的专用函数:

 
  1. void visit(VertexType i)
  2. {
  3. printf("%s ",i); // VertexType是char [20]类型
  4. }

以邻接表作为存储结构进行深度优先遍历的算法如下:

深度优先遍历的代码分为两部分,遍历的图可能是非连通图,从一个顶点出发,可能不能遍历所有顶点,故对于每个顶点都要检查一次,是否被访问过,如果没有,从这个没被访问的顶点出发执行一次深度优先遍历,算法如下:

 
  1. void DFSTraverse(ALGgraph G)
  2. {
  3. // 初始条件:图G存在,vi是顶点的输出函数的指针。
  4. // 操作结果:从第1个顶点起,深度优先遍历图G,并对每个顶点访问一次且仅一次
  5. int v;
  6. for(v=0;v<G.vexnum;v++)
  7. visited[v]=0; // 访问标志数组初始化(未被访问)
  8. for(v=0;v<G.vexnum;v++)
  9. if(!visited[v])
  10. DFS(G,v); // 对尚未访问的顶点v调用DFS
  11. printf("\n");
  12. }

编程要求

根据提示,在右侧编辑器补充代码,实现以邻接表作为存储结构的图深度优先遍历算法:

  • void DFS(ALGraph G,int v); //从第v个顶点出发递归地深度优先遍历图G

  • void DFSTraverse(ALGraph G); // 对图G作深度优先遍历

测试说明

平台会对你编写的代码进行测试:

测试输入: 0 lt2.txt

输入说明: 第一行输入0,表示输入图的类型为有向图。 第二行输入文件名,该文件里保存了图的数据信息,内容如下:

有向图的世界里

第1行为图的顶点的个数n; 第2行为图的边的条数m; 第3行至第n+2行是n个顶点的数据; 第n+3行至第n+m+2行是m条边的数据;

预期输出: 有向图 7个顶点: 高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统 9条弧(边): 高等数学→离散数学 高等数学→C语言 程序设计基础→C语言 程序设计基础→数据结构 C语言→数据结构 离散数学→编译原理 离散数学→数据结构 数据结构→操作系统 数据结构→编译原理

 

深度优先遍历序列: 高等数学 离散数学 编译原理 数据结构 操作系统 C语言 程序设计基础

 

#include<stdio.h> 
#include<stdlib.h> 
#include<string.h>
#include<limits.h> 

#include"ALGraph.h"



void DFS(ALGraph G,int v);          //从第v个顶点出发递归地深度优先遍历图G
void DFSTraverse(ALGraph G);        // 对图G作深度优先遍历
int  visited[MAX_VERTEX_NUM];       // 访问标志数组(全局量)

int main()
{
	ALGraph g;
	CreateGraphF (g); // 利用数据文件创建图
	Display(g);       // 输出图
	printf("深度优先遍历序列:\n"); 
	DFSTraverse(g);	
	return 0;
}


void DFS(ALGraph G,int v)
{   //从第v个顶点出发递归地深度优先遍历图G
	/********** Begin **********/
	ArcNode *p;
	p=G.vertices[v].firstarc;
	visited[v]=1;
	visit(G.vertices[v].data);
	for(int w=FirstAdjVex(G,G.vertices[v].data);w>=0;w=NextAdjVex(G,G.vertices[v].data,G.vertices[w].data)){
		if(!visited[w])
			DFS(G,w);
	}
	/********** End **********/
}

void DFSTraverse(ALGraph G)
{   // 对图G作深度优先遍历
	/********** Begin **********/
    int v;
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	for(v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS(G,v);
	printf("\n");
	/********** End **********/
}

输出说明: 第一行输出图的类型。 第二行起输出图的顶点和边的数据信息。 最后一行为从“高等数学”出发进行深度优先遍历的序列。

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

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

相关文章

CHINTERGEO2023中国测绘地理信息技术装备展览会,大势智慧在3010展台期待您的莅临!

11月27日-11月29日 CHINTERGEO2023中国测绘地理信息技术装备展览会 二层-HALL3展厅-3010 大势智慧携符合信创要求的实景三维软硬件全流程解决方案 为您带来一场全国产、真安全的实景三维新型智能测绘装备盛宴 期待您的莅临&#xff01;

JNPF开发平台凭什么火?

一、关于低代码 JNPF平台在提供无代码&#xff08;可视化建模&#xff09;和低代码&#xff08;高度可扩展的集成工具以支持跨功能团队协同工作&#xff09;开发工具上是独一无二的。支持简单、快速地构建及不断改进Web端应用程序&#xff0c;可为整个应用程序的生命周期提供全…

onnx模型转换opset版本和固定动态输入尺寸

背景&#xff1a;之前我想把onnx模型从opset12变成opset12&#xff0c;太慌乱就没找着&#xff0c;最近找到了官网上有示例的&#xff0c;大爱onnx官网&#xff0c;分享给有需求没找着的小伙伴们。 1. onnx模型转换opset版本 官网示例&#xff1a; import onnx from onnx im…

拓扑排序-

有向无环图是拓扑排序 拓扑排序将图中所有的顶点排成一个线性序列&#xff0c;使得所有的有向边均从序列的前面指向后面。 拓扑排序使用深度优先搜索来实现&#xff0c;图中有环则无法进行拓扑排序 一个有向图&#xff0c;如果图中有入度为0的点&#xff0c;就把这个点删掉…

“一键导出,高效整理:将之前的部分记录导出!“

亲爱的朋友们&#xff0c;你们是否曾经为了导出之前的记录而感到烦恼&#xff1f;冗长的过程&#xff0c;无法精确控制的选项&#xff0c;实在让人感到心力交瘁。但现在&#xff0c;我们为你带来一种全新的解决方案&#xff0c;让你的工作更轻松&#xff0c;更高效&#xff01;…

Notpad-- ubuntu下载安装

Notpad-- ubuntu下载安装 下载 Gitee链接&#xff1a; https://gitee.com/cxasm/notepad– 安装 sudo apt install *.deb运行 /opt/apps/com.hmja.notepad/files/Notepad--出错 需要安装qt5 sudo apt-get install qt5-default

基于MS16F3211芯片的触摸控制灯的状态变化和亮度控制(11.20)

1.判断长按短按 u8 Mode_state_flag 0; u32 buttonPressTime 0; u8 longPressflag 0; u8 shortPressflag 0; // 普通认证 执行此处函数 void T_Key0_Func(void) {if (TKey_Signal.oneBit.b0 1){buttonPressTime;}if ((TKey_Signal.oneBit.b0 1) && (Pre_TKey_Re…

Docker快速安装Mariadb11.1

MariaDB数据库管理系统是MySQL的一个分支&#xff0c;主要由开源社区在维护&#xff0c;采用GPL授权许可 MariaDB的目的是完全兼容MySQL&#xff0c;包括API和命令行&#xff0c;使之能轻松成为MySQL的代替品。在存储引擎方面&#xff0c;使用XtraDB来代替MySQL的InnoDB。 Mari…

每日一题 2216. 美化数组的最少删除数(中等,贪心)

贪心&#xff0c;一开始可能会觉得如果删除前面一个相等的元素时&#xff0c;会导致后面的元素前移&#xff0c;造成产生更多的相等的元素对的情况但是在遍历过程中至少要在相等元素对中删除一个&#xff0c;也可以同时删除两个使得后面的元素奇偶关系不变&#xff0c;但是显然…

基于GB28181搭建流媒体服务器--1.概念解析

什么是GB28181 GB28181(国标28181)&#xff0c;全称为《中华人民共和国公共安全视频监控联网系统技术要求》&#xff0c;是中国国家标准委员会发布的一个针对公共安全视频监控领域的标准框架。该标准指导了视频监控设备之间的联网互通&#xff0c;统一管理和控制&#xff0c;并…

Vue3鼠标拖拽生成区域块并选中元素

Vue3鼠标拖拽生成区域块并选中元素&#xff0c;选中的元素则背景高亮(或者其它逻辑)。 <script setup> import { ref } from vue// 区域ref const regionRef ref(null)// 内容ref const itemRefs ref(null)// 是否开启绘画区域 const enable ref(false)// 鼠标开始位置…

路线规划问题

文章目录 1、问题描述2、节点类设置3、设置节点之间的关系4、路线规划5、完整类6、结果7、优化 1、问题描述 如下图&#xff0c;存在A~F六个地点&#xff0c;已知所有地点的相关关系&#xff08;每个地点能到达的下一节点名称以及对应的路程&#xff09;&#xff1b; 计算某个…

深度学习动物识别 - 卷积神经网络 机器视觉 图像识别 计算机竞赛

文章目录 0 前言1 背景2 算法原理2.1 动物识别方法概况2.2 常用的网络模型2.2.1 B-CNN2.2.2 SSD 3 SSD动物目标检测流程4 实现效果5 部分相关代码5.1 数据预处理5.2 构建卷积神经网络5.3 tensorflow计算图可视化5.4 网络模型训练5.5 对猫狗图像进行2分类 6 最后 0 前言 &#…

最新最全系列之Selenium:传入webdriver驱动的新方法 Service()函数;以前的executable_path报警告,即将弃用

传入webdriver驱动的新方法 Service()函数&#xff1b;以前的executable_path报警告&#xff0c;即将弃用 以前的方法 举例&#xff1a;webdriver.Chrome(executable_pathdriver_path)&#xff1b;看提示警告&#xff0c;提示该方法即将被弃用&#xff1b;如下图&#xff1a; …

碳中和领域研究,细谈新能源“爆发”的原因之一

碳中和时代&#xff0c;能源结构、能源生产方式将发生根本变化&#xff0c;依靠绿色科技的进步&#xff0c;驱动颠覆性技术的创新。 碳中和的概念及主要方式 碳中和可以理解为一种类似“数字化”、“信息化”的方式或概念。覆盖我们生活中的各个领域。 实现碳中和的目的不仅…

力控软件与2台200Smart之间无线以太网通信

在实际系统中&#xff0c;车间里分布多台PLC&#xff0c;需要用上位机软件集中控制。通常所有设备距离在几十米到上百米不等。用户会选择以太网方式是因为传输速度有保障&#xff0c;而选择无线以太网方案是因为不想开挖电缆沟&#xff0c;或者布线不方便&#xff0c;不但施工麻…

HCIP-二、MSTP+Eth-trunk

二、MSTPEth-trunk 实验拓扑实验需求及解法 实验拓扑 实验需求及解法 //1.如图所示&#xff0c;配置设备名称和 IP 地址。 //2.在 SW1 与 SW2 之间配置链路聚合协议 LACP&#xff0c;完成以下需求&#xff1a; //2.1 SW1 作为主动端&#xff0c;设置系统优先级为最高。 [SW1]l…

软件测试最全的面试八股文(2023最新版)

1、你的测试职业发展是什么? 测试经验越多&#xff0c;测试能力越高。所以我的职业发展是需要时间积累的&#xff0c;一步步向着高级测试工程师奔去。而且我也有初步的职业规划&#xff0c;前3年积累测试经验&#xff0c;按如何做好测试工程师的要点去要求自己&#xff0c;不…

【微信小程序】2023年11月版本 关于小程序隐私保护指引设置的公告 | 修改微信小程序隐私保护 |小程序无法获取用户昵称 头像 性别 等问题

一、登录小程序后台 《关于小程序隐私保护指引设置的公告》 https://mp.weixin.qq.com/cgi-bin/announce?actiongetannouncement&announce_id11691660367cfUvX&version&langzh_CN&token 上面是官方的文档&#xff0c;但是由于比较陈旧&#xff0c;和现在的页面…

“三面一体”的业务调度方案在运营商订单运营的实践

在当前信息化时代&#xff0c;运营商的业务流程复杂度和多样性持续增长&#xff0c;多个系统、部门以及相关事务需要进行高效准确的调度。如何在这样的背景下&#xff0c;保证业务流程的顺畅&#xff0c;业务信息的实时传递以及业务决策的准确性&#xff0c;是业务运营面临的重…