站群管理,淘宝做关键词的网站,智慧服务区下载,wap端网站建设题目详情#xff1a;
现有村落间道路的统计数据表中#xff0c;列出了有可能建设成标准公路的若干条道路的成本#xff0c;求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N#xff08;≤1000#xff09;和候选道路数目M#xff08…题目详情
现有村落间道路的统计数据表中列出了有可能建设成标准公路的若干条道路的成本求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数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 (V0; VGraph-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 (i0; iGraph-Ne; i) {scanf(%d %d %d, E-V1, E-V2, E-Weight); /* 注意如果权重不是整型Weight的读入格式要改 */InsertEdge( Graph, E );}} /* 如果顶点有数据的话读入数据 */for (V0; VGraph-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 (V0; VGraph-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 (V0; VGraph-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 ( VERROR ) /* 若这样的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( W0; WGraph-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;
}
