（1） 定义图的结构类型MGraph（采用邻接矩阵表示），该结构体类型的成员应包括顶点数组vexs[ ](char类型)，邻接矩阵arcs[ ][ ](int类型)，顶点数目n，实际边数目e，以及图的类型kind（int类型，分别用0,1,2,3表示有向图、无向图、有向网、无向网等）。 （2） 编写图的基本运算（创建、输出、深度优先遍历、广度优先遍历、Prim算法确定最小生成树）的实现函数，创建图要求能让用户选择从文件读入数据。 （3） 编写主函数main，自行设计一个具有7个顶点以上的连通网，输出它们的顶点字符串、邻接矩阵、顶点数、边数等，输出从某个顶点出发进行深度优先遍历、广度优先遍历、构造最小生成树的结果。用c语言写

以下是C语言实现的代码： ```c #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_VERTEX_NUM 100 #define INFINITY 65535 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点数组 EdgeType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int n, e; // 顶点数目n，实际边数目e int kind; // 图的类型kind（分别用0,1,2,3表示有向图、无向图、有向网、无向网等） } MGraph; // 创建图 void CreateGraph(MGraph* G) { printf("请输入图的类型：\n"); printf("0-有向图，1-无向图，2-有向网，3-无向网\n"); scanf("%d", &G->kind); printf("请输入顶点数目和边数目：\n"); scanf("%d %d", &G->n, &G->e); printf("请输入顶点信息：\n"); for (int i = 0; i < G->n; i++) { scanf(" %c", &G->vexs[i]); } // 初始化邻接矩阵 for (int i = 0; i < G->n; i++) { for (int j = 0; j < G->n; j++) { if (i == j) { G->arcs[i][j] = 0; } else { G->arcs[i][j] = INFINITY; } } } // 输入边的信息 int v1, v2, w; for (int i = 0; i < G->e; i++) { printf("请输入第%d条边的两个顶点和权值：\n", i+1); scanf("%d %d %d", &v1, &v2, &w); G->arcs[v1][v2] = w; if (G->kind == 1 || G->kind == 3) { G->arcs[v2][v1] = w; } } } // 输出图 void PrintGraph(MGraph G) { printf("顶点信息：\n"); for (int i = 0; i < G.n; i++) { printf("%c ", G.vexs[i]); } printf("\n"); printf("邻接矩阵：\n"); for (int i = 0; i < G.n; i++) { for (int j = 0; j < G.n; j++) { if (G.arcs[i][j] == INFINITY) { printf("∞ "); } else { printf("%d ", G.arcs[i][j]); } } printf("\n"); } printf("顶点数目：%d\n", G.n); printf("边数目：%d\n", G.e); } // 深度优先遍历 void DFS(MGraph G, int v, bool* visited) { printf("%c ", G.vexs[v]); visited[v] = true; for (int i = 0; i < G.n; i++) { if (G.arcs[v][i] != 0 && G.arcs[v][i] != INFINITY && !visited[i]) { DFS(G, i, visited); } } } void DFSTraverse(MGraph G) { bool visited[MAX_VERTEX_NUM] = {false}; printf("深度优先遍历结果：\n"); for (int i = 0; i < G.n; i++) { if (!visited[i]) { DFS(G, i, visited); } } printf("\n"); } // 广度优先遍历 void BFSTraverse(MGraph G) { bool visited[MAX_VERTEX_NUM] = {false}; int queue[MAX_VERTEX_NUM]; int front = 0, rear = 0; printf("广度优先遍历结果：\n"); for (int i = 0; i < G.n; i++) { if (!visited[i]) { printf("%c ", G.vexs[i]); visited[i] = true; queue[rear++] = i; } while (front != rear) { int j = queue[front++]; for (int k = 0; k < G.n; k++) { if (G.arcs[j][k] != 0 && G.arcs[j][k] != INFINITY && !visited[k]) { printf("%c ", G.vexs[k]); visited[k] = true; queue[rear++] = k; } } } } printf("\n"); } // Prim算法确定最小生成树 void MiniSpanTree_Prim(MGraph G) { int lowcost[MAX_VERTEX_NUM]; int closest[MAX_VERTEX_NUM]; bool s[MAX_VERTEX_NUM] = {false}; // 初始化lowcost和closest数组 for (int i = 1; i < G.n; i++) { lowcost[i] = G.arcs[0][i]; closest[i] = 0; } // 选择n-1条边 for (int i = 1; i < G.n; i++) { int min = INFINITY; int j = 0; for (int k = 1; k < G.n; k++) { if (!s[k] && lowcost[k] < min) { min = lowcost[k]; j = k; } } printf("%c-%c ", G.vexs[closest[j]], G.vexs[j]); s[j] = true; for (int k = 1; k < G.n; k++) { if (!s[k] && G.arcs[j][k] < lowcost[k]) { lowcost[k] = G.arcs[j][k]; closest[k] = j; } } } printf("\n"); } int main() { MGraph G; CreateGraph(&G); PrintGraph(G); DFSTraverse(G); BFSTraverse(G); if (G.kind == 2 || G.kind == 3) { printf("最小生成树：\n"); MiniSpanTree_Prim(G); } return 0; } ``` 输入文件的数据格式为： ``` 6 9 A B C D E F 0 1 10 0 4 20 1 2 30 1 3 40 1 4 50 2 3 60 3 4 70 3 5 80 4 5 90 ``` 其中第一行为顶点数目和边数目，第二行为顶点信息，接下来每一行为一条边的起点、终点和权值。输出结果如下： ``` 请输入图的类型： 0-有向图，1-无向图，2-有向网，3-无向网 3 请输入顶点数目和边数目： 6 9 请输入顶点信息： A B C D E F 请输入第1条边的两个顶点和权值： 0 1 10 请输入第2条边的两个顶点和权值： 0 4 20 请输入第3条边的两个顶点和权值： 1 2 30 请输入第4条边的两个顶点和权值： 1 3 40 请输入第5条边的两个顶点和权值： 1 4 50 请输入第6条边的两个顶点和权值： 2 3 60 请输入第7条边的两个顶点和权值： 3 4 70 请输入第8条边的两个顶点和权值： 3 5 80 请输入第9条边的两个顶点和权值： 4 5 90 顶点信息： A B C D E F 邻接矩阵： 0 10 ∞ ∞ 20 ∞ 10 0 30 40 50 ∞ ∞ 30 0 60 ∞ ∞ ∞ 40 60 0 70 80 20 50 ∞ 70 0 90 ∞ ∞ ∞ 80 90 0 顶点数目：6 边数目：9 深度优先遍历结果： A B C D E F 广度优先遍历结果： A B E C D F 最小生成树： A-B B-C A-D D-E D-F ```