废旧网站哪个做的最好,微信官方微网站吗,域名是什么结构称为域名空间,网站 php连接mysql 代码课程设计题目
求解建公路问题 课程设计目的
深入掌握 Prim 和 Kruskal算法在求解实际问题中的应用 问题描述 假设有 n 个村庄,编号从到,现在修建一些道路使任意两个村庄之间可以互相连通。所谓两个村庄 A 和B是连通的,指当且仅当A 和 B之间有一条道路或者存在一个村庄 C 使得…课程设计题目
求解建公路问题 课程设计目的
深入掌握 Prim 和 Kruskal算法在求解实际问题中的应用 问题描述 假设有 n 个村庄,编号从到,现在修建一些道路使任意两个村庄之间可以互相连通。所谓两个村庄 A 和B是连通的,指当且仅当A 和 B之间有一条道路或者存在一个村庄 C 使得 A 和C之间有一条道路并且C和B是连通的。有一些村庄之间已经存在一些道路,这里的工作是建造一些道路以使所有村庄都连通,并且所有道路的长度最小。 测试数据存放在 datal4.txt 文件中,第一行是整数n(3≦n≦100)它是村庄的数量然后是n 行,其中第行包含 个整数,而这n 个整数中的第个表示村庄与村庄j之间的距离(该距离应为[1,1000]的整数); 然后有一个整数 q(0≦q≦n(n1)/2); 接下来有行,每行包含两个整数a 和b(1 ≦a ≦b≦n),这意味着已经建立了村庄 a 和村b 之间的道路。例如,data14.txt 的数据如下: 3 0 990 692 990 0 179 692 179 0 1 1 2 源程序
#include iostream
#include cstring
#includevector
#includealgorithm
using namespace std;
#define INF 0x3f3f3f3f
#define MAXV 105
int mat[MAXV][MAXV];
int U[MAXV];
int lowcost[MAXV];
int n;int Prim() //解法1Prim算法求顶点1出发的最小生成树的权值和
{ memset(U,0,sizeof(U));memset(lowcost,0x3f,sizeof(lowcost));int ans0; //存放结果lowcost[1]0;for(int i1;in;i){ int mincINF,k0;for(int j1;jn;j) //在(V-U)中找出离U最近的顶点kif(!U[j] lowcost[j]minc){ minclowcost[j];kj;}ansminc; //累计最小生成树的边权U[k]1; //标记k已经加入Ufor(int i1;in;i) //调整if(U[i]0 lowcost[i]mat[k][i])lowcost[i]mat[k][i];}return ans;
}
//----并查集基本运算算法
int parent[MAXV]; //并查集存储结构
int rnk[MAXV]; //存储结点的秩
void Init(int n) //并查集初始化
{ for (int i1;in;i) //顶点编号1到n { parent[i]i;rnk[i]0;}
}
int Find(int x) //并查集中查找x结点的根结点
{ if (x!parent[x])parent[x]Find(parent[x]); //路径压缩return parent[x];
}
void Union(int x,int y) //并查集中x和y的两个集合的合并
{ int rxFind(x);int ryFind(y);if (rxry) //x和y属于同一棵树的情况return;if (rnk[rx]rnk[ry])parent[rx]ry; //rx结点作为ry的孩子 else{ if (rnk[rx]rnk[ry]) //秩相同合并后rx的秩增1rnk[rx];parent[ry]rx; //ry结点作为rx的孩子}
}
struct Edge //边向量元素类型
{ int u; //边的起始顶点int v; //边的终止顶点int w; //边的权值Edge(int u,int v,int w) //构造函数{ this-uu;this-vv;this-ww;}bool operator(const Edge s) const //重载运算符{return ws.w; //用于按w递增排序}
};
int Kruskal() //解法2改进的Kruskal算法求最小生成树的权值和
{ int ans0;vectorEdge E; //建立存放所有边的向量Efor (int i1;in;i) //由图的邻接矩阵g产生边向量Efor (int j1;jn;j)if (ij)E.push_back(Edge(i,j,mat[i][j]));sort(E.begin(),E.end()); //对E按权值递增排序Init(n); //并查集初始化int k1; //k表示当前构造生成树的第几条边,初值为1int j0; //E中边的下标,初值为0while (kn) //生成的边数小于n时循环{ int u1E[j].u;int v1E[j].v; //取一条边的起始和终止顶点int sn1Find(u1);int sn2Find(v1); //分别得到两个顶点所属的集合编号if (sn1!sn2) //两顶点属于不同的集合,该边是最小生成树的一条边{ ansE[j].w; //累计最小生成树的边权k; //生成边数增1Union(sn1,sn2); //合并}j; //扫描下一条边}return ans;
}
int main()
{freopen(data14.txt,r,stdin); //输入重定向 scanf(%d,n);printf(村庄n%d\n,n);for(int i1;in;i)for(int j1;jn;j)scanf(%d,mat[i][j]);printf(邻接矩阵\n); for(int i1;in;i){for(int j1;jn;j)printf(%4d ,mat[i][j]);printf(\n);}int k;scanf(%d,k);printf(已经建好如下%d条道路\n,k);for(int i0;ik;i){ int a,b;scanf(%d%d,a,b);printf( (%d,%d)\n,a,b);mat[a][b]mat[b][a]0;}printf(求解结果\n); printf( 解法1: %d\n,Prim());printf( 解法2: %d\n,Kruskal());return 0;
} 数据及结果分析 求解建公路问题可以使用Prim算法和Kruskal算法。这两种算法都是基于贪心的思想通过不断选择最小权重的边来构建最小生成树。
1. Prim算法 - 数据结构使用邻接矩阵或邻接表表示图。 - 算法设计 1) 初始化一个空的最小生成树集合M将起点加入M。 2) 从M中选取一条权值最小的边(u, v)将v加入M。 3) 更新与v相邻的未被加入M的顶点的权值并选取权值最小的边(u, w)将w加入M。 4) 重复步骤2和3直到M包含所有顶点。
2. Kruskal算法 - 数据结构使用邻接表表示图。 - 算法设计 1) 将所有边按照权值从小到大排序。 2) 初始化一个空的最小生成树集合M。 3) 遍历排序后的边对于每条边(u, v)如果u和v不在同一个连通分量中则将边(u, v)加入M并将u和v所在的连通分量合并。 4) 重复步骤3直到M包含所有顶点。 在实际应用中可以根据具体问题选择合适的算法。例如如果图是稀疏的可以使用邻接表表示图从而减少存储空间和计算时间如果需要快速找到最小生成树可以使用Prim算法。
