请使用C语言基于邻接矩阵存储结构构建带权无向图,输出其深度遍历序列和广度遍历序列。 【输入形式】 输入数据有多行,首行m和n,表示图有m个顶点和n条边;第二行是m个顶点名称,中间空格分隔;之后为n条边,表示形式为:起点名称 终点名称 权值;最后一行为遍历的起点名称。 【输出形式】 输出数据有两行,首行为深度遍历序列,末行为广度遍历序列。 【样例输入】 4 5 A B C D A B 5 A C 2 A D 1 B C 4 C D 6 A 【样例输出】 A B C D A B C D
时间: 2024-02-01 18:16:53 浏览: 75
邻接表或者邻接矩阵为存储结构实现连通无向图的深度优先和广度优先遍历
3星 · 编辑精心推荐
以下是基于邻接矩阵存储结构的带权无向图的深度遍历和广度遍历的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_VERTEX_NUM 50
typedef struct {
char name; // 顶点名称
} VertexType;
typedef struct {
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵,存储边的权值
int vexNum, arcNum; // 图的顶点数和边数
VertexType vexs[MAX_VERTEX_NUM]; // 存储顶点的数组
} MGraph;
// 初始化图
void initGraph(MGraph *G) {
int i, j;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
for (j = 0; j < MAX_VERTEX_NUM; j++) {
G->edges[i][j] = 0;
}
}
G->vexNum = 0;
G->arcNum = 0;
}
// 向图中添加一个顶点
void addVertex(MGraph *G, char name) {
G->vexs[G->vexNum].name = name;
G->vexNum++;
}
// 向图中添加一条边
void addEdge(MGraph *G, char start, char end, int weight) {
int i, j;
for (i = 0; i < G->vexNum; i++) {
if (G->vexs[i].name == start) {
break;
}
}
for (j = 0; j < G->vexNum; j++) {
if (G->vexs[j].name == end) {
break;
}
}
G->edges[i][j] = weight;
G->edges[j][i] = weight;
G->arcNum++;
}
// 深度优先遍历
void dfs(MGraph *G, int v, bool *visited) {
int i;
printf("%c ", G->vexs[v].name);
visited[v] = true;
for (i = 0; i < G->vexNum; i++) {
if (G->edges[v][i] != 0 && !visited[i]) {
dfs(G, i, visited);
}
}
}
// 广度优先遍历
void bfs(MGraph *G, int v, bool *visited) {
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
int i, j, k;
printf("%c ", G->vexs[v].name);
visited[v] = true;
queue[rear++] = v;
while (front != rear) {
i = queue[front++];
for (j = 0; j < G->vexNum; j++) {
if (G->edges[i][j] != 0 && !visited[j]) {
printf("%c ", G->vexs[j].name);
visited[j] = true;
queue[rear++] = j;
}
}
}
}
int main() {
MGraph G;
initGraph(&G);
int m, n, i, j, k, weight;
char start, end, begin;
bool visited[MAX_VERTEX_NUM];
// 读入顶点和边
scanf("%d%d", &m, &n);
for (i = 0; i < m; i++) {
char name;
scanf(" %c", &name);
addVertex(&G, name);
}
for (i = 0; i < n; i++) {
scanf(" %c %c %d", &start, &end, &weight);
addEdge(&G, start, end, weight);
}
// 读入遍历的起点
scanf(" %c", &begin);
// 初始化visited数组
for (i = 0; i < G.vexNum; i++) {
visited[i] = false;
}
// 深度优先遍历
for (i = 0; i < G.vexNum; i++) {
if (G.vexs[i].name == begin) {
dfs(&G, i, visited);
break;
}
}
printf("\n");
// 初始化visited数组
for (i = 0; i < G.vexNum; i++) {
visited[i] = false;
}
// 广度优先遍历
for (i = 0; i < G.vexNum; i++) {
if (G.vexs[i].name == begin) {
bfs(&G, i, visited);
break;
}
}
printf("\n");
return 0;
}
```
输入样例:
```
4 5
A B C D
A B 5
A C 2
A D 1
B C 4
C D 6
A
```
输出样例:
```
A B C D
A B C D
```
阅读全文