[puzzle-2]无向图的深度优先搜索算法
创始人
2025-05-28 09:55:14

首先在将算法之前需要先构造无向图，具体请参考上一篇文章《[puzzle-1]无向图的存储方式》.

深度优先搜索算法介绍

深度优先算法类似于 树的先序遍历  ：

1、找到一个未被遍历的顶点，如上图V1,首先将V1状态标注为 访问过。

2、找到V1的临界点V2标注为 访问过，找到V2的邻接点V4标注为 访问过，继续找到V4的邻接点V8标注为 访问过，继续找到V8的邻接点V5标注为 访问过。

3、找到V5后，V5没有未被访问过的邻接点了，开始回退，V5退到V8,V8退到V4,V4退到V2,V2退到V1.

4、找到V1的另外一个邻接点V3标注为 访问过，找到V3的邻接点V6标注为 访问过，继续找到V6的邻接点V7标注为 访问过。

5、找到V7后，V7没有被访问过的临界点了，开始回退，V7回退到V6，V6回退到V3,V3回退到V1.

6、查找V1是否还有没有被访问的邻接点，如果有继续重复上述操作，知道所有的邻接点都被访问完毕。

如上图的顶点遍历顺序是：V1->V2->V4->V8->V5->V3->V6->V7

C语言代码实现：

1、声明一个用于存放所有顶点访问状态的数据。

// 顶点访问状态的数组
int vertex_status[MAX_NUM];

2、构建无向图的时候初始化顶点访问状态为0；

	// 初始化顶点状态for(i=0;i

3、开始搜索

        确保拿到每一个节点，如果当前节点没有访问过，调用 深度优先搜索算法        

// 深度搜索启动 
void dfs_start(void)
{int i;// 确保获取到每一个顶点 for(i=0;i

4、深度搜索算法函数

// 深入优先搜索
void dfs(int pos)
{// 如果当前顶点没有被访问 if(!vertex_status[pos]) {// 设置顶点访问状态，并输出顶点数据 vertex_status[pos] = 1;printf("%d ",vertex_arr[pos]);// 查找下一个邻接点，调用dfsint i;for(i=0;i

5、main函数调用

int main()
{int res = create_graph();if(res == -1){return -1;}print_graph();	dfs_start();return 0;
}

执行结果：

 

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：恒生指数开盘微涨0.01%，恒生科技指数涨0.52% 恒生科技指数开盘涨0.06% 恒生指数开盘涨1.98%

下一篇：微信小程序第三节 —— 页面跳转的那些事儿

相关内容

热门资讯

“光伏第一股”跳闸了 光伏一送... 打不完的官司，还不完的债，谁来接盘亿晶光电这个烫手的山芋。文/每日资本论常州的梅雨季节又闷又热，但对...
QDII投资额度持续放宽，“港... 随着年内QDII（合格境内机构投资者）投资额度持续放宽，叠加港股市场结构性反弹，境内资金布局港股资产...
科达自控拟收购海图科技控股权，... 6月27日晚间，科达自控披露公告称，公司拟以现金受让海图科技2550万股股份，占海图科技股本总额的比...
机构看好A股，“稳中向好”态势... 外部风险缓和叠加稳增长政策持续发力，上周A股市场情绪显著回暖，上证指数创下今年以来新高。盘面上，新兴...
苹果更新欧洲App Store... 【TechWeb】苹果公司于当地时间周四宣布修改其欧洲应用商店App Store的政策，此举旨在避免...
美国与G7成员达成协议 将建立... 美国和其他七国集团成员签署了一项旨在避免全球税收战的协议，提出建立“并行”体系，使美国公司免受现有全...
奇安信：近期中标港交所IT基础... 6月27日，奇安信在上证e互动平台回复投资者提问时表示，公司近期中标港交所IT基础设施安全评估项目，...
蔡澜助理发文，回应蔡澜遗产分配... 近日，美食家、专栏作家、电视节目主持人蔡澜逝世，享年83岁。6月29日，蔡澜助理杨翱发帖表示，近期网...
每天不间断交易！南方区域电力市... 6月28日，南方区域电力市场连续结算试运行启动会在广州召开。经过长达35个月的前期准备和12轮的短期...
“深夜AI轰炸”消费者起诉获赔... [ 《民法典》第1033条规定，不得以电话、短信等方式侵扰他人的私人生活安宁。同时，第496条对银行...
“这次有点不一样”！直击浦发银... 6月27日，浦发银行2024年年度股东会在上海如期举行。该行党委书记、董事长张为忠，党委副书记、行长...
四维智联向港交所提交上市申请 据雷峰网《新智驾》获悉，2025年6月27日，智能座舱解决方案提供商四维智联（AUTO AI）正式向...
中国联合国采购促进会国际专家工... 2025 年 6 月上旬，中国联合国采购促进会国际专家工作委员会顾问/可持续发展委员会常务副主任李继...
财经调查丨舞蹈培训假证书真圈钱... （央视财经《财经调查记者输入“少儿舞蹈考级”“社会艺术水平考级”等关键词后，网络上瞬间涌现大量信息。...
有色板块走势强劲 电工合金、北... 有色板块27日盘中走势强劲，截至发稿，电工合金、中孚实业、北方铜业等涨停，锡业股份、江西铜业涨约6%...
茅台新加坡经销商：不以降价为噱... 近来茅台经销商的日子不好过。茅台年度股东大会刚落幕，国内散飞批发价就跌破2000元关口，在刚过去的“...
挂牌！山姆新店4.3万㎡，5.... 作为山姆第50家的广东东莞寮步店，开业一直备受关注，成为山姆会员商店中名列前茅的门店，备受关注的东莞...
上海家化董事长林小海：聚焦六神... 21世纪经济报道记者朱艺艺 上海报道近日，上海家化（600315.SH）在位于上海市虹口区的公司总部...
朱共山最近家有喜事：刚签约蚂蚁... 6月29日，协鑫能科（002015）与沙电投资(上海)有限公司（简称：沙电投资）在苏州签署战略合作协...
特朗普施压！数字税不许收，加拿... 一场意外的较量即将在全球经济舞台上拉开序幕。美国与加拿大，这两个常常在众人视线之外默默互动的国家，如...
祥源文旅跌0.51%，成交额1... 6月27日，祥源文旅跌0.51%，成交额1.75亿元，换手率3.39%，总市值82.78亿元。 异动...
开设50个本科专业！广州应用科... 撰文丨李帆 李凯平近日，广州应用科技学院正式公布2025年夏季普通高考招生计划，计划招生7452人，...
被证监会点名警告后，江苏老板临... 早不走，晚不走，就在被证监会点名警告后，江苏老板汪坤带着妻子，套现7.7亿安全撤离了。近日，上市公司...
一财社论：优化资本市场风险警示... 市场期待A股风险警示和管控不再是简单的交易阻断。27日，上证所、深交所就调整主板风险警示股票价格涨跌...
下周A股解禁超810亿元，这4... Wind数据显示，下周A股市场将有68只股票面临解禁，合计解禁数量为31.65亿股，按最新收盘价计算...
前5月工业企业利润总额2.7万... 本报讯（记者 赵语涵）国家统计局昨天发布工业效益月度报告。1至5月，全国规模以上工业企业实现利润总额...
800亿蔡崇信，选秀夜震动NB... 来源：视觉中国撰文丨马小雨 鄢子为 编辑丨鄢子为蔡崇信，刷新NBA联盟的纪录。6月下旬，他旗下的布鲁...
连续三年亏损的锦盛新材因信息披... 2025年6月27日晚锦盛新材（300849）发布公告称，收到中国证券监督管理委员会（以下简称“证监...
被诺和诺德抛弃的网红药房 诺和... 出品 | 虎嗅科技医疗组作者 | 陈广晶编辑 | 苗正卿头图 | AI生成诺和诺德导演了一场双输的剧...
原创 2... 向投资者明确指出，数字货币的市场走势远未到达终点！ 然而，接下来的领涨先锋将不再是恒宝和四方，而是那...