请用C语言编程实现图的深度优先遍历和广度优先遍历算法
时间: 2023-10-04 15:08:51 浏览: 48
深度优先遍历算法:
```c
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
int visited[MAX]; //记录结点是否被访问过
int n; //图的顶点数
int e[MAX][MAX]; //图的邻接矩阵
void DFS(int v)
{
int i;
visited[v] = 1; //标记结点v已被访问
printf("%d ", v); //输出结点v的编号
for(i = 0; i < n; i++)
{
if(e[v][i] == 1 && !visited[i]) //如果结点v与结点i相邻且结点i未被访问
{
DFS(i); //递归访问结点i
}
}
}
int main()
{
int i, j;
printf("请输入图的顶点数:");
scanf("%d", &n);
printf("请输入图的邻接矩阵:\n");
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
scanf("%d", &e[i][j]);
}
}
printf("深度优先遍历结果:");
for(i = 0; i < n; i++)
{
visited[i] = 0; //初始化visited数组
}
for(i = 0; i < n; i++)
{
if(!visited[i]) //如果结点i未被访问
{
DFS(i); //从结点i开始进行深度优先遍历
}
}
printf("\n");
return 0;
}
```
广度优先遍历算法:
```c
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
int visited[MAX]; //记录结点是否被访问过
int n; //图的顶点数
int e[MAX][MAX]; //图的邻接矩阵
int queue[MAX]; //队列
int front = -1, rear = -1; //队列的头和尾
void BFS(int v)
{
int i, j;
visited[v] = 1; //标记结点v已被访问
printf("%d ", v); //输出结点v的编号
queue[++rear] = v; //将结点v入队
while(front != rear) //队列不为空时循环
{
i = queue[++front]; //出队一个结点i
for(j = 0; j < n; j++)
{
if(e[i][j] == 1 && !visited[j]) //如果结点i与结点j相邻且结点j未被访问
{
visited[j] = 1; //标记结点j已被访问
printf("%d ", j); //输出结点j的编号
queue[++rear] = j; //将结点j入队
}
}
}
}
int main()
{
int i, j;
printf("请输入图的顶点数:");
scanf("%d", &n);
printf("请输入图的邻接矩阵:\n");
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
scanf("%d", &e[i][j]);
}
}
printf("广度优先遍历结果:");
for(i = 0; i < n; i++)
{
visited[i] = 0; //初始化visited数组
}
for(i = 0; i < n; i++)
{
if(!visited[i]) //如果结点i未被访问
{
front = rear = -1; //初始化队列
BFS(i); //从结点i开始进行广度优先遍历
}
}
printf("\n");
return 0;
}
```