浙大数据结构第八周之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

主要思路：

先补一下邻接表建图

邻接表的处理方法：

（1）图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。
（2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

例如，下图就是一个无向图的邻接表的结构：

 从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，

data是数据域，存储顶点的信息，

firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。

边表结点由adjvex和next两个域组成。

adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，（可以通过此下标在一维顶点数组中查询到这个顶点的信息）

next则存储指向边表中下一个结点的指针。

数据结构一：边：

typedef struct ENode *PtrToENode;
struct ENode{Vertex V1, V2;      /* 有向边<V1, V2> */WeightType Weight;  /* 权重 */
};
typedef PtrToENode Edge;

数据结构二：邻接点

/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{Vertex AdjV;        /* 邻接点下标 */WeightType Weight;  /* 边权重 */PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
};

 数据结构三：顶点表头节点

/* 顶点表头结点的定义 */
typedef struct Vnode{PtrToAdjVNode FirstEdge;   /* 指向边表的第一个结点，即此顶点的第一个邻接点 */DataType Data;            /* 存顶点的数据 *//* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */
} AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */

数据结构四：图节点

/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{  int Nv;     /* 顶点数 */int Ne;     /* 边数   */AdjList G;  /* 邻接表 */
};
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */

初始化有顶点没有边的空图：

LGraph CreateGraph( int VertexNum )
{ /* 初始化一个有VertexNum个顶点但没有边的图 */Vertex V;LGraph Graph;Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */Graph->Nv = VertexNum;Graph->Ne = 0;/* 初始化邻接表头指针 *//* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */for (V=0; V<Graph->Nv; V++)Graph->G[V].FirstEdge = NULL;   //将每个顶点的邻接链表的头结点指针设置为 NULL。return Graph; 
}

插入边（插入的时候是头插法）

void InsertEdge( LGraph Graph, Edge E )
{    /* 插入边 <V1, V2> *//* 为V2建立新的邻接点 */PtrToAdjVNode NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->AdjV = E->V2;NewNode->Weight = E->Weight;/* 将V2插入V1的表头，插入的边表示从v1指向v2 */NewNode->Next = Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge = NewNode;/* 若是无向图，还要插入边 <V2, V1> *//* 为V1建立新的邻接点 */NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->AdjV = E->V1;NewNode->Weight = E->Weight;/* 将V1插入V2的表头 */NewNode->Next = Graph->G[E->V2].FirstEdge;Graph->G[E->V2].FirstEdge = NewNode;
}

建图 

LGraph BuildGraph()
{LGraph Graph;Edge E;Vertex V;int Nv, i;scanf("%d", &Nv);   /* 读入顶点个数 */Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ scanf("%d", &(Graph->Ne));   /* 读入边数 */if ( Graph->Ne != 0 ) { /* 如果有边 */ E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */ /* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */for (i=0; i<Graph->Ne; i++) {scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); /* 注意：如果权重不是整型，Weight的读入格式要改 */InsertEdge( Graph, E );}} /* 如果顶点有数据的话，读入数据 */for (V=0; V<Graph->Nv; V++) scanf(" %c", &(Graph->G[V].Data));return Graph;
}

然后是Prim算法：

/* 邻接矩阵存储 - Prim最小生成树算法 */Vertex FindMinDist( MGraph Graph, WeightType dist[] )
{ /* 返回未被收录顶点中dist最小者 */Vertex MinV, V; WeightType MinDist = INFINITY;for (V=0; V<Graph->Nv; V++) {if ( dist[V]!=0 && dist[V]<MinDist) {/* 若V未被收录，且dist[V]更小 */MinDist = dist[V]; /* 更新最小距离 */MinV = V; /* 更新对应顶点 */}}if (MinDist < INFINITY) /* 若找到最小dist */return MinV; /* 返回对应的顶点下标 */else return ERROR;  /* 若这样的顶点不存在，返回-1作为标记 */
}int Prim( MGraph Graph, LGraph MST )
{ /* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */WeightType dist[MaxVertexNum], TotalWeight;Vertex parent[MaxVertexNum], V, W;int VCount;Edge E;/* 初始化。默认初始点下标是0 */for (V=0; V<Graph->Nv; V++) {/* 这里假设若V到W没有直接的边，则Graph->G[V][W]定义为INFINITY */dist[V] = Graph->G[0][V];parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */ }TotalWeight = 0; /* 初始化权重和     */VCount = 0;      /* 初始化收录的顶点数 *//* 创建包含所有顶点但没有边的图。注意用邻接表版本 */MST = CreateGraph(Graph->Nv);E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 *//* 将初始点0收录进MST */dist[0] = 0;VCount ++;parent[0] = -1; /* 当前树根是0 */while (1) {V = FindMinDist( Graph, dist );/* V = 未被收录顶点中dist最小者 */if ( V==ERROR ) /* 若这样的V不存在 */break;   /* 算法结束 *//* 将V及相应的边<parent[V], V>收录进MST */E->V1 = parent[V];E->V2 = V;E->Weight = dist[V];InsertEdge( MST, E );TotalWeight += dist[V];dist[V] = 0;VCount++;for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {/* 若W是V的邻接点并且未被收录 */if ( Graph->G[V][W] < dist[W] ) {/* 若收录V使得dist[W]变小 */dist[W] = Graph->G[V][W]; /* 更新dist[W] */parent[W] = V; /* 更新树 */}}} /* while结束*/if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */TotalWeight = ERROR;return TotalWeight;   /* 算法执行完毕，返回最小权重和或错误标记 */
}

其实本题可以只用邻接矩阵构建的图（或邻接表构建的图)也能解决，因为本题只要求MST的权值，并没有考察更多MST的性质，不过就当巩固所学吧 

代码实现：

#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE_NUMS 1005
#define INFINITY 100000
#define TRUE 1
#define FALSE 0
#define NONE -1
#define ROOT 1
typedef int bool;
/*ListGraph的数据结构*/
/*边*/
typedef struct ENode ENode;
typedef ENode* PToEdgeNode;
struct ENode {int Start, End, Weight;
};
/*邻接点*/
typedef struct AdjVNode AdjVNode;
typedef AdjVNode* PToAdjVNode;
struct AdjVNode {int VertexIndex, Weight;PToAdjVNode Next;
};
/*头结点*/
typedef struct HeadNode HeadNode;
struct HeadNode {int Weight;PToAdjVNode FirstEdge;
};
/*图节点*/
typedef struct ListGraphNode ListGraphNode;
typedef ListGraphNode* ListGraph;
struct ListGraphNode {int EdgeNums, VertexNums;HeadNode AdjList[MAX_NODE_NUMS];
};
/*建一个空图*/
ListGraph CreateEmptyListGraph(int vertexNums) {ListGraph LGraph = (ListGraph)malloc(sizeof(ListGraphNode));LGraph->EdgeNums = 0; LGraph->VertexNums = vertexNums;for(int i = 0; i <= vertexNums; i++) {LGraph->AdjList[i].FirstEdge = NULL;}return LGraph;
}
/*插入边*/
void InsertEdgeInLGraph(ListGraph LGraph, PToEdgeNode edge) {/*插入<start, end>的边*/PToAdjVNode newVertex = (PToAdjVNode)malloc(sizeof(AdjVNode));newVertex->VertexIndex = edge->End;newVertex->Weight = edge->Weight;newVertex->Next = LGraph->AdjList[edge->Start].FirstEdge;LGraph->AdjList[edge->Start].FirstEdge = newVertex;/*插入<end,start>的边，这是因为无向图，如果是有向图可以省略*/newVertex = (PToAdjVNode)malloc(sizeof(AdjVNode));newVertex->VertexIndex = edge->Start;newVertex->Weight = edge->Weight;newVertex->Next = LGraph->AdjList[edge->End].FirstEdge;LGraph->AdjList[edge->End].FirstEdge = newVertex;return;
}
ListGraph BuildListGraph(int vertexNums, int edgeNums) {ListGraph LGraph = CreateEmptyListGraph(vertexNums);for(int i = 0; i < edgeNums; i++) {PToEdgeNode newEdge = (PToEdgeNode)malloc(sizeof(ENode));scanf("%d %d %d", &(newEdge->Start), &(newEdge->End), &(newEdge->Weight));InsertEdgeInLGraph(LGraph, newEdge);free(newEdge);}return LGraph;
}/*MatrixGraph的数据结构*/
typedef struct MatrixGraphNode MatrixGraphNode;
typedef MatrixGraphNode* MatrixGraph;
struct MatrixGraphNode {int VertexNums, EdgeNums;int Weight[MAX_NODE_NUMS][MAX_NODE_NUMS];
};
MatrixGraph CreateEmptyMatrixGraph(int vertexNums) {MatrixGraph MGraph = (MatrixGraph)malloc(sizeof(MatrixGraphNode));MGraph->VertexNums = vertexNums;MGraph->EdgeNums = 0;for(int i = 0; i <= vertexNums; i++) {for(int j = 0; j <= vertexNums; j++) {MGraph->Weight[i][j] = INFINITY;}}return MGraph;
}
void InsertEdgeInMGraph(int start, int end, int weight, MatrixGraph MGraph) {MGraph->Weight[start][end] = weight;MGraph->Weight[end][start] = weight;return;
}
MatrixGraph BuildMGraph(int vertexNums, int edgeNums) {MatrixGraph MGraph = CreateEmptyMatrixGraph(vertexNums);MGraph->EdgeNums = edgeNums;for(int i = 0; i < edgeNums; i++) {int start, end, weight;scanf("%d %d %d", &start, &end, &weight);InsertEdgeInMGraph(start, end, weight, MGraph);}return MGraph;
}
/*Prim算法*/
/*在剩余节点中找到与最小生成树权值最小的边*/
int FindMinDis(MatrixGraph MGraph, const int dis[]) {int minV = NONE;int minDist = INFINITY;for(int i = 1; i <= MGraph->VertexNums; i++) {if(dis[i] != FALSE && dis[i] < minDist) { //dist其实兼顾了Dijkstra中vis数组的作用minDist = dis[i];minV = i;}}return minV;
}
int Prim(MatrixGraph MGraph) {int dis[MAX_NODE_NUMS];     //dis[i]表示节点i到最小生成树的距离int parent[MAX_NODE_NUMS];int totalWeight = 0;int Vcount = 0;/*初始化dis和path数组，默认是从下标1开始，因为顶点从下标1开始*/for(int i = 1; i <= MGraph->VertexNums; i++) {dis[i] = MGraph->Weight[ROOT][i];  //由初始化可以看出，如果ROOT(定这个ROOT的原因是因为最小生成树只有一个根节点)~i两个节点之间有边，就初始化为权值，否则就初始化为INFINITYparent[i] = ROOT;    //假设所有顶点的上一级顶点都是ROOT}/*开始建立最小生成树*/ListGraph MST = CreateEmptyListGraph(MGraph->VertexNums);dis[ROOT] = 0;    //将顶点1作为最小生成树的根节点Vcount++;parent[ROOT] = NONE;while(TRUE) {int minV = FindMinDis(MGraph, dis);if(minV == NONE) break;/*将minV加入到最小生成树中*/PToEdgeNode newEdge = (PToEdgeNode)malloc(sizeof(ENode));newEdge->Start = parent[minV];newEdge->End = minV;newEdge->Weight = dis[minV];InsertEdgeInLGraph(MST, newEdge);Vcount++;totalWeight += dis[minV];dis[minV] = FALSE;    //防止重复加入/*更新dis和path数组*/for(int i = 1; i <= MGraph->VertexNums; i++) {if(dis[i] != FALSE && MGraph->Weight[minV][i] < INFINITY) {   //如果i是之前找到的最小顶点的邻接点并且没有收录if(dis[i] > MGraph->Weight[minV][i]) {  //如果收录最小的节点minV后使得节点i到最小生成树MST的距离变小dis[i] = MGraph->Weight[minV][i];   parent[i] = minV;}}}free(newEdge);}free(MST);if(Vcount < MGraph->VertexNums) return NONE;return totalWeight;
}
int main() {int vertexNums, edgeNums;scanf("%d %d", &vertexNums, &edgeNums);MatrixGraph MGraph = BuildMGraph(vertexNums, edgeNums);printf("%d", Prim(MGraph));free(MGraph);return 0;
}