大家好，又见面了，我是你们的朋友全栈君。
图遍历问题分为四类
遍历完所有的边而不能有重复，即所謂“一笔画问题”或“欧拉路径”；
遍历完所有的顶点而没有重复，即所谓“哈密尔顿问题”。
遍历完所有的边而可以有重复，即所谓“中国邮递员问题”；
遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。
对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。
第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密尔顿图的性质。
图的基本知识
顶点:图中的数据元素称为顶点
有向图:有方向的图叫有向图
无向图:没有方向的图叫无线图
完全图:有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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/135585.html原文链接：https://javaforall.net
