用c语言编写一个拥有菜单的系统,功能包括: (1)定义图的邻接矩阵 (2)深度优先遍历 (3)广度优先遍历
时间: 2024-01-08 18:01:52 浏览: 27
好的,以下是一个简单的用C语言编写的图的邻接矩阵、深度优先遍历和广度优先遍历的系统:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 10
// 邻接矩阵表示法
typedef struct Graph {
int vertex[MAX_SIZE]; // 顶点数组
int edge[MAX_SIZE][MAX_SIZE]; // 边的二维数组
int vertex_num; // 顶点数
int edge_num; // 边数
} Graph;
// 初始化图
void initGraph(Graph *g) {
printf("请输入顶点数:");
scanf("%d", &g->vertex_num);
printf("请输入边数:");
scanf("%d", &g->edge_num);
printf("请输入顶点的值:\n");
for (int i = 0; i < g->vertex_num; i++) {
scanf("%d", &g->vertex[i]);
}
printf("请输入边的信息(格式:a, b):\n");
for (int i = 0; i < g->edge_num; i++) {
int a, b;
scanf("%d, %d", &a, &b);
g->edge[a][b] = 1;
g->edge[b][a] = 1; // 无向图
}
}
// 深度优先遍历
void dfs(Graph g, int v, bool visited[]) {
visited[v] = true;
printf("%d ", g.vertex[v]);
for (int i = 0; i < g.vertex_num; i++) {
if (g.edge[v][i] == 1 && !visited[i]) {
dfs(g, i, visited);
}
}
}
void depthFirstSearch(Graph g) {
bool visited[MAX_SIZE] = {false};
printf("深度优先遍历的结果为:");
for (int i = 0; i < g.vertex_num; i++) {
if (!visited[i]) {
dfs(g, i, visited);
}
}
printf("\n");
}
// 广度优先遍历
void breadthFirstSearch(Graph g, int v, bool visited[]) {
int queue[MAX_SIZE];
int front = 0, rear = 0;
queue[rear++] = v;
visited[v] = true;
while (front < rear) {
int cur = queue[front++];
printf("%d ", g.vertex[cur]);
for (int i = 0; i < g.vertex_num; i++) {
if (g.edge[cur][i] == 1 && !visited[i]) {
queue[rear++] = i;
visited[i] = true;
}
}
}
}
void breadthFirstSearch(Graph g) {
bool visited[MAX_SIZE] = {false};
printf("广度优先遍历的结果为:");
for (int i = 0; i < g.vertex_num; i++) {
if (!visited[i]) {
breadthFirstSearch(g, i, visited);
}
}
printf("\n");
}
int main() {
Graph g;
initGraph(&g);
depthFirstSearch(g);
breadthFirstSearch(g);
return 0;
}
```
这个系统可以让用户输入图的顶点数和边数,然后让用户输入每个顶点的值和每条边的信息。接着,它会使用邻接矩阵表示法来存储图,并实现深度优先遍历和广度优先遍历。