图的遍历-c语言

图的遍历

问题描述

分析

代码实现（dfs）

#include <stdio.h>
int e[101][101],book[101];//e为存储图的邻接矩阵表示法的二维数组，book为图中的点
int n, m,sum;//sum表示顶点数
//n为顶点数，m是边的个数

void dfs(int x) {//x为当前所在顶点的编号
	int i;
	//if(book[x]==1)
	printf("%d ", x);
	sum++;//每访问一个顶点sum就加1
	if (sum == n)//如果所有定点都遍历到了
		return;
	for (i = 1; i <= n; i++) {
		if (e[x][i] == 1 && book[i] == 0) {
			book[i] = 1;
			dfs(i);
		}
	}
	//book[x] = 0;
	return;
	
}
int main() {
	int i, a,b;
	scanf_s("%d %d", &n, &m);
	//m是用来告诉程序要输入几条边的
	for (i = 1; i <= m; i++) {//i<=m
		scanf_s("%d %d", &a, &b);
		e[a][b] = 1;
		e[b][a] = 1;//因为邻接矩阵表示法是沿对角线对称的
	}
	book[1] = 1;
	dfs(1);
	getchar(); getchar();
	return 0;
}

图的表示方法：邻接矩阵表示法

输入

5 5
1 2
1 3
1 5
2 4
3 5

输出

1 2 4 3 5

总结

代码实现（bfs）

#include <stdio.h>

int main() {
	int a[51][51];//邻接矩阵表示法的二维数组
	int book[100] = {0};//做标记，表示这个点已经遍历过了。一定要初始化！！
	int i, j, n, m,c,b,tail,head,cur;
	int que[100];//把遍历的点按顺序记下来
	scanf_s("%d %d", &n, &m);//n表示几个点，m表示几条边
	//循环输入m条边到二维数组
	for (i = 1; i <= m; i++) {
		scanf_s("%d %d", &c, &b);
		a[c][b] = 1;
		a[b][c] = 1;
	}
	//初始化记录的数组
	tail = 1;
	head = 1;
	que[tail] = 1;//从编号1开始，将1号顶点加入队列
	tail++;//队尾变化
	book[1] = 1;//对1进行标记
	//当队列不为空时
	while (head < tail) {
		cur = que[head];//记录当前正在遍历的顶点号
		for (i = 1; i <= n; i++) {//从1~n依次尝试
			
				//如果有边且未标记  
				if (a[cur][i]==1 && book[i] == 0) {
					//入队，并标记
					book[i] = 1;
					que[tail] = i;
					tail++;//队尾变化
				}
				if (tail > n)//如果所有顶点都遍历到了就结束
					break;
			
		}
		head++;
	}
	for (i = 1; i <= n; i++)
		printf("%d ", que[i]);
	getchar(); getchar();
	return 0;
}

输入

5 5
1 2
1 3
1 5
2 4
3 5

输出

1 2 3 5 4