一、深度优先与广度优先遍历 从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visited[i]，未访问时值为false，访问一次后就改为true。 图的遍历分为深度优先遍历和广度优先遍历两种方法，两者的时间效率都是O(n*n)。 1.深度优先遍历 深度优先遍历与深搜DFS相似，从一个点A出发，将这个点标为已访问visited[i]:=true;，然后再访问所有与之相连，且未被访问过的点。当A的所有邻接点都被访问过后，再退回到A的上一个点（假设是B），再从B的另一个未被访问的邻接点出发，继续遍历。 下面给出的深度优先遍历的参考程序，假设图以邻接表存储 void dfs(int i) //图用数组模拟邻接表存储，访问点i { visited[i] = true; //标记为已经访问过 for (int j = 1; j <= num[i]; j++) //遍历与i相关联的所有未访问过的顶点 if (!visited[g[i][j]]) dfs(g[i][j]); }
主程序如下: int main() { …… memset(visited,false,sizeof(visited)); for (int i = 1; i <= n; i++) //每一个点都作为起点尝试访问，因为不是从任何 //一点开始都能遍历整个图 if (!visited[i]) dfs(i); …… return 0; } 2.广度优先遍历 广度优先遍历并不常用，从编程复杂度的角度考虑，通常采用的是深度优先遍历。 广度优先遍历和广搜BFS相似，因此使用广度优先遍历一张图并不需要掌握什么新的知识，在原有的广度优先搜索的基础上，做一点小小的修改，就成了广度优先遍历算法。
二、一笔画问题 如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。 我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有以下两个定理。 定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点。 定理2：存在欧拉回路的条件：图是连通的，有0个奇点。 两个定理的正确性是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点外，每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去次数一定都是相等的，显然没有奇点。 求欧拉路的算法很简单，使用深度优先遍历即可。 根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行DFS，时间复杂度为O(m+n)，m为边数，n是点数。 #include #include using namespace std; #define maxn 101 int g[maxn][maxn]; //此图用邻接矩阵存储 int du[maxn]; //记录每个点的度，就是相连的边的数目 int circuit[maxn]; //用来记录找到的欧拉路的路径 int n,e,circuitpos,i,j,x,y,start; void find_circuit(int i) //这个点深度优先遍历过程寻找欧拉路 { int j; for (j = 1; j <= n; j++) if (g[i][j] == 1) //从任意一个与它相连的点出发 { g[j][i] = g[i][j] = 0; find_circuit(j); } circuit[++circuitpos] = i; //记录下路径 } int main() { memset(g,0,sizeof(g)); cin >> n >> e; for (i = 1; i <= e; i++) { cin >> x >> y; g[y][x] = g[x][y] = 1; du[x]++; //统计每个点的度 du[y]++; } start = 1; //如果有奇点，就从奇点开始寻找，这样找到的就是 for (i = 1; i <= n; i++) //欧拉路。没有奇点就从任意点开始， if (du[i]%2 == 1) //这样找到的就是欧拉回路。(因为每一个点都是偶点) start = i; circuitpos = 0; find_circuit(start); for (i = 1; i <= circuitpos; i++) cout << circuit[i] << ’ '; cout << endl; return 0; }
三、哈密尔顿环 欧拉回路是指不重复地走过所有路径的回路，而哈密尔顿环是指不重复地走过所有的点，并且最后还能回到起点的回路。 使用简单的深度优先搜索，就能求出一张图中所有的哈密尔顿环。 #include #include using namespace std; int start,length,x,n; bool visited[101],v1[101]; int ans[101], num[101]; int g[101][101]; void print() { int i; for (i = 1; i <= length; i++) cout << ’ ’ << ans[i]; cout << endl; } void dfs(int last,int i) { visited[i] = true; //标记为已经访问过 v1[i] = true; //标记为已在一张图中出现过 ans[++length] = i; //记录下答案 for (int j = 1; j <= num[i]; j++) { if (g[i][j]==x&&g[i][j]!=last) //回到起点，构成哈密尔顿环 { ans[++length] = g[i][j]; print(); //这里说明找到了一个环，则输出ans数组。 length–; break; } if (!visited[g[i][j]]) dfs(i,g[i][j]); } length–; visited[i] = false； } int main() { memset(visited,false,sizeof(visited)); memset(v1,false,sizeof(v1)); for (x = 1; x <= n; x++) //每一个点都作为起点尝试访问，因为不是从任何一点开始都能找过整个图的 if (!v1[x]) //如果点x不在之前曾经被访问过的图里。 { length = 0; //定义一个ans数组存答案，length记答案的长度。 dfs(x); } return 0; }
