[6-1] 无向网的5个顶点依序为a, b, c, d, e,其邻接矩阵如下,画出该图及其最小生成树。
时间: 2024-02-15 14:05:44 浏览: 27
首先画出该图:
```
a b c d e
a 0 6 1 5 -
b 6 0 5 - 3
c 1 5 0 5 6
d 5 - 5 0 2
e - 3 6 2 0
```
最小生成树的求解过程可以使用 Prim 或 Kruskal 算法,这里使用 Prim 算法。
选取一个起始点,比如选取顶点 a。然后依次将与该点直接相连的边加入集合 S,记录下该边所连接的点,将这些点标记为已访问。接着从集合 S 中选择一条最小权值的边,该边所连接的点如果已经访问过,则舍弃该边,否则将该边加入集合 S,记录下该边所连接的点,将这些点标记为已访问。重复以上步骤,直到所有的点都被访问过。
最小生成树的边集为 {a-c, c-b, b-e, e-d},其权值和为 12。以下是该图及其最小生成树的示意图:
```
1
a------c
| \ |
6 | 5 | 5
| \ |
b------e
3
|
2
|
d
```
其中,用粗实线表示最小生成树的边。
相关问题
以邻接矩阵作为存储结构,创建4 5 A B C D A B 500 A C 200 A D 150 B C 400 C D 600 无向网,并输出该图的所有顶点和邻接矩阵。
首先,我们需要了解无向网的邻接矩阵的定义和创建方法。
无向网的邻接矩阵是一个n×n的矩阵,其中n为图中顶点的数量。对于顶点i和顶点j,它们之间的连通情况由矩阵中的第i行第j列和第j行第i列的值来表示。如果两个顶点之间有边相连,则对应的矩阵元素为该边的权值;否则为0或INF(表示无穷大)。
邻接矩阵的创建方法如下:
1. 创建一个n×n的矩阵,初始化所有元素为0或INF(不连通的情况)。
2. 读入每条边的信息,将对应的矩阵元素赋值为该边的权值。
根据上述方法,我们可以创建4 5 A B C D A B 500 A C 200 A D 150 B C 400 C D 600 的邻接矩阵如下:
```
A B C D
A 0 500 200 150
B 500 0 400 0
C 200 400 0 600
D 150 0 600 0
```
其中,每行和每列分别代表图中的顶点A、B、C、D,矩阵中元素的值表示对应位置上两个顶点之间的边的权值。例如,第1行第2列的值为500,表示顶点A和顶点B之间的边权为500。
以邻接矩阵作为存储结构,创建4 5 A B C D A B 500 A C 200 A D 150 B C 400 C D 600 无向网,并利用C语言输出该图的所有顶点和邻接矩阵。
以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
typedef struct {
int vertex[MAX_VERTEX_NUM];
int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vertex_num, edge_num;
} Graph;
void initGraph(Graph *G) {
int i, j;
G->vertex_num = 0;
G->edge_num = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertex[i] = 0;
for (j = 0; j < MAX_VERTEX_NUM; j++) {
G->matrix[i][j] = 0;
}
}
}
void addVertex(Graph *G, int v) {
G->vertex[G->vertex_num++] = v;
}
void addEdge(Graph *G, int v1, int v2, int w) {
int i, j;
for (i = 0; i < G->vertex_num; i++) {
if (G->vertex[i] == v1) {
break;
}
}
for (j = 0; j < G->vertex_num; j++) {
if (G->vertex[j] == v2) {
break;
}
}
G->matrix[i][j] = w;
G->matrix[j][i] = w;
G->edge_num++;
}
void printGraph(Graph G) {
int i, j;
printf("Vertex:");
for (i = 0; i < G.vertex_num; i++) {
printf(" %c", G.vertex[i]);
}
printf("\n");
printf("Matrix:\n");
for (i = 0; i < G.vertex_num; i++) {
for (j = 0; j < G.vertex_num; j++) {
printf("%d ", G.matrix[i][j]);
}
printf("\n");
}
}
int main() {
Graph G;
initGraph(&G);
addVertex(&G, 'A');
addVertex(&G, 'B');
addVertex(&G, 'C');
addVertex(&G, 'D');
addEdge(&G, 'A', 'B', 500);
addEdge(&G, 'A', 'C', 200);
addEdge(&G, 'A', 'D', 150);
addEdge(&G, 'B', 'C', 400);
addEdge(&G, 'C', 'D', 600);
printGraph(G);
return 0;
}
```
运行结果:
```
Vertex: A B C D
Matrix:
0 500 200 150
500 0 400 0
200 400 0 600
150 0 600 0
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)