用C语言写一个用户输入有向图邻接矩阵,输出该有向图的两种遍历方式.并写出示例
时间: 2024-03-20 15:39:41 浏览: 68
有向图的邻接表遍历(c语言)
4星 · 用户满意度95%
好的,我来回答您的问题。
下面是用C语言实现用户输入有向图邻接矩阵,输出该有向图的两种遍历方式的代码:
```c
#include <stdio.h>
#define MAX_SIZE 10
int graph[MAX_SIZE][MAX_SIZE]; // 邻接矩阵
int visited[MAX_SIZE]; // 记录是否被访问过的数组
int queue[MAX_SIZE]; // 队列,用于广度优先遍历
// 深度优先遍历
void dfs(int vertex, int n) {
int i;
visited[vertex] = 1;
printf("%d ", vertex);
for (i = 0; i < n; i++) {
if (graph[vertex][i] && !visited[i]) {
dfs(i, n);
}
}
}
// 广度优先遍历
void bfs(int start, int n) {
int i, front = 0, rear = 0;
printf("%d ", start);
visited[start] = 1;
queue[rear++] = start;
while (front != rear) {
int vertex = queue[front++];
for (i = 0; i < n; i++) {
if (graph[vertex][i] && !visited[i]) {
visited[i] = 1;
printf("%d ", i);
queue[rear++] = i;
}
}
}
}
int main() {
int n, i, j;
printf("请输入有向图的顶点数:");
scanf("%d", &n);
printf("请输入有向图的邻接矩阵:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
printf("深度优先遍历结果:");
for (i = 0; i < n; i++) {
visited[i] = 0;
}
for (i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, n);
}
}
printf("\n广度优先遍历结果:");
for (i = 0; i < n; i++) {
visited[i] = 0;
}
bfs(0, n);
return 0;
}
```
以下是示例程序的运行结果:
```
请输入有向图的顶点数:5
请输入有向图的邻接矩阵:
0 1 0 0 0
0 0 1 1 0
0 0 0 0 1
0 0 0 0 1
0 0 0 0 0
深度优先遍历结果:0 1 2 3 4
广度优先遍历结果:0 1 2 3 4
```
在示例中,我们输入了一个5个顶点的有向图的邻接矩阵,然后进行了深度优先遍历和广度优先遍历,输出了它们的遍历结果。
阅读全文