C语言【问题描述】 请基于邻接矩阵存储结构构建带权无向图，输出其深度遍历序列和广度遍历序列。 【输入形式】 输入数据有多行，首行m和n，表示图有m个顶点和n条边；第二行是m个顶点名称，中间空格分隔；之后为n条边，表示形式为：起点名称 终点名称 权值；最后一行为遍历的起点名称。 【输出形式】 输出数据有两行，首行为深度遍历序列，末行为广度遍历序列。

以下是基于邻接矩阵存储结构的带权无向图的深度遍历和广度遍历的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_VERTEX_NUM 100

typedef struct {
    char name[20];   // 顶点名称
} VertexType;

typedef struct {
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
    int vexnum, arcnum;   // 顶点数和边数
    VertexType vexs[MAX_VERTEX_NUM];  // 顶点数组
} MGraph;

bool visited[MAX_VERTEX_NUM];  // 标记顶点是否被访问过
int path[MAX_VERTEX_NUM];  // 保存深度遍历路径
int pathIndex = 0;

// 初始化一个带权无向图
void InitGraph(MGraph* G) {
    int i, j;
    memset(G->edges, 0, sizeof(G->edges));  // 初始化邻接矩阵
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入%d个顶点名称，以空格分隔：", G->vexnum);
    for (i = 0; i < G->vexnum; i++) {
        scanf("%s", G->vexs[i].name);
    }
    char start[20], end[20];
    int weight;
    printf("请输入%d条边，每条边包括起点名称、终点名称和权值，以空格分隔：\n", G->arcnum);
    for (i = 0; i < G->arcnum; i++) {
        scanf("%s%s%d", start, end, &weight);
        // 查找起点和终点在顶点数组中的下标
        int m = -1, n = -1;
        for (j = 0; j < G->vexnum; j++) {
            if (strcmp(G->vexs[j].name, start) == 0) {
                m = j;
            }
            if (strcmp(G->vexs[j].name, end) == 0) {
                n = j;
            }
            if (m != -1 && n != -1) {
                break;
            }
        }
        G->edges[m][n] = weight;  // 存储边的权值
        G->edges[n][m] = weight;
    }
}

// 深度优先遍历
void DFS(MGraph* G, int v) {
    visited[v] = true;
    path[pathIndex++] = v;  // 把当前顶点加入路径
    int i;
    for (i = 0; i < G->vexnum; i++) {
        if (G->edges[v][i] != 0 && !visited[i]) {  // 如果有边相连且未被访问
            DFS(G, i);
        }
    }
}

// 广度优先遍历
void BFS(MGraph* G, int v) {
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    int i;
    visited[v] = true;
    queue[rear++] = v;  // 把当前顶点加入队列
    while (front < rear) {
        int w = queue[front++];  // 取出队首元素
        path[pathIndex++] = w;  // 把当前顶点加入路径
        for (i = 0; i < G->vexnum; i++) {
            if (G->edges[w][i] != 0 && !visited[i]) {  // 如果有边相连且未被访问
                visited[i] = true;
                queue[rear++] = i;  // 把相邻未访问的顶点加入队列
            }
        }
    }
}

int main() {
    MGraph G;
    InitGraph(&G);
    char start[20];
    printf("请输入遍历起点名称：");
    scanf("%s", start);
    int i, j, start_index = -1;
    // 查找遍历起点在顶点数组中的下标
    for (i = 0; i < G.vexnum; i++) {
        if (strcmp(G.vexs[i].name, start) == 0) {
            start_index = i;
            break;
        }
    }
    if (start_index == -1) {
        printf("没有找到起点！\n");
        return 0;
    }
    memset(visited, false, sizeof(visited));  // 初始化visited数组
    printf("深度遍历序列：");
    DFS(&G, start_index);
    for (i = 0; i < pathIndex; i++) {
        printf("%s ", G.vexs[path[i]].name);
    }
    printf("\n");
    pathIndex = 0;  // 重置路径数组下标
    memset(visited, false, sizeof(visited));  // 初始化visited数组
    printf("广度遍历序列：");
    BFS(&G, start_index);
    for (i = 0; i < pathIndex; i++) {
        printf("%s ", G.vexs[path[i]].name);
    }
    printf("\n");
    return 0;
}

输入示例：

6 9
A B C D E F
A B 1
A C 2
B C 3
B D 4
B E 5
C E 6
D E 7
D F 8
E F 9
A

输出示例：

深度遍历序列：A B C E D F 
广度遍历序列：A B C E D F