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