图遍历问题

图遍历问题图遍历问题分为四类遍历完所有的边而不能有重复,即所謂“一笔画问题”或“欧拉路径”;遍历完所有的顶点而没有重复,即所谓“哈密尔顿问题”。遍历完所有的边而可以有重复,即所谓“中国邮递员问题”;遍历完所有的顶点而可以重复,即所谓“旅行推销员问题”。对于第一和第三类问题已经得到了完满的解决,而第二和第四类问题则只得到了部分解决。第一类问题就是研究所谓的欧拉图的性质,而第二类问题则是…

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

图遍历问题分为四类

遍历完所有的边而不能有重复,即所謂“一笔画问题”或“欧拉路径”;

遍历完所有的顶点而没有重复,即所谓“哈密尔顿问题”。

遍历完所有的边而可以有重复,即所谓“中国邮递员问题”;

遍历完所有的顶点而可以重复,即所谓“旅行推销员问题”。

对于第一和第三类问题已经得到了完满的解决,而第二和第四类问题则只得到了部分解决。

第一类问题就是研究所谓的欧拉图的性质,而第二类问题则是研究所谓的哈密尔顿图的性质。

图的基本知识   

顶点:图中的数据元素称为顶点

有向图:有方向的图叫有向图

无向图:没有方向的图叫无线图

完全图:有n(n-1)/2条边的无向图称为完全图

有向完全图:具有n(n-1)条弧的有向图称为有向完全图

稀疏图:有很少条边或弧的图称为稀疏图,反之称为稠密图

权:与图的边或弧相关的数叫做权(weight)

例子1:

           图的深度遍历   

Time Limit: 1000MS   

Memory limit: 65536K

题目描述

请定一个无向图,顶点编号从0到n-1,用深度优先搜索(DFS),遍历并输出。遍历时,先遍历节点编号小的。

输入

输入第一行为整数n(0 < n < 100),表示数据的组数。 对于每组数据,第一行是两个整数k,m(0 < k < 100,0 < m < k*k),表示有m条边,k个顶点。 下面的m行,每行是空格隔开的两个整数u,v,表示一条连接u,v顶点的无向边。

输出

输出有n行,对应n组输出,每行为用空格隔开的k个整数,对应一组数据,表示DFS的遍历结果。

示例输入

1
4 4
0 1
0 2
0 3
2 3

示例输出

0 1 2 3
【】

 

转载于:https://www.cnblogs.com/Roni-i/p/8608569.html

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

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

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

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

(0)


相关推荐

发表回复

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

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