数据结构练习：深度优先遍历（DFS）和广度优先遍历（BFS）（顺序存储结构）

深度优先遍历（DFS）

#define _CRT_SECURE_NO_WARNINGS
#include
#define MaXInt 32767 //最大权值,代表无穷大
#define MVNum 10	//最大顶点数

//定义图的结构体
typedef struct {
	//顶点数组
	char vex[MVNum];
	//边数组(邻接矩阵)
	int edge[MVNum][MVNum];
	//顶点数，边数
	int vexnum, edgenum;
}Graph;

//辅助数组(标记已被访问过的顶点)
int visited[MVNum];
//初始化辅助数组,数字0代表此顶点未被访问过
void init_visited(Graph *G) {
	for (int i = 0; i < G->vexnum; i++)
	{
		visited[i] = 0;
	}
}


//创建图
void CreateGraph(Graph *G) {
	//初始化总顶点数和总边数
	G->vexnum = 0;
	G->edgenum = 0;
	printf("请输入图的总顶点数和总边数:");
	//输入图的总顶点数和总边数
	scanf("%d %d", &G->vexnum, &G->edgenum);

	

	//输入顶点信息
	for (int i = 0; i < G->vexnum; i++)
	{	
		char v;
		printf("请输入第%d顶点信息:",i+1);
		scanf(" %c", &v);
		G->vex[i] = v;
	}
	printf("输入完成!n");

	

	//初始化邻接矩阵，边的权值
	for (int i = 0; i < G->vexnum; i++){
		for (int j = 0; j < G->vexnum; j++)
		{
			G->edge[i][j] = MaXInt;
		}
	}

	//输入边信息
	int i, j;
	//构造邻接矩阵(输入两个顶点在vex数组中的下标，如果置为1则表示此两点中有边)
	printf("请输入两个顶点(两点间有边)的下标:");
	scanf("%d %d", &i, &j);
	while (i!=-1 && j!=-1)	//循环结束条件
	{
		G->edge[i][j] = 1;
		G->edge[j][i] = 1;	//无向图的邻接矩阵为对称矩阵
		scanf("%d %d", &i, &j);
	}
	
}

//DFS遍历(从下标为v的顶点开始遍历图)
void DFS(Graph *G,int v) {
	 //输出当前第i个顶点
	 printf("%c",G->vex[v]);
	 //将第i个顶点的标志置为已经遍历
	 visited[v] = 1;//表示已经访问过此顶点
	 //循环从i顶点到各个顶点（j）
	 for (int i = v; i < G->vexnum; i++){
		 for (int j = 0; j < G->vexnum; j++)
		 {
			 //循环中判断i和j顶点间是否有边，并且j顶点也没标记过
			 if (G->edge[i][j] == 1 && !visited[j]) {	//检查到v_i和v_j之间有边
				 //调用dfs;将当前顶点作为下次遍历的起点
				 DFS(G, j);	//跳到v_j所在行开始遍历
			 }	
		 }
	 }
}


//主函数
int main() {
	//定义图
	Graph G;
	//初始化辅助数组
	init_visited(&G);
	//创建图
	CreateGraph(&G);
	//遍历邻接矩阵(每一行换行)
	for (int i = 0; i < G.vexnum; i++){
		for (int j = 0; j < G.vexnum; j++)
		{
			printf("%d ",G.edge[i][j]);
		}
		printf("n");
	}
	printf("深度优先遍历结果:");
	//从第1个顶点开始遍历
	DFS(&G, 0);
	return 0;
}

此例的深度优先遍历详细过程

运行结果：

广度优先遍历（BFS）

#define _CRT_SECURE_NO_WARNINGS
#include
#define MVNum 10	//最大顶点数
#define QSize 10

//定义图的结构体
typedef struct {
	//顶点数组
	char vex[MVNum];
	//边数组(邻接矩阵)
	int edge[MVNum][MVNum];
	//顶点数，边数
	int vexnum, edgenum;
}Graph;


typedef struct Queue {
	char data[QSize];
	int front, rear;
}SeqQueue;
//队列顺序存储
//初始化队列
void InitQueue(SeqQueue *Q) {
	Q->front = 0;
	Q->rear = 0;
}
//入队操作
int EnQueue(SeqQueue Q, char e) {
	//判断队满
	if ((Q.rear + 1) % QSize == Q.front)
		return 0;
	//将新元素从队尾入队
	Q.data[Q.rear] = e;
	//队尾指针改变
	Q.rear = (Q.rear + 1) % QSize;	//防止假溢出
	return 1;
}
//出队操作
int DeQueue(SeqQueue Q, char* e) {
	//判断队空
	if (Q.front == Q.rear)
		return 0;
	*e = Q.data[Q.front];	//用e接收队头元素
	//队头指针改变
	Q.front = (Q.front + 1) % QSize;
	return 1;
}


//辅助数组(标记已被访问过的顶点)
int visited[MVNum];
//初始化辅助数组
void init_visited(Graph* G) {
	for (int i = 0; i < G->vexnum; i++)
	{
		visited[i] = 0;
	}
}


//创建图
void CreateGraph(Graph* G) {
	//初始化总顶点数和总边数
	G->vexnum = 0;
	G->edgenum = 0;
	printf("请输入图的总顶点数和总边数:");
	//输入图的总顶点数和总边数
	scanf("%d %d", &G->vexnum, &G->edgenum);

	

	//输入顶点信息
	for (int i = 0; i < G->vexnum; i++)
	{
		char v;
		printf("请输入第%d顶点信息:", i + 1);
		scanf(" %c", &v);
		G->vex[i] = v;
	}
	printf("输入完成!n");

	

	//初始化邻接矩阵，边的权值
	for (int i = 0; i < G->vexnum; i++) {
		for (int j = 0; j < G->vexnum; j++)
		{
			G->edge[i][j] = 0;
		}
	}

	//输入边信息
	int i, j;
	//构造邻接矩阵(输入两个顶点在vex数组中的下标，如果置为1则表示此两点中有边)
	printf("请输入两个顶点(两点间有边)的下标:");
	scanf("%d %d", &i, &j);
	while (i != -1 && j != -1)
	{
		G->edge[i][j] = 1;
		G->edge[j][i] = 1;
		scanf("%d %d", &i, &j);
	}

}

//广度优先遍历
void BFS(Graph G) {

	//接收出队顶点
	char e;
	//定义队列
	SeqQueue Q;
	//初始化队列
	InitQueue(&Q);
	//遍历邻接矩阵
	for (int i = 0; i < G.vexnum; i++)
	{
		//如果该顶点未被访问过，则打印该顶点
		if (!visited[i])
		{
			//打印该顶点
			printf("%c", G.vex[i]);
			//打印后代表该顶点被访问过，将此顶点在辅助数组中的标志置1
			visited[i] = 1;
			//将该顶点入队
			EnQueue(Q, G.vex[i]);
			//判断队空
			while (Q.front!=Q.rear)
			{
				//出队
				DeQueue(Q, &e);
				for (int  j = 0; j < G.vexnum; j++)
				{
					//邻接矩阵某顶点v_i和v_j间有边，且v_j未被访问过，打印v_j(v_i的邻接点)
					if (G.edge[i][j]==1 && !visited[j])
					{
						//打印v_i的邻接点v_j
						printf("%c", G.vex[j]);
						//打印v_j后，该顶点被访问过
						visited[j] = 1;
						//将v_i的邻接点v_j入队
						EnQueue(Q,G.vex[j]);
					}
				}

			}
		}
	}
}


//主函数
int main() {
	//定义图
	Graph G;
	//初始化辅助数组
	init_visited(&G);
	
	//创建图
	CreateGraph(&G);
	//遍历邻接矩阵(每一行换行)
	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++)
		{
			printf("%d ", G.edge[i][j]);
		}
		printf("n");
	}
	printf("广度优先遍历结果:");
	//从第1个顶点开始遍历
	BFS(G);
	return 0;
}

运行结果