c语音编写代码 要求:(1)使用邻接矩阵建无向网,对图实现广度、深度遍历;使用普里姆算法求最小生成树。 (2)使用邻接表建图,对图实现广度、深度遍历;使用克鲁斯卡尔算法求最小生成树。 举例说明输入来正确运行程序
时间: 2024-02-06 22:12:23 浏览: 26
好的,以下是C语言实现图的遍历和最小生成树的代码:
1. 使用邻接矩阵建无向网,对图实现广度、深度遍历;使用普里姆算法求最小生成树。
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_VERTEX_NUM 20
#define INF INT_MAX
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 顶点
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertexNum, edgeNum; // 顶点数和边数
} Graph;
// 初始化图
void initGraph(Graph *graph) {
int i, j;
graph->vertexNum = 0;
graph->edgeNum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
graph->vertex[i] = 0;
for (j = 0; j < MAX_VERTEX_NUM; j++) {
graph->edge[i][j] = INF;
}
}
}
// 添加顶点
void addVertex(Graph *graph, int v) {
graph->vertex[graph->vertexNum++] = v;
}
// 添加边
void addEdge(Graph *graph, int v1, int v2, int weight) {
graph->edge[v1][v2] = graph->edge[v2][v1] = weight;
graph->edgeNum++;
}
// 深度优先遍历
void dfs(Graph *graph, int v, bool visited[]) {
visited[v] = true;
printf("%d ", graph->vertex[v]);
int i;
for (i = 0; i < graph->vertexNum; i++) {
if (graph->edge[v][i] != INF && !visited[i]) {
dfs(graph, i, visited);
}
}
}
// 广度优先遍历
void bfs(Graph *graph, int v, bool visited[]) {
int queue[MAX_VERTEX_NUM];
int rear = 0, front = 0;
visited[v] = true;
queue[rear++] = v;
while (rear != front) {
int v = queue[front++];
printf("%d ", graph->vertex[v]);
int i;
for (i = 0; i < graph->vertexNum; i++) {
if (graph->edge[v][i] != INF && !visited[i]) {
visited[i] = true;
queue[rear++] = i;
}
}
}
}
// 普里姆算法求最小生成树
void prim(Graph *graph) {
int lowcost[MAX_VERTEX_NUM];
int closest[MAX_VERTEX_NUM];
bool visited[MAX_VERTEX_NUM] = {false};
int i, j, k, min, sum = 0;
visited[0] = true;
for (i = 1; i < graph->vertexNum; i++) {
lowcost[i] = graph->edge[0][i];
closest[i] = 0;
}
for (i = 1; i < graph->vertexNum; i++) {
min = INF;
for (j = 1; j < graph->vertexNum; j++) {
if (!visited[j] && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
printf("(%d, %d) %d\n", closest[k], k, min);
visited[k] = true;
sum += min;
for (j = 1; j < graph->vertexNum; j++) {
if (!visited[j] && graph->edge[k][j] < lowcost[j]) {
lowcost[j] = graph->edge[k][j];
closest[j] = k;
}
}
}
printf("最小生成树的权值:%d\n", sum);
}
int main() {
Graph graph;
initGraph(&graph);
int i;
for (i = 1; i <= 6; i++) {
addVertex(&graph, i);
}
addEdge(&graph, 1, 2, 6);
addEdge(&graph, 1, 3, 1);
addEdge(&graph, 1, 4, 5);
addEdge(&graph, 2, 3, 5);
addEdge(&graph, 2, 5, 3);
addEdge(&graph, 3, 4, 5);
addEdge(&graph, 3, 5, 6);
addEdge(&graph, 3, 6, 4);
addEdge(&graph, 4, 6, 2);
addEdge(&graph, 5, 6, 6);
printf("邻接矩阵:\n");
for (i = 0; i < graph.vertexNum; i++) {
int j;
for (j = 0; j < graph.vertexNum; j++) {
if (graph.edge[i][j] == INF) {
printf("INF ");
} else {
printf("%d ", graph.edge[i][j]);
}
}
printf("\n");
}
printf("深度优先遍历:");
bool visited[MAX_VERTEX_NUM] = {false};
dfs(&graph, 0, visited);
printf("\n");
printf("广度优先遍历:");
for (i = 0; i < graph.vertexNum; i++) {
visited[i] = false;
}
bfs(&graph, 0, visited);
printf("\n");
printf("最小生成树:\n");
prim(&graph);
return 0;
}
```
在上述代码中,我们定义了一个结构体`Graph`来表示图,其中包括顶点和邻接矩阵。程序首先初始化图,然后添加顶点和边。接着,我们实现了深度优先遍历和广度优先遍历,以及普里姆算法求最小生成树。
2. 使用邻接表建图,对图实现广度、深度遍历;使用克鲁斯卡尔算法求最小生成树。
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_VERTEX_NUM 20
#define INF INT_MAX
typedef struct EdgeNode {
int adjvex; // 邻接点下标
int weight; // 边权值
struct EdgeNode *next; // 下一个邻接点
} EdgeNode;
typedef struct VertexNode {
int data; // 顶点信息
EdgeNode *firstEdge; // 第一个邻接点
} VertexNode;
typedef struct {
VertexNode vertex[MAX_VERTEX_NUM];
int vertexNum, edgeNum; // 顶点数和边数
} Graph;
// 初始化图
void initGraph(Graph *graph) {
int i;
graph->vertexNum = 0;
graph->edgeNum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
graph->