python/C++课程/待整理知识/啊哈算法/p131.cpp

#include <stdio.h>

int e[100][100], book[100], n, sum = 0;

void dfs(int cur) {//cur是当前顶点编号
	int i;
	printf("%d ", cur);
	sum++;//每访问一个顶点，sum就加一；
	// 边界
	if (sum == n) {//所有顶点都已经访问过则直接跳出
		return;
	}
	// 尝试每一步
	for (i = 1; i <=n; i++) {//从1号顶点到n号顶点依次进行尝试，看哪些顶点与当前顶点cur有边相连。
//	//判断当前顶点cur到顶点i是否有边，并且顶点i是否已访问过；
		if (e[cur][i] == 1 && book[i] == 0) {
			book[i] = 1;//标记顶点i已经访问过；
			dfs(i);//从顶点i再出发继续遍历；
		}
	}
	return;
}

int main() {
	int i, j, m, a, b;

	scanf("%d %d", &n, &m);
	//初始化二维矩阵；
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i == j) e[i][j] = 0;
			else e[i][j] = 999999;//相当于无穷大；

	// 二位数组是沿着主对角线对称，即无向图
	for (i = 1; i <= m; i++) {
		scanf("%d %d", &a, &b);
		e[a][b] = 1;
		e[b][a] = 1;//这里是无向图，所以需要将e[b][a]也赋值为1；
	}
//从1号顶点出发；
	book[1] = 1;//标记1号顶点已经访问过；
	dfs(1);//从1号顶点开始遍历；
	getchar();
	getchar();
	return 0;
}