先依次输入无向图的顶点信息,再依次输入无向图的边信息,建立图的邻接矩阵存储结构并将其顶点向量和邻接矩阵打印输出,接下来在1中建立的无向图的邻接矩阵存储结构基础上使用递归法对图进行深度优先搜索遍历并输出顶点序列; 在1中建立的无向图邻接矩阵存储结构基础上 。最后对图进行广度优先搜索遍历并输出顶点序列。用C语言表述
时间: 2024-02-06 14:12:11 浏览: 69
好的,以下是您的问题的回答:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 顶点的最大个数
// 邻接矩阵存储结构
typedef struct {
char vexs[MAX_VERTEX_NUM]; // 存储图中的顶点信息
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储图中的边信息
int vexnum, arcnum; // 存储图中的顶点数和边数
} MGraph;
// 创建无向图的邻接矩阵存储结构
void CreateMGraph(MGraph *graph) {
int i, j, k, w;
printf("请输入无向图的顶点数:");
scanf("%d", &graph->vexnum);
printf("请输入无向图的边数:");
scanf("%d", &graph->arcnum);
// 初始化邻接矩阵
for (i = 0; i < graph->vexnum; i++) {
for (j = 0; j < graph->vexnum; j++) {
graph->arc[i][j] = 0;
}
}
// 输入顶点信息
printf("请输入无向图的顶点信息:\n");
for (i = 0; i < graph->vexnum; i++) {
printf("第%d个顶点:", i+1);
scanf(" %c", &graph->vexs[i]);
}
// 输入边信息
printf("请输入无向图的边信息:\n");
for (k = 0; k < graph->arcnum; k++) {
printf("输入边(vi, vj)上的下标i和下标j(用空格隔开):");
scanf("%d %d", &i, &j);
printf("输入边(vi, vj)的权重:");
scanf("%d", &w);
graph->arc[i][j] = w;
graph->arc[j][i] = w;
}
}
// 打印图的邻接矩阵存储结构
void PrintMGraph(MGraph graph) {
int i, j;
printf("图的顶点信息:");
for (i = 0; i < graph.vexnum; i++) {
printf("%c ", graph.vexs[i]);
}
printf("\n");
printf("图的邻接矩阵:\n");
for (i = 0; i < graph.vexnum; i++) {
for (j = 0; j < graph.vexnum; j++) {
printf("%d ", graph.arc[i][j]);
}
printf("\n");
}
}
// 深度优先搜索遍历图
void DFS(MGraph *graph, int v, int *visited) {
int i;
visited[v] = 1;
printf("%c ", graph->vexs[v]);
for (i = 0; i < graph->vexnum; i++) {
if (graph->arc[v][i] && !visited[i]) {
DFS(graph, i, visited);
}
}
}
// 对图进行深度优先搜索遍历
void DFSTraverse(MGraph *graph) {
int i;
int visited[MAX_VERTEX_NUM] = {0};
printf("深度优先搜索遍历顶点序列:");
for (i = 0; i < graph->vexnum; i++) {
if (!visited[i]) {
DFS(graph, i, visited);
}
}
printf("\n");
}
// 广度优先搜索遍历图
void BFS(MGraph *graph, int v, int *visited, int *queue, int *front, int *rear) {
int i, j;
visited[v] = 1;
printf("%c ", graph->vexs[v]);
queue[++*rear] = v;
while (*front <= *rear) {
i = queue[(*front)++];
for (j = 0; j < graph->vexnum; j++) {
if (graph->arc[i][j] && !visited[j]) {
visited[j] = 1;
printf("%c ", graph->vexs[j]);
queue[++*rear] = j;
}
}
}
}
// 对图进行广度优先搜索遍历
void BFSTraverse(MGraph *graph) {
int i;
int visited[MAX_VERTEX_NUM] = {0};
int queue[MAX_VERTEX_NUM];
int front = 0, rear = -1;
printf("广度优先搜索遍历顶点序列:");
for (i = 0; i < graph->vexnum; i++) {
if (!visited[i]) {
BFS(graph, i, visited, queue, &front, &rear);
}
}
printf("\n");
}
int main() {
MGraph graph;
CreateMGraph(&graph);
PrintMGraph(graph);
DFSTraverse(&graph);
BFSTraverse(&graph);
return 0;
}
```
注意,由于您要求不透露您的要求,因此我并不知道您的具体需求。如果以上回答不符合您的要求,请您再次告诉我您的需求,我会尽力帮助您。
阅读全文