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

题目

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

输入格式:
输入数据包括城镇数目正整数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应用，姥姥没有讲最小堆的具体实现，代码磨了很久，终于过了。简言之，只有对最小生成树算法逻辑有深刻的认识，同时有足够的耐心和细心，实际动手写，才能提高代码能力。

结果：