- 浏览: 287200 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
zh1159007904:
大侠,你这个程序的递归部分看不懂,能不能麻烦解释一下递归的思路 ...
求21位水仙花数(C语言实现) -
shenma_IT:
我是一楼的神马_CS哦 再次表示感谢!!
求21位水仙花数(C语言实现) -
shenma_IT:
好 万分感谢 !!
求21位水仙花数(C语言实现) -
Touch_2011:
shenma_CS 写道你好! 我看了你的代码 有好多让我佩服 ...
求21位水仙花数(C语言实现) -
Touch_2011:
乘法是模拟数学上两个数相乘,但在处理进位方面可能有点不同。比如 ...
求21位水仙花数(C语言实现)
求这个网的最小生成树
/* * 普里姆算法和克鲁斯卡尔算法求最小生成树 * 采用邻接矩阵存储 * */ #include<stdio.h> #define MAX_VERTEX_NUM 20 //图的定义 typedef struct { int vertexNum; int edgeNum; char vertex[MAX_VERTEX_NUM]; int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; }Graph,*PGraph; //辅助数组元素 typedef struct { int from; int to; int weight; int flag; }ArrayNode; //构造无向网 void createdGraph(PGraph g) { int i,j; g->vertexNum=6; g->edgeNum=10; for(i=0;i<g->vertexNum;i++) g->vertex[i]='A'+i; for(i=0;i<g->vertexNum;i++) for(j=0;j<g->vertexNum;j++) g->arc[i][j]=0; g->arc[0][1]=6; g->arc[0][2]=1; g->arc[0][3]=5; g->arc[1][0]=6; g->arc[1][2]=5; g->arc[1][4]=3; g->arc[2][0]=1; g->arc[2][1]=5; g->arc[2][3]=5; g->arc[2][4]=6; g->arc[2][5]=4; g->arc[3][0]=5; g->arc[3][2]=5; g->arc[3][5]=2; g->arc[4][1]=3; g->arc[4][2]=6; g->arc[4][5]=6; g->arc[5][2]=4; g->arc[5][3]=2; g->arc[5][4]=6; } //初始化最小生成树 void initTree(PGraph tree) { int i,j; tree->vertexNum=6; tree->edgeNum=5; for(i=0;i<tree->vertexNum;i++) tree->vertex[i]='0'; for(i=0;i<tree->vertexNum;i++) for(j=0;j<tree->vertexNum;j++) tree->arc[i][j]=0; } //普里姆算法求最小生成树 void prim(PGraph g,PGraph tree) { int i,j,k; int index; //指向权值最小的边 ArrayNode edgeArray[MAX_VERTEX_NUM*2]; //辅助数组 int length=0; //数组长度 int n=1; //统计数组已加入多少个顶点 //初始状态把第一个顶点加入树中 tree->vertex[0]='A'; printf("%-3c",tree->vertex[0]); i=0; while(1){ //寻找与顶点i相接且这条边的另一个顶点不在树中的边,存入edgeArray数组中 for(j=0;j<g->vertexNum;j++){ if(g->arc[i][j] > 0){ //判断这条边的另一个顶点在不在树中 for(k=0;k<tree->vertexNum;k++){ if(tree->vertex[k] == g->vertex[j]) break; } if(k == tree->vertexNum){ edgeArray[length].from=i; edgeArray[length].to=j; edgeArray[length].weight=g->arc[i][j]; edgeArray[length].flag=0; length++; } } } //从数组中选择权值最小的边 index=-1; for(j=0;j<length;j++){ if(index == -1 && edgeArray[j].flag == 0) index=j; if(edgeArray[j].flag==0 && edgeArray[j].weight < edgeArray[index].weight) index=j; } //在树中加入一个顶点,且把这条权值最小的边加入树中 tree->vertex[edgeArray[index].to]='A'+edgeArray[index].to; edgeArray[index].flag=1; tree->arc[edgeArray[index].from][edgeArray[index].to]=edgeArray[index].weight; tree->arc[edgeArray[index].to][edgeArray[index].from]=edgeArray[index].weight; //当这个顶点加入树中时,与这个顶点相邻的边不可加入树中 for(k=0;k<length;k++){ if(edgeArray[k].to == edgeArray[index].to) edgeArray[k].flag=1; } i=edgeArray[index].to; printf("%-3c",tree->vertex[i]); n++; //当有g->vertexNum个顶点时,最小生成树构造完成 if(n==g->vertexNum) break; } } //判断两个顶点是否连通(广度优先搜索) int connected(PGraph tree,int from,int to) { int i,j,k; int vertex[MAX_VERTEX_NUM];//看成队列 int front,rear; if(from==to) return 1; front=rear=0; //把第一个顶点存入数组 vertex[rear++]=from; //遍历tree while(front<=rear){ i=vertex[front]; for(j=0;j<tree->vertexNum;j++) if(tree->arc[i][j]>0){ if(j==to) return 1; //判断此顶点是否在队列中 for(k=0;k<rear;k++) if(vertex[k] == j) break; if(k==rear) vertex[rear++]=j; } front++; } return 0; } //克鲁斯卡尔算法求最小生成树 void kruskal(PGraph g,PGraph tree) { ArrayNode edgeArray[MAX_VERTEX_NUM]; //辅助数组 int length=0; int i,j,k,index,n; //顶点先加入树中 for(i=0;i<tree->vertexNum;i++) tree->vertex[i]=i+'A'; //1.把所有的边有序(从小到大)的插入edgeArray数组中 for(i=0;i<g->vertexNum;i++) for(j=0;j<g->vertexNum;j++){ if(i<j && g->arc[i][j]>0){ //寻找插入的位置index for(k=0;k<length;k++){ if(edgeArray[k].weight > g->arc[i][j]) break; } index=k; //移位 for(k=length;k>index;k--) edgeArray[k]=edgeArray[k-1]; //插入 length++; edgeArray[index].flag=0; edgeArray[index].from=i; edgeArray[index].to=j; edgeArray[index].weight=g->arc[i][j]; } } //2.从小到大取出n-1条边构造最小生成树 n=0; while(n < g->vertexNum-1){ //从小到大取一条符合要求的边 for(k=0;k<length;k++) if(edgeArray[k].flag==0 && connected(tree,edgeArray[k].from,edgeArray[k].to)==0){ break; } //把这条边加入树中 tree->arc[edgeArray[k].from][edgeArray[k].to]=edgeArray[k].weight; tree->arc[edgeArray[k].to][edgeArray[k].from]=edgeArray[k].weight; edgeArray[k].flag=1; printf("%-3d",edgeArray[k].weight); n++; } } void main() { Graph graph; Graph tree; createdGraph(&graph); initTree(&tree); printf("普里姆算法树中顶点加入的顺序:\n"); prim(&graph,&tree); printf("\n"); initTree(&tree); printf("克鲁斯卡尔算法树中边加入的顺序:\n"); kruskal(&graph,&tree); printf("\n"); }
发表评论
-
二叉查找树(二叉排序树)的详细实现
2011-10-22 13:18 1313博客地址: http://blog.csdn.net/tou ... -
确定参赛者名单(C语言实现)
2011-07-10 10:39 1583/* 2011第二届国信蓝点 ... -
整数划分(C语言实现)
2011-07-10 10:35 4983/* 整数的划分问题。 如,对于正整数n=6,可以分划为 ... -
几种全排列的算法(C语言实现)
2011-07-07 00:14 6327/* * 几种排列组合的算法 */ #incl ... -
Playfire加密算法(C语言实现)
2011-07-06 10:13 2991这是C语言选拔赛最后一题,题目如下: /* ... -
浅析贪心算法
2011-07-05 17:46 13821.基本思路: a.顾名思义,贪心算法总是作出在当前看来最好 ... -
浅析动态规划算法
2011-07-05 15:30 17901、 ... -
浅析递归
2011-07-02 20:40 20601.递归的思想: 设计一个递归函数,明确这个递归函数的定义, ... -
浅析分治法
2011-07-02 13:54 22741、分治法思想: 将一个难以直接解决的大问题,分割成一些规模 ... -
浅析回溯算法
2011-06-29 22:48 29121、回溯法的基本思想 (1)在确定解空间的组织结构 ... -
高精度计算
2011-06-27 14:06 10381.大整数加法 2.大整数减法 3.大整数乘法 4.大整 ... -
浅析模拟算法
2011-06-27 07:58 18711.描述 有些问题难以找到公式或规律来解决,可以按 ... -
农夫过河的四种解法
2011-06-25 14:21 6932/* * 题目描述:有一个农夫,带着一只狼、一只羊、一颗白 ... -
各种排序算法的实现(C语言实现)
2011-06-17 22:31 1717/* * 各种基本排序算法实现(以由小到大为例) */ ... -
二叉查找树(C语言实现)
2011-06-15 23:47 2575/* * 构造一颗二叉查找树,实现树的插入、删除等基本操作 ... -
哈希表查找(C语言实现)
2011-06-15 13:38 11431/* * 题目:给定一个全部由字符串组成的字典,字符串全部 ... -
索引查找之英语词典(C语言实现)
2011-06-14 22:48 5521/* * 题目:英语词典。所有的单词存放在dictionary ... -
求最短路径的两种算法(C语言实现)
2011-06-11 11:23 28397求这个有向网中任意两点的最短路径 /* ... -
拓扑排序(C语言实现)
2011-06-10 23:09 3157对这个有向图进行拓扑排序 /* * 拓扑排序(采用邻 ... -
邻接表存储的有向图的基本操作(C语言实现)
2011-06-06 11:47 13950/* * 邻接表存储的有向图的基本操作 */ #in ...
相关推荐
最小生成树c语言实现,采用动态输入最终自动生成最小树路径结果
本程序是C语言实现的最小生成树源代码,使用word文档格式
数据结构最小生成树,C语言源代码,感兴趣的可以看一下。
最小生成树kruskal算法并查集版 C语言实现 - Slyar Home
c语言实现最小生成树算法
c语言编程 最小生成树 c语言编程 最小生成树 c语言编程 最小生成树
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
用c语言实现数据结构中最小生成树问题,代码实验报告
该程序是我写的博客“一起talk C栗子吧(第五十回:C语言实例--最小生成树二)”的配套程序,共享给大家使用
最小生成树计数的详细解题报告与C++代码~ 利用矩阵~
最小生成树kruskal算法并查集版+C语言实现
使用C语言构造可以使n个城市连接的最小生成树,是数据结构设计的内容。
在linux下使用GCC编译运行,用于N个城市之间的架构铁路的最节省方案。
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
输入数据: 7 11 A B 7 A D 5 B C 8 B D 9 B E 7 C E 5 D E 15 D F 6 E F 8 E G 9 F G 11 输出: A - D : 5 D - F : 6 A - B : 7 B - E : 7 E - C : 5 E - G : 9 Total:39
利用克鲁斯卡尔算法求网的最小生成树。要求:若要在n各城市之间建设通信网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网络,是一个网的最小生成树问题。
用普里姆(Prim)算法构造最小生成树 数据结构树与图的经典编程题。优秀的代码哦。
最小生成树 最小生成树(minimum spanning tree)是由n个顶点,n-1条边,将一个连通图连接起来,且使权值最小的结构。 最小生成树可以用Prim(普里姆)算法或kruskal(克鲁斯卡尔)算法求出。 我们将以下面的带权...
这是我买的一本课程设计案例书上的源代码,上面的案例很经典,特别适合于作 毕业设计的学生使用,当然了,也可以做为做课程设计的学生以参考,希望能给 大家提供帮助!!