当前位置： 首页 > news >正文

浙大陈越何钦铭数据结构08-图7 公路村村通【循环和最小堆版】

news 2025/8/24 11:28:42

题目

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
输出样例:
12

分析：
一个典型的最小生成树问题，可以用Prim或Kruskal实现，本文使用Prim用循环和最小堆2种方式实现。

循环代码：

#include <stdio.h>
#include <stdlib.h>#define MAX_VERTEX_NUM 1000
#define INFINITY 65535
#define ERROR -1typedef int Vertex;
typedef int WeightType;struct _Edge
{Vertex V, W;WeightType weight;
};
typedef struct _Edge *Edge;typedef struct _AdjNode *AdjNode;
struct _AdjNode
{Vertex adjV;WeightType weight;AdjNode next;
};typedef struct AdjTable
{AdjNode firstEdge;
} AdjTable[MAX_VERTEX_NUM];struct _LGraph
{int Nv, Ne;AdjTable graph;
};
typedef struct _LGraph *LGraph;LGraph CreateGraph(int vertexNum);
void InsertEdge(LGraph graph, Edge E);
LGraph BuildGraph(int vertexNum, int edgeNum);
Vertex FindMinDist(LGraph G, WeightType dist[]);
int Prim(LGraph graph, Vertex S);/*
08-图7 公路村村通
难度：1星6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3126 4
1 2 5
1 3 3
1 4 7
5 6 26 6
1 2 10
2 4 20
3 4 30
1 3 40
1 4 50
2 3 604 4
1 2 10
2 3 20
3 4 30
1 4 404 6
1 2 10
1 3 40
1 4 50
2 3 60
2 4 20
3 4 30
602 1
1 2 107 21
1 2 14
1 3 11
1 4 19
1 5 12
1 6 17
1 7 20
2 3 16
2 4 15
2 5 13
2 6 10
2 7 18
3 4 20
3 5 12
3 6 11
3 7 16
4 5 14
4 6 17
4 7 19
5 6 10
5 7 15
6 7 137 21
1 2 14
1 3 11
1 4 19
1 5 12
1 6 17
1 7 20
2 3 16
2 4 15
2 5 13
2 6 10
2 7 18
3 4 20
3 5 12
3 6 11
3 7 16
4 5 14
4 6 17
4 7 19
5 6 10
5 7 15
6 7 13*/int main()
{int N, M;scanf("%d %d", &N, &M);LGraph G = BuildGraph(N, M);printf("%d\n", Prim(G, 0));free(G);return 0;
}LGraph CreateGraph(int vertexNum)
{LGraph G;G = (LGraph)malloc(sizeof(struct _LGraph));G->Nv = vertexNum;G->Ne = 0;for (int V = 0; V < G->Nv; V++){G->graph[V].firstEdge = NULL;}return G;
}void InsertEdge(LGraph G, Edge E)
{AdjNode NewNode;NewNode = (AdjNode)malloc(sizeof(struct _AdjNode));NewNode->adjV = E->W;NewNode->weight = E->weight;NewNode->next = G->graph[E->V].firstEdge;G->graph[E->V].firstEdge = NewNode;NewNode = (AdjNode)malloc(sizeof(struct _AdjNode));NewNode->adjV = E->V;NewNode->weight = E->weight;NewNode->next = G->graph[E->W].firstEdge;G->graph[E->W].firstEdge = NewNode;
}LGraph BuildGraph(int vertexNum, int edgeNum)
{LGraph G = CreateGraph(vertexNum);G->Ne = edgeNum;Edge E;E = (Edge)malloc(sizeof(struct _Edge));for (int i = 0; i < G->Ne; i++){scanf("%d %d %d", &E->V, &E->W, &E->weight);E->V--;E->W--;InsertEdge(G, E);}free(E);return G;
}Vertex FindMinDist(LGraph G, WeightType dist[])
{ /* 返回未被收录顶点中dist最小者 */Vertex minV, V;WeightType minDist = INFINITY;for (V = 0; V < G->Nv; V++){if (dist[V] != 0 && dist[V] < minDist){/* 若V未被收录，且dist[V]更小 */minDist = dist[V]; /* 更新最小距离 */minV = V;          /* 更新对应顶点 */}}if (minDist < INFINITY) /* 若找到最小dist */return minV;        /* 返回对应的顶点下标 */elsereturn ERROR; /* 若这样的顶点不存在，返回-1作为标记 */
}int Prim(LGraph G, Vertex S)
{ // 只计算TotalWeight，无需实际创建生成树WeightType dist[G->Nv], totalWeight;Vertex V;AdjNode W;int vCount;for (V = 0; V < G->Nv; V++)dist[V] = INFINITY;for (W = G->graph[S].firstEdge; W; W = W->next)dist[W->adjV] = W->weight;totalWeight = 0;vCount = 0;dist[S] = 0;vCount++;while (1){V = FindMinDist(G, dist);if (V == ERROR)break;totalWeight += dist[V];dist[V] = 0;vCount++;for (W = G->graph[V].firstEdge; W; W = W->next){if (dist[W->adjV] != 0){if (W->weight < dist[W->adjV]){dist[W->adjV] = W->weight;}}}}if (vCount < G->Nv) /* MST中收的顶点少于|V|-1个 */totalWeight = ERROR;return totalWeight;
}

最小堆代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MIN_DATA -1000
#define ELEMENT_TYPE int
#define MAX_VERTEX_NUM 1000
#define INFINITY 65535
#define ERROR -1typedef int Vertex;
typedef int WeightType;struct _MinHeap
{ELEMENT_TYPE *Elements;int Size;int Capacity;
};
typedef struct _MinHeap *MinHeap;struct _Edge
{Vertex V, W;WeightType weight;
};
typedef struct _Edge *Edge;typedef struct _AdjNode *AdjNode;
struct _AdjNode
{Vertex adjV;WeightType weight;AdjNode next;
};typedef struct AdjTable
{AdjNode firstEdge;
} AdjTable[MAX_VERTEX_NUM];struct _LGraph
{int Nv, Ne;AdjTable graph;
};
typedef struct _LGraph *LGraph;MinHeap CreateHeap(int MaxSize);
bool isEmpty(MinHeap H);
bool isFull(MinHeap H);
ELEMENT_TYPE DelMin(MinHeap H, int dist[]);
void BuildMinHeap(MinHeap H, int dist[]);
void PercUp(MinHeap H, int p, int dist[]);LGraph CreateGraph(int vertexNum);
void InsertEdge(LGraph graph, Edge E);
LGraph BuildGraph(int vertexNum, int edgeNum);void UpdateHeap(MinHeap H, int dist[], Vertex V);
Vertex FindMinDist(MinHeap H, int dist[]);
int Prim(LGraph graph, Vertex S);/*
08-图7 公路村村通
难度：2星6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3126 4
1 2 5
1 3 3
1 4 7
5 6 24 4
1 2 10
2 3 20
3 4 30
1 4 404 6
1 2 10
1 3 40
1 4 50
2 3 60
2 4 20
3 4 30607 21
1 2 14
1 3 11
1 4 19
1 5 12
1 6 17
1 7 20
2 3 16
2 4 15
2 5 13
2 6 10
2 7 18
3 4 20
3 5 12
3 6 11
3 7 16
4 5 14
4 6 17
4 7 19
5 6 10
5 7 15
6 7 13*/int main()
{int N, M;scanf("%d %d", &N, &M);LGraph G = BuildGraph(N, M);printf("%d\n", Prim(G, 0));free(G);return 0;
}LGraph CreateGraph(int vertexNum)
{LGraph G;G = (LGraph)malloc(sizeof(struct _LGraph));G->Nv = vertexNum;G->Ne = 0;for (int V = 0; V < G->Nv; V++){G->graph[V].firstEdge = NULL;}return G;
}void InsertEdge(LGraph G, Edge E)
{AdjNode newNode;newNode = (AdjNode)malloc(sizeof(struct _AdjNode));newNode->adjV = E->W;newNode->weight = E->weight;newNode->next = G->graph[E->V].firstEdge;G->graph[E->V].firstEdge = newNode;newNode = (AdjNode)malloc(sizeof(struct _AdjNode));newNode->adjV = E->V;newNode->weight = E->weight;newNode->next = G->graph[E->W].firstEdge;G->graph[E->W].firstEdge = newNode;
}LGraph BuildGraph(int vertexNum, int edgeNum)
{LGraph G = CreateGraph(vertexNum);G->Ne = edgeNum;Edge E;E = (Edge)malloc(sizeof(struct _Edge));for (int i = 0; i < G->Ne; i++){ // 用E->V--，E->W--解决顶点序号从1开始的问题scanf("%d %d %d", &E->V, &E->W, &E->weight);E->V--;E->W--;InsertEdge(G, E);}free(E);return G;
}Vertex FindMinDist(MinHeap H, int dist[])
{Vertex minV = ERROR;// 从堆中取出最小值，并维护最小堆的有效性。minV = DelMin(H, dist);return minV;
}int Prim(LGraph G, Vertex S)
{ // 只计算TotalWeight，无需实际创建生成树WeightType dist[G->Nv], totalWeight;Vertex V;AdjNode W;int vCount;for (V = 0; V < G->Nv; V++)dist[V] = INFINITY;for (W = G->graph[S].firstEdge; W; W = W->next)dist[W->adjV] = W->weight;totalWeight = 0;vCount = 0;dist[S] = 0;vCount++;// 根据dist对未收录顶点创建最小堆MinHeap H = CreateHeap(G->Nv);for (V = 0; V < G->Nv; V++){if (dist[V] != 0){ // H->Elements保存的是未收集顶点的编号，本例依次是1,2,3H->Elements[++H->Size] = V;}}BuildMinHeap(H, dist);while (1){V = FindMinDist(H, dist);if (V == ERROR)break;totalWeight += dist[V];dist[V] = 0;vCount++;for (W = G->graph[V].firstEdge; W; W = W->next){if (dist[W->adjV] != 0){if (W->weight < dist[W->adjV]){ /*目标是调整H->Elements,改了吗？没有，也没有必要H-Elements保存的是顶点。现在要做的是定位到W->adjV对应顶点，做percup*/dist[W->adjV] = W->weight;UpdateHeap(H, dist, W->adjV);}}}}if (vCount < G->Nv) /* MST中收的顶点少于|V|-1个 */totalWeight = ERROR;return totalWeight;
}MinHeap CreateHeap(int MaxSize)
{MinHeap H = (MinHeap)malloc(sizeof(struct _MinHeap));H->Elements = (ELEMENT_TYPE *)malloc((MaxSize + 1) * sizeof(ELEMENT_TYPE));H->Elements[0] = MIN_DATA;H->Size = 0;H->Capacity = MaxSize;return H;
}bool isEmpty(MinHeap H)
{return H->Size == 0;
}bool isFull(MinHeap H)
{return H->Size == H->Capacity;
}ELEMENT_TYPE DelMin(MinHeap H, int dist[])
{if (!isEmpty(H)){ELEMENT_TYPE min, last;int parent, child;min = H->Elements[1];last = H->Elements[H->Size--];for (parent = 1; 2 * parent <= H->Size; parent = child){child = 2 * parent;if ((child != H->Size) && (dist[H->Elements[child]] > dist[H->Elements[child + 1]])){child++;}if (dist[last] <= dist[H->Elements[child]]){break;}else{H->Elements[parent] = H->Elements[child];}}H->Elements[parent] = last;if (dist[min] < INFINITY)return min;elsereturn ERROR;}else{return ERROR;}
}void PercUp(MinHeap H, int p, int dist[])
{ /*根据顶点的dist值，决定顶点在堆中的存储位置。对dist[H->Elements[child]] > dist[H->Elements[child + 1]]的理解dist[x] > dist[y],本质是比较两个顶点之间的dist值，x,y是顶点序号。dist[x]的初始值通过dist[V] = G->dist[S][V]获得，并用dist[W] = dist[V] + G->dist[V][W]更新child是顶点在堆中的索引，H->Elements[child]存储的是顶点序号所以dist[H->Elements[child]]是顶点的dist值。*/int parent, child;ELEMENT_TYPE X;X = H->Elements[p];for (parent = p; 2 * parent <= H->Size; parent = child){child = 2 * parent;if ((child != H->Size) && (dist[H->Elements[child]] > dist[H->Elements[child + 1]])){child++;}if (dist[X] <= dist[H->Elements[child]]){break;}else{H->Elements[parent] = H->Elements[child];}}H->Elements[parent] = X;
}void BuildMinHeap(MinHeap H, int dist[])
{ // p表示顶点在堆中的位置int p;for (p = H->Size / 2; p > 0; p--){PercUp(H, p, dist);}
}void UpdateHeap(MinHeap H, int dist[], Vertex V)
{int i, idx, x;// 找到V在堆中的位置for (i = 1; i <= H->Size; i++){if (H->Elements[i] == V){idx = i;x = dist[H->Elements[idx]];break;}}// 更新V的dist值，并向上调整堆// dist[V] = dist[H->Elements[i]];/* 是否需要条件i>1？*/for (i = idx; i > 1 && dist[H->Elements[i / 2]] > x; i /= 2){H->Elements[i] = H->Elements[i / 2];}H->Elements[i] = V;
}

小结:
典型的Prim应用，姥姥没有讲最小堆的具体实现，代码磨了很久，终于过了。简言之，只有对最小生成树算法逻辑有深刻的认识，同时有足够的耐心和细心，实际动手写，才能提高代码能力。

结果：
在这里插入图片描述

http://www.lryc.cn/news/157561.html

相关文章：

  • Linux 部署1Panel现代化运维管理面板远程访问
  • 用百度云怎么重装电脑系统
  • SpringCloud环境搭建及入门案例
  • 什么是序列化和反序列化？
  • React 消息文本循环展示
  • java获取jenkins发布版本信息
  • java八股文面试[数据库]——可重复读怎么实现的（MVCC）
  • cl 和 “clangtidy“分别是什么？是同一样东西吗？
  • ubuntu22.04开机自启动Eureka服务
  • 【 OpenGauss源码学习 —— 列存储（analyze）(三)】
  • Element Plus table formatter函数返回html内容
  • c++ mutable
  • element-plus 踩的坑
  • Python、Rust中的协程
  • Vuepress样式修改内容宽度
  • Vue2电商前台项目——项目的初始化及搭建
  • 递归算法学习——N皇后问题，单词搜索
  • 【SpringBoot】mockito+junit 单元测试
  • webserver 同步 I/O 模拟 Proactor 模式的工作流程
  • mysql8-基于docker搭建主从同步
  • 智能水表远程控制系统：引领节水新时代
  • 【FusionInsight 迁移】HBase从C50迁移到6.5.1（03）6.5.1上准备Loader
  • redis多线程操作
  • OpenCV(十七)：拉普拉斯图像金字塔
  • OpenCL编程指南-10.2使用C++包装器API的矢量相加示例
  • mysql数据库，字符串使用双引号““导致报错，使用单引号‘‘不报错，Unknown column ‘user-test‘ in ‘where clause‘
  • [华为云云服务器评测] 华为云耀云服务器 Java、node环境配置
  • 中企绕道突破封锁，防不胜防 | 百能云芯
  • 动手实践：从栈帧看字节码是如何在 JVM 中进行流转的
  • PEX装机