请用C语言写一个用户输入有向图的邻接矩阵,输出两种遍历方式的代码
时间: 2024-03-28 14:38:30 浏览: 64
好的,下面是用户输入有向图的邻接矩阵的代码:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 100
int main() {
int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = {0};
int vertex_num, edge_num;
printf("请输入有向图的顶点数和边数:\n");
scanf("%d%d", &vertex_num, &edge_num);
printf("请输入每条边的起点和终点:\n");
int start, end;
for (int i = 0; i < edge_num; i++) {
scanf("%d%d", &start, &end);
matrix[start][end] = 1;
}
printf("该有向图的邻接矩阵为:\n");
for (int i = 0; i < vertex_num; i++) {
for (int j = 0; j < vertex_num; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
return 0;
}
```
下面是两种遍历方式的代码,分别是深度优先遍历和广度优先遍历:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
int visited[MAX_VERTEX_NUM] = {0};
typedef struct {
int data[MAX_VERTEX_NUM];
int front, rear;
} Queue;
void initQueue(Queue *queue) {
queue->front = queue->rear = 0;
}
int isEmptyQueue(Queue *queue) {
return queue->front == queue->rear;
}
void enQueue(Queue *queue, int value) {
queue->data[queue->rear++] = value;
}
int deQueue(Queue *queue) {
return queue->data[queue->front++];
}
void DFS(int matrix[][MAX_VERTEX_NUM], int vertex_num, int start) {
printf("%d ", start);
visited[start] = 1;
for (int i = 0; i < vertex_num; i++) {
if (matrix[start][i] && !visited[i]) {
DFS(matrix, vertex_num, i);
}
}
}
void BFS(int matrix[][MAX_VERTEX_NUM], int vertex_num, int start) {
Queue queue;
initQueue(&queue);
printf("%d ", start);
visited[start] = 1;
enQueue(&queue, start);
while (!isEmptyQueue(&queue)) {
int current = deQueue(&queue);
for (int i = 0; i < vertex_num; i++) {
if (matrix[current][i] && !visited[i]) {
printf("%d ", i);
visited[i] = 1;
enQueue(&queue, i);
}
}
}
}
int main() {
int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = {0};
int vertex_num, edge_num;
printf("请输入有向图的顶点数和边数:\n");
scanf("%d%d", &vertex_num, &edge_num);
printf("请输入每条边的起点和终点:\n");
int start, end;
for (int i = 0; i < edge_num; i++) {
scanf("%d%d", &start, &end);
matrix[start][end] = 1;
}
printf("该有向图的邻接矩阵为:\n");
for (int i = 0; i < vertex_num; i++) {
for (int j = 0; j < vertex_num; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
printf("该有向图的深度优先遍历结果为:\n");
for (int i = 0; i < vertex_num; i++) {
if (!visited[i]) {
DFS(matrix, vertex_num, i);
}
}
printf("\n");
for (int i = 0; i < vertex_num; i++) {
visited[i] = 0;
}
printf("该有向图的广度优先遍历结果为:\n");
for (int i = 0; i < vertex_num; i++) {
if (!visited[i]) {
BFS(matrix, vertex_num, i);
}
}
printf("\n");
return 0;
}
```
以上代码可能存在一些细节问题,但是基本思路应该是没有问题的。
阅读全文