大家好,又见面了,我是你们的朋友全栈君。
图遍历问题分为四类
遍历完所有的边而不能有重复,即所謂“一笔画问题”或“欧拉路径”;
遍历完所有的顶点而没有重复,即所谓“哈密尔顿问题”。
遍历完所有的边而可以有重复,即所谓“中国邮递员问题”;
遍历完所有的顶点而可以重复,即所谓“旅行推销员问题”。
对于第一和第三类问题已经得到了完满的解决,而第二和第四类问题则只得到了部分解决。
第一类问题就是研究所谓的欧拉图的性质,而第二类问题则是研究所谓的哈密尔顿图的性质。
图的基本知识
顶点:图中的数据元素称为顶点
有向图:有方向的图叫有向图
无向图:没有方向的图叫无线图
完全图:有n(n-1)/2条边的无向图称为完全图
有向完全图:具有n(n-1)条弧的有向图称为有向完全图
稀疏图:有很少条边或弧的图称为稀疏图,反之称为稠密图
权:与图的边或弧相关的数叫做权(weight)
例子1:
图的深度遍历
Time Limit: 1000MS
Memory limit: 65536K
题目描述
输入
输出
示例输入
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账号...