邻接矩阵：建立所给无向带权图的邻接矩阵存储并输出该矩阵

很抱歉，我是一个语言模型AI，无法为您提供完整的C语言代码。但我可以给您提供一个参考： 1. 邻接矩阵： ``` #include <stdio.h> #define MAX_VERTEX_NUM 100 typedef struct { int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum, arcnum; } Graph; void createGraph(Graph *G) { int i, j, w; scanf("%d %d", &G->vexnum, &G->arcnum); for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { G->arcs[i][j] = 0; } } for (i = 0; i < G->arcnum; i++) { scanf("%d %d %d", &i, &j, &w); G->arcs[i][j] = w; G->arcs[j][i] = w; } } void printGraph(Graph G) { int i, j; for (i = 0; i < G.vexnum; i++) { for (j = 0; j < G.vexnum; j++) { printf("%d ", G.arcs[i][j]); } printf("\n"); } } int main() { Graph G; createGraph(&G); printGraph(G); return 0; } ``` 2. 邻接表： ``` #include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 100 typedef struct ArcNode { int adjvex; struct ArcNode *next; int weight; } ArcNode; typedef struct VNode { char data; ArcNode *firstarc; } VNode; typedef struct { VNode adjlist[MAX_VERTEX_NUM]; int vexnum, arcnum; } Graph; typedef struct Queue { int data; struct Queue *next; } Queue; void createGraph(Graph *G) { int i, j, w; ArcNode *p, *q; scanf("%d %d", &G->vexnum, &G->arcnum); for (i = 0; i < G->vexnum; i++) { G->adjlist[i].data = i + 'a'; G->adjlist[i].firstarc = NULL; } for (i = 0; i < G->arcnum; i++) { scanf("%d %d %d", &i, &j, &w); p = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = j; p->next = G->adjlist[i].firstarc; p->weight = w; G->adjlist[i].firstarc = p; q = (ArcNode *)malloc(sizeof(ArcNode)); q->adjvex = i; q->next = G->adjlist[j].firstarc; q->weight = w; G->adjlist[j].firstarc = q; } } void printGraph(Graph G) { int i; ArcNode *p; for (i = 0; i < G.vexnum; i++) { printf("%c ", G.adjlist[i].data); p = G.adjlist[i].firstarc; while (p != NULL) { printf("%c(%d) ", p->adjvex + 'a', p->weight); p = p->next; } printf("\n"); } } void DFS(Graph G, int v, int *visited) { ArcNode *p; visited[v] = 1; printf("%c ", G.adjlist[v].data); p = G.adjlist[v].firstarc; while (p != NULL) { if (!visited[p->adjvex]) { DFS(G, p->adjvex, visited); } p = p->next; } } void BFS(Graph G, int v, int *visited) { Queue *rear, *front; ArcNode *p; rear = front = (Queue *)malloc(sizeof(Queue)); front->next = NULL; visited[v] = 1; printf("%c ", G.adjlist[v].data); rear->data = v; rear->next = NULL; while (front->next != NULL) { front = front->next; p = G.adjlist[front->data].firstarc; while (p != NULL) { if (!visited[p->adjvex]) { visited[p->adjvex] = 1; printf("%c ", G.adjlist[p->adjvex].data); rear->next = (Queue *)malloc(sizeof(Queue)); rear = rear->next; rear->data = p->adjvex; rear->next = NULL; } p = p->next; } } } int main() { Graph G; int visited[MAX_VERTEX_NUM]; createGraph(&G); printGraph(G); DFS(G, 0, visited); printf("\n"); BFS(G, 0, visited); printf("\n"); return 0; } ``` 3. 最小生成树： ``` #include <stdio.h> #define MAX_VERTEX_NUM 100 #define INF 32767 typedef struct { int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum, arcnum; } Graph; void createGraph(Graph *G) { int i, j, w; scanf("%d %d", &G->vexnum, &G->arcnum); for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { G->arcs[i][j] = INF; } } for (i = 0; i < G->arcnum; i++) { scanf("%d %d %d", &i, &j, &w); G->arcs[i][j] = w; G->arcs[j][i] = w; } } void prim(Graph G, int *lowcost, int *closest) { int i, j, k, min; for (i = 1; i < G.vexnum; i++) { lowcost[i] = G.arcs[0][i]; closest[i] = 0; } for (i = 1; i < G.vexnum; i++) { min = INF; for (j = 1; j < G.vexnum; j++) { if (lowcost[j] < min && lowcost[j] != 0) { min = lowcost[j]; k = j; } } printf("(%c, %c) ", closest[k] + 'a', k + 'a'); lowcost[k] = 0; for (j = 1; j < G.vexnum; j++) { if (G.arcs[k][j] < lowcost[j]) { lowcost[j] = G.arcs[k][j]; closest[j] = k; } } } } int main() { Graph G; int lowcost[MAX_VERTEX_NUM], closest[MAX_VERTEX_NUM]; createGraph(&G); prim(G, lowcost, closest); return 0; } ```

很高兴为你解答这个问题！以下是满足你要求的C语言程序： ```c #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_VERTEX_NUM 100 // 最大顶点数 // 邻接矩阵存储图结构体 typedef struct { int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vertexNum; // 顶点数 int edgeNum; // 边数 } MGraph; // 邻接表存储图结构体 typedef struct EdgeNode { int adjvex; // 邻接点编号 int weight; // 边权值 struct EdgeNode *next; // 指向下一条边的指针 } EdgeNode; typedef struct VertexNode { int data; // 顶点数据 EdgeNode *firstEdge; // 指向第一条边的指针 } VertexNode; typedef struct { VertexNode adjList[MAX_VERTEX_NUM]; // 邻接表 int vertexNum; // 顶点数 int edgeNum; // 边数 } ALGraph; // 邻接矩阵存储方式的创建图 void createMGraph(MGraph *G) { printf("请输入图的顶点数和边数：\n"); scanf("%d %d", &G->vertexNum, &G->edgeNum); // 初始化邻接矩阵 for (int i = 0; i < G->vertexNum; i++) { for (int j = 0; j < G->vertexNum; j++) { G->edges[i][j] = 0; } } // 建立邻接矩阵 for (int k = 0; k < G->edgeNum; k++) { printf("请输入第 %d 条边的起点、终点和权值：\n", k+1); int i, j, w; scanf("%d %d %d", &i, &j, &w); G->edges[i][j] = w; G->edges[j][i] = w; // 无向图 } } // 输出邻接矩阵 void printMGraph(MGraph G) { printf("邻接矩阵：\n"); for (int i = 0; i < G.vertexNum; i++) { for (int j = 0; j < G.vertexNum; j++) { printf("%d ", G.edges[i][j]); } printf("\n"); } } // 邻接表存储方式的创建图 void createALGraph(ALGraph *G) { printf("请输入图的顶点数和边数：\n"); scanf("%d %d", &G->vertexNum, &G->edgeNum); // 初始化邻接表 for (int i = 0; i < G->vertexNum; i++) { G->adjList[i].data = i; G->adjList[i].firstEdge = NULL; } // 建立邻接表 for (int k = 0; k < G->edgeNum; k++) { printf("请输入第 %d 条边的起点、终点和权值：\n", k+1); int i, j, w; scanf("%d %d %d", &i, &j, &w); // 新建边节点 EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode)); e->adjvex = j; e->weight = w; // 将边节点插入起点的邻接表中 e->next = G->adjList[i].firstEdge; G->adjList[i].firstEdge = e; // 无向图，需要将边反向再插入一次 e = (EdgeNode*)malloc(sizeof(EdgeNode)); e->adjvex = i; e->weight = w; e->next = G->adjList[j].firstEdge; G->adjList[j].firstEdge = e; } } // 深度优先遍历的递归函数 void DFS(ALGraph G, int v, bool visited[]) { visited[v] = true; printf("%d ", G.adjList[v].data); EdgeNode *p = G.adjList[v].firstEdge; while (p) { int w = p->adjvex; if (!visited[w]) { DFS(G, w, visited); } p = p->next; } } // 深度优先遍历 void DFSTraverse(ALGraph G) { bool visited[MAX_VERTEX_NUM] = {false}; printf("深度优先遍历结果：\n"); for (int i = 0; i < G.vertexNum; i++) { if (!visited[i]) { DFS(G, i, visited); } } printf("\n"); } // 广度优先遍历 void BFSTraverse(ALGraph G) { bool visited[MAX_VERTEX_NUM] = {false}; printf("广度优先遍历结果：\n"); int queue[MAX_VERTEX_NUM]; int front = -1, rear = -1; for (int i = 0; i < G.vertexNum; i++) { if (!visited[i]) { visited[i] = true; printf("%d ", G.adjList[i].data); queue[++rear] = i; while (front != rear) { int v = queue[++front]; EdgeNode *p = G.adjList[v].firstEdge; while (p) { int w = p->adjvex; if (!visited[w]) { visited[w] = true; printf("%d ", G.adjList[w].data); queue[++rear] = w; } p = p->next; } } } } printf("\n"); } // Prim算法求最小生成树 void MiniSpanTree_Prim(MGraph G) { int lowcost[MAX_VERTEX_NUM]; // 存放顶点i到最小生成树的最小权值 int closest[MAX_VERTEX_NUM]; // 存放与i相邻的最近顶点编号 bool s[MAX_VERTEX_NUM] = {false}; // S集合，初始为空 int sum = 0; // 总权值 // 初始化 for (int i = 0; i < G.vertexNum; i++) { lowcost[i] = G.edges[0][i]; closest[i] = 0; } s[0] = true; // n-1次找出n-1条边 for (int i = 1; i < G.vertexNum; i++) { int min = INT_MAX; int j = 0; // 找到当前S集合中距离最近的顶点 for (int k = 0; k < G.vertexNum; k++) { if (!s[k] && lowcost[k] < min) { min = lowcost[k]; j = k; } } s[j] = true; sum += min; printf("找到一条边：(%d, %d) 权值为 %d\n", closest[j], j, min); // 更新lowcost和closest数组 for (int k = 0; k < G.vertexNum; k++) { if (!s[k] && G.edges[j][k] < lowcost[k]) { lowcost[k] = G.edges[j][k]; closest[k] = j; } } } printf("最小生成树的总权值为：%d\n", sum); } int main() { MGraph G1; ALGraph G2; // 邻接矩阵存储方式的创建图 createMGraph(&G1); printMGraph(G1); // 邻接表存储方式的创建图 createALGraph(&G2); DFSTraverse(G2); BFSTraverse(G2); // Prim算法求最小生成树 MiniSpanTree_Prim(G1); return 0; } ``` 这个程序实现了三个要求： 1. 建立所给无向带权图的邻接矩阵存储并输出该矩阵。 2. 建立所给无向图的邻接表，并输出该图的深度优先遍历和广度优先遍历结果。 3. 以无向网表示 n 个城市之间通表示该线路的造价，设计一个方案，使这个通信网的总造价最低，实现了Prim算法求最小生成树。 如果你有任何问题，欢迎继续提问！