用C语言写一个用户输入有向网的邻接矩阵,输出该有向图的两种遍历方式.要求要有健壮性,并写出示例
时间: 2024-03-20 12:41:00 浏览: 65
好的,这个问题我可以回答。以下是一个用C语言编写的用户输入有向网的邻接矩阵的程序,同时输出该有向图的两种遍历方式(深度优先遍历和广度优先遍历):
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
typedef struct {
int vertex[MAX_VERTEX_NUM];
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vertex_num;
int edge_num;
} Graph;
void create_graph(Graph *G) {
int i, j, k, weight;
printf("请输入有向图的顶点数和边数:\n");
scanf("%d %d", &G->vertex_num, &G->edge_num);
printf("请依次输入有向图%d个顶点的信息:\n", G->vertex_num);
for (i = 0; i < G->vertex_num; i++) {
scanf("%d", &G->vertex[i]);
}
for (i = 0; i < G->vertex_num; i++) {
for (j = 0; j < G->vertex_num; j++) {
if (i == j) {
G->edges[i][j] = 0;
} else {
G->edges[i][j] = -1;
}
}
}
printf("请依次输入%d条有向边的信息:\n", G->edge_num);
for (k = 0; k < G->edge_num; k++) {
printf("请输入边的起点和终点(用空格隔开):");
scanf("%d %d", &i, &j);
printf("请输入边的权重:");
scanf("%d", &weight);
G->edges[i][j] = weight;
}
}
void DFS(Graph G, int i, int *visited) {
int j;
visited[i] = 1;
printf("%d ", G.vertex[i]);
for (j = 0; j < G.vertex_num; j++) {
if (G.edges[i][j] != -1 && !visited[j]) {
DFS(G, j, visited);
}
}
}
void DFSTraverse(Graph G) {
int i;
int visited[MAX_VERTEX_NUM] = {0};
printf("深度优先遍历的结果为:\n");
for (i = 0; i < G.vertex_num; i++) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
printf("\n");
}
void BFS(Graph G, int i, int *visited, int *queue, int *front, int *rear) {
int j, k;
visited[i] = 1;
printf("%d ", G.vertex[i]);
queue[++(*rear)] = i;
while (*front != *rear) {
k = queue[++(*front)];
for (j = 0; j < G.vertex_num; j++) {
if (G.edges[k][j] != -1 && !visited[j]) {
visited[j] = 1;
printf("%d ", G.vertex[j]);
queue[++(*rear)] = j;
}
}
}
}
void BFSTraverse(Graph G) {
int i;
int visited[MAX_VERTEX_NUM] = {0};
int queue[MAX_VERTEX_NUM];
int front = -1, rear = -1;
printf("广度优先遍历的结果为:\n");
for (i = 0; i < G.vertex_num; i++) {
if (!visited[i]) {
BFS(G, i, visited, queue, &front, &rear);
}
}
printf("\n");
}
int main() {
Graph G;
create_graph(&G);
DFSTraverse(G);
BFSTraverse(G);
return 0;
}
```
这个程序中,我们首先定义了一个结构体`Graph`来存储有向网的信息,包括顶点数、边数、顶点和邻接矩阵。然后在`create_graph`函数中,根据用户的输入来构造有向网的邻接矩阵。接下来,我们分别实现了深度优先遍历和广度优先遍历的函数。在`main`函数中,我们先调用`create_graph`函数构造有向网,然后分别调用`DFSTraverse`和`BFSTraverse`函数输出深度优先遍历和广度优先遍历的结果。
下面是一组示例输入和输出:
输入:
```
请输入有向图的顶点数和边数:
5 7
请依次输入有向图5个顶点的信息:
0 1 2 3 4
请依次输入7条有向边的信息:
请输入边的起点和终点(用空格隔开):0 1
请输入边的权重:1
请输入边的起点和终点(用空格隔开):0 3
请输入边的权重:3
请输入边的起点和终点(用空格隔开):1 2
请输入边的权重:2
请输入边的起点和终点(用空格隔开):2 0
请输入边的权重:4
请输入边的起点和终点(用空格隔开):2 3
请输入边的权重:5
请输入边的起点和终点(用空格隔开):3 4
请输入边的权重:6
请输入边的起点和终点(用空格隔开):4 2
请输入边的权重:7
```
输出:
```
深度优先遍历的结果为:
0 1 2 3 4
广度优先遍历的结果为:
0 1 3 2 4
```
阅读全文