最小生成树的java代码 最小生成树的java代码是什么
一个简单的算法演示程序(JAVA语言实现)
还真敢要，别说5分了，5块钱也没人帮你做，自己想办法吧，懒鬼
创新互联主营上蔡网站建设的网络公司,主营网站建设方案,手机APP定制开发,上蔡h5小程序制作搭建,上蔡网站营销推广欢迎上蔡等地区企业咨询
java 最小生成树
public class AbstractGraphV
{
public AbstractGraph(List?extends Edge edges, ListVvertices)
{
}
public static class Edge
{
}
}
public class WeightedGraph extends AbstractGraphFloat
{
public WeightedGraph(ListWeightedEdge edges, ListFloat vertices)
{
super(edges, vertices);
}
public static class WeightedEdge extends Edge
{
}
}
试试这种？
kruskal算法java实现，哪位大神能帮忙调通这段代码！
算法如何，就不懂了。但，代码已经正常编译、运行 了
import java.util.*;
import java.io.*;
public class KruskalTest{
private static final int m=3501981;//边数
private static final int n= 2647; //顶点数
private static int[] parent = new int[n];//parent数组,长度为顶点数
private static ArrayListEdge list;//序列
private static float sum = 0; //最小生成树边权总和
public static void main(String[] args)throws FileNotFoundException{
new KruskalTest().test();
}
public void test()throws FileNotFoundException{
File file=new File(".\\Euclidean distance.xlsx");
//读取文件
Scanner sc= new Scanner(file);
double number;
list = new ArrayListEdge();
for(int i=1;i=n;i++)
for(int j=i;j=n;j++) {
Edge edge= new Edge();
edge.u=i;
edge.v=j;
if(sc.hasNext()) {
number=sc.nextDouble();
edge.w=number;
} list.add(edge);
}
Collections.sort(list, new ComparatorEdge(){
@Override
public int compare(Edge o1, Edge o2){
return (int)(o1.w - o2.w);
}
});
//for(int i = 0;i list.size();i++){
// Edge edge = list.get(i);
// System.out.println(edge.u + " " + edge.v + " " + edge.w) ;
// }
kruskal();
System.out.println("the length of MST is " + sum);
}
static void upset(){
for(int i = 0;i n;i++)
parent[i] = -1;
}
int find(int x){
int s;
for(s = x;parent[s] = 0;s = parent[s]);
while(s != x){
int tmp = parent[x];
parent[x] = s;
x = tmp;
}return s;
}
void union(int R1,int R2){
int r1 = find(R1);
int r2 = find(R2);
int temp = parent[r1] + parent[r2];
if(parent[r1] parent[r2]){
parent[r1] = r2;
parent[r2] = temp;
}else{
parent[r2] = r1;
parent[r1] = temp;
}
}
void kruskal(){
int num = 0;
int u ,v;
upset();
for(int i = 0;i m;i++){
Edge edge = (Edge)list.get(i);
u = edge.u;
v = edge.v;
if(find(u) != find(v)){
sum += edge.w;
union(u, v);
num ++;
}
if(num = n - 1)break;
}
}
class Edge{
int u,v;
double w;
}
}
最小生成树问题
关于遗传算法解决最小生成树的问题。
这是prufer编码的代码：
#include stdio.h
#define END 0 // 结束
#define L_BRACKET 1 // 左括号
#define R_BRACKET 2 // 右括号
#define NUMBER 4 // 数
typedef struct _node
{
int value; // 节点值
int childs; // 子节点数
struct _node *parent; // 父节点
struct _node *first_child; // 第一个孩子节点
struct _node *sibling; // 下一个兄弟节点
}NODE;
typedef struct _token
{
int type; // 标记类型(左、右括号，数)
int value; // 值(仅当类型为数时有效)
}TOKEN;
typedef void (*FUNC)(NODE *);
static NODE *pSmallest = 0;// 指向最小的叶子节点
/* 取下一个标记
input 输入串
pToken 用于返回取得的标记
返回值 取走下一个标记后的输入串
*/
char *GetNextToken(char *input,TOKEN *pToken)
{
char *p,ch;
int value;
pToken-type = END;
/* 跳过空白 */
p = input;
while ((ch = *p) ch != '(' ch != ')' !isdigit(ch))
p++;
switch(ch)
{
case '(': pToken-type = L_BRACKET; p++; break;
case ')': pToken-type = R_BRACKET; p++; break;
default:
/* 识别数 */
if (isdigit(ch))
{
value = 0;
while ((ch = *p) isdigit(ch))
{
value = 10 * value + (ch - '0');
p++;
}
pToken-type = NUMBER;
pToken-value = value;
}
break;
}
/* 根据是否到达串尾返回不同的值*/
return (*p == '\0' ? 0 : p);
}
/* 根据输入内容构造树
input 输入串
返回值 构造的树的根节点指针
*/
NODE *BuildTree(char *input)
{
char *p;
TOKEN token;
NODE *pCur,*pNew,*pRoot,*pLast;
p = input; pCur = pLast = pRoot = 0;
do
{
p = GetNextToken(p,token);
switch(token.type)
{
case L_BRACKET:
break;
case R_BRACKET:
/* 回到上一级 */
pLast = pCur;
if (0 != pCur)
pCur = pCur-parent;
break;
case NUMBER:
pNew = (NODE *)malloc(sizeof(NODE));
memset(pNew,0,sizeof(NODE));
pNew-value = token.value;
/*设定父兄节点 */
pNew-parent = pCur;
if (0 != pLast)
{
pLast-sibling = pNew;
pLast = pNew;
}
if (0 != pCur)
{
if (0 == pCur-childs++)
pCur-first_child = pNew;
}
else pRoot = pNew;
p = GetNextToken(p,token);
if (token.type == L_BRACKET)
{
pCur = pNew;/*下一个符号是 (,表示此子树有孩子节点*/
pLast = 0;
}
else if (token.type == R_BRACKET)
pLast = pNew;/*下一个符号是 ),表示某子树结束了*/
break;
}
}while (0 != p);
return pRoot;
}
/* 先序遍历树,并调用指定函数对遍历到的节点进行处理
pRoot 树的根节点指针
func 用于对访问到的节点进行处理的函数
*/
void TravelTree(NODE *pRoot,FUNC func)
{
NODE *pCur;
if (0 == pRoot) return;
(*func)(pRoot);
pCur = pRoot-first_child;
while (pCur)
{
TravelTree(pCur,func);
pCur = pCur-sibling;
}
}
/* 判断指定节点是否是叶子节点(只有一条边相连的节点) */
int IsLeafNode(NODE *pNode)
{
return (0 != pNode (0 == pNode-childs 0 != pNode-parent)
|| (1 == pNode-childs 0 == pNode-parent));
}
/* 比较叶子节点值 */
void LeafValueCompare(NODE *pNode)
{
if (IsLeafNode(pNode))
if (0 == pSmallest) pSmallest = pNode;
else if (pNode-value pSmallest-value)
pSmallest = pNode;
}
/* 从树中删除指定的叶子节点
pRoot 指向树根的指针
pNode 要删除的节点指针
返回值 新的根节点指针
*/
NODE *ReleaseLeafNode(NODE *pRoot,NODE *pNode)
{
NODE *pParent,*pSibling;
if (0 == pNode-childs)
{
pParent = pNode-parent;
if (pParent)
{
pSibling = pParent-first_child;
if (pNode == pSibling)/*要删除的是父节点的第一个孩子*/
pParent-first_child = pNode-sibling;
else
{
while (pSibling pSibling-sibling != pNode)
pSibling = pSibling-sibling;
if (pSibling)
pSibling-sibling = pNode-sibling;
}
pParent-childs--;
}
free(pNode);
}
else/*根节点被删除*/
{
pRoot = pNode-first_child;
pRoot-parent = 0;
free(pNode);
}
return pRoot;
}
void ReleaseTree(NODE *pRoot)
{
NODE *pCur,*pNext;
if (pRoot)
{
pCur = pRoot-first_child;
while (pCur)
{
pNext = pCur-sibling;
ReleaseTree(pCur);
pCur = pNext;
}
free(pRoot);
}
}
int main(int argc,char *argv[])
{
NODE *pRoot;
char line[250];
int n;
while (!feof(stdin))
{
line[0] = '\0';
gets(line);
pRoot = BuildTree(line);
n = 0;
while (pRoot pRoot-childs != 0)
{
pSmallest = 0;
TravelTree(pRoot,LeafValueCompare); // 遍历树
if (0 == pSmallest-childs)
printf(n++ ? " %d" : "%d",pSmallest-parent-value);
else
printf(n++ ? " %d" : "%d",pSmallest-first_child-value);
pRoot = ReleaseLeafNode(pRoot,pSmallest);
}
if (0 != pRoot)
{
printf("\n");
ReleaseTree(pRoot);
}
}
return 0;
}
然后是遗传算法的实现：
/**************************************************************************/
/* This is a simple genetic algorithm implementation where the */
/* evaluation function takes positive values only and the */
/* fitness of an individual is the same as the value of the */
/* objective function */
/**************************************************************************/
#include stdio.h
#include stdlib.h
#include math.h
/* Change any of these parameters to match your needs */
#define POPSIZE 50 /* population size */
#define MAXGENS 1000 /* max. number of generations */
#define NVARS 3 /* no. of problem variables */
#define PXOVER 0.8 /* probability of crossover */
#define PMUTATION 0.15 /* probability of mutation */
#define TRUE 1
#define FALSE 0
int generation; /* current generation no. */
int cur_best; /* best individual */
FILE *galog; /* an output file */
struct genotype /* genotype (GT), a member of the population */
{
double gene[NVARS]; /* a string of variables */
double fitness; /* GT's fitness */
double upper[NVARS]; /* GT's variables upper bound */
double lower[NVARS]; /* GT's variables lower bound */
double rfitness; /* relative fitness */
double cfitness; /* cumulative fitness */
};
struct genotype population[POPSIZE+1]; /* population */
struct genotype newpopulation[POPSIZE+1]; /* new population; */
/* replaces the */
/* old generation */
/* Declaration of procedures used by this genetic algorithm */
void initialize(void);
double randval(double, double);
void evaluate(void);
void keep_the_best(void);
void elitist(void);
void select(void);
void crossover(void);
void Xover(int,int);
void swap(double *, double *);
void mutate(void);
void report(void);
/***************************************************************/
/* Initialization function: Initializes the values of genes */
/* within the variables bounds. It also initializes (to zero) */
/* all fitness values for each member of the population. It */
/* reads upper and lower bounds of each variable from the */
/* input file `gadata.txt'. It randomly generates values */
/* between these bounds for each gene of each genotype in the */
/* population. The format of the input file `gadata.txt' is */
/* var1_lower_bound var1_upper bound */
/* var2_lower_bound var2_upper bound ... */
/***************************************************************/
void initialize(void)
{
FILE *infile;
int i, j;
double lbound, ubound;
if ((infile = fopen("gadata.txt","r"))==NULL)
{
fprintf(galog,"\nCannot open input file!\n");
exit(1);
}
/* initialize variables within the bounds */
for (i = 0; i NVARS; i++)
{
fscanf(infile, "%lf",lbound);
fscanf(infile, "%lf",ubound);
for (j = 0; j POPSIZE; j++)
{
population[j].fitness = 0;
population[j].rfitness = 0;
population[j].cfitness = 0;
population[j].lower[i] = lbound;
population[j].upper[i]= ubound;
population[j].gene[i] = randval(population[j].lower[i],
population[j].upper[i]);
}
}
fclose(infile);
}
/***********************************************************/
/* Random value generator: Generates a value within bounds */
/***********************************************************/
double randval(double low, double high)
{
double val;
val = ((double)(rand()%1000)/1000.0)*(high - low) + low;
return(val);
}
/*************************************************************/
/* Evaluation function: This takes a user defined function. */
/* Each time this is changed, the code has to be recompiled. */
/* The current function is: x[1]^2-x[1]*x[2]+x[3] */
/*************************************************************/
void evaluate(void)
{
int mem;
int i;
double x[NVARS+1];
for (mem = 0; mem POPSIZE; mem++)
{
for (i = 0; i NVARS; i++)
x[i+1] = population[mem].gene[i];
population[mem].fitness = (x[1]*x[1]) - (x[1]*x[2]) + x[3];
}
}
/***************************************************************/
/* Keep_the_best function: This function keeps track of the */
/* best member of the population. Note that the last entry in */
/* the array Population holds a copy of the best individual */
/***************************************************************/
void keep_the_best()
{
int mem;
int i;
cur_best = 0; /* stores the index of the best individual */
for (mem = 0; mem POPSIZE; mem++)
{
if (population[mem].fitness population[POPSIZE].fitness)
{
cur_best = mem;
population[POPSIZE].fitness = population[mem].fitness;
}
}
/* once the best member in the population is found, copy the genes */
for (i = 0; i NVARS; i++)
population[POPSIZE].gene[i] = population[cur_best].gene[i];
}
/****************************************************************/
/* Elitist function: The best member of the previous generation */
/* is stored as the last in the array. If the best member of */
/* the current generation is worse then the best member of the */
/* previous generation, the latter one would replace the worst */
/* member of the current population */
/****************************************************************/
void elitist()
{
int i;
double best, worst; /* best and worst fitness values */
int best_mem, worst_mem; /* indexes of the best and worst member */
best = population[0].fitness;
worst = population[0].fitness;
for (i = 0; i POPSIZE - 1; ++i)
{
if(population[i].fitness population[i+1].fitness)
{
if (population[i].fitness = best)
{
best = population[i].fitness;
best_mem = i;
}
if (population[i+1].fitness = worst)
{
worst = population[i+1].fitness;
worst_mem = i + 1;
}
}
else
{
if (population[i].fitness = worst)
{
worst = population[i].fitness;
worst_mem = i;
}
if (population[i+1].fitness = best)
{
best = population[i+1].fitness;
best_mem = i + 1;
}
}
}
/* if best individual from the new population is better than */
/* the best individual from the previous population, then */
/* copy the best from the new population; else replace the */
/* worst individual from the current population with the */
/* best one from the previous generation */
if (best = population[POPSIZE].fitness)
{
for (i = 0; i NVARS; i++)
population[POPSIZE].gene[i] = population[best_mem].gene[i];
population[POPSIZE].fitness = population[best_mem].fitness;
}
else
{
for (i = 0; i NVARS; i++)
population[worst_mem].gene[i] = population[POPSIZE].gene[i];
population[worst_mem].fitness = population[POPSIZE].fitness;
}
}
/**************************************************************/
/* Selection function: Standard proportional selection for */
/* maximization problems incorporating elitist model - makes */
/* sure that the best member survives */
/**************************************************************/
void select(void)
{
int mem, i, j, k;
double sum = 0;
double p;
/* find total fitness of the population */
for (mem = 0; mem POPSIZE; mem++)
{
sum += population[mem].fitness;
}
/* calculate relative fitness */
for (mem = 0; mem POPSIZE; mem++)
{
population[mem].rfitness = population[mem].fitness/sum;
}
population[0].cfitness = population[0].rfitness;
/* calculate cumulative fitness */
for (mem = 1; mem POPSIZE; mem++)
{
population[mem].cfitness = population[mem-1].cfitness +
population[mem].rfitness;
}
/* finally select survivors using cumulative fitness. */
for (i = 0; i POPSIZE; i++)
{
p = rand()%1000/1000.0;
if (p population[0].cfitness)
newpopulation[i] = population[0];
else
{
for (j = 0; j POPSIZE;j++)
if (p = population[j].cfitness
ppopulation[j+1].cfitness)
newpopulation[i] = population[j+1];
}
}
/* once a new population is created, copy it back */
for (i = 0; i POPSIZE; i++)
population[i] = newpopulation[i];
}
/***************************************************************/
/* Crossover selection: selects two parents that take part in */
/* the crossover. Implements a single point crossover */
/***************************************************************/
void crossover(void)
{
int i, mem, one;
int first = 0; /* count of the number of members chosen */
double x;
for (mem = 0; mem POPSIZE; ++mem)
{
x = rand()%1000/1000.0;
if (x PXOVER)
{
++first;
if (first % 2 == 0)
Xover(one, mem);
else
one = mem;
}
}
}
/**************************************************************/
/* Crossover: performs crossover of the two selected parents. */
/**************************************************************/
void Xover(int one, int two)
{
int i;
int point; /* crossover point */
/* select crossover point */
if(NVARS 1)
{
if(NVARS == 2)
point = 1;
else
point = (rand() % (NVARS - 1)) + 1;
for (i = 0; i point; i++)
swap(population[one].gene[i], population[two].gene[i]);
}
}
/*************************************************************/
/* Swap: A swap procedure that helps in swapping 2 variables */
/*************************************************************/
void swap(double *x, double *y)
{
double temp;
temp = *x;
*x = *y;
*y = temp;
}
/**************************************************************/
/* Mutation: Random uniform mutation. A variable selected for */
/* mutation is replaced by a random value between lower and */
/* upper bounds of this variable */
/**************************************************************/
void mutate(void)
{
int i, j;
double lbound, hbound;
double x;
for (i = 0; i POPSIZE; i++)
for (j = 0; j NVARS; j++)
{
x = rand()%1000/1000.0;
if (x PMUTATION)
{
/* find the bounds on the variable to be mutated */
lbound = population[i].lower[j];
hbound = population[i].upper[j];
population[i].gene[j] = randval(lbound, hbound);
}
}
}
/***************************************************************/
/* Report function: Reports progress of the simulation. Data */
/* dumped into the output file are separated by commas */
/***************************************************************/
void report(void)
{
int i;
double best_val; /* best population fitness */
double avg; /* avg population fitness */
double stddev; /* std. deviation of population fitness */
double sum_square; /* sum of square for std. calc */
double square_sum; /* square of sum for std. calc */
double sum; /* total population fitness */
sum = 0.0;
sum_square = 0.0;
for (i = 0; i POPSIZE; i++)
{
sum += population[i].fitness;
sum_square += population[i].fitness * population[i].fitness;
}
avg = sum/(double)POPSIZE;
square_sum = avg * avg * POPSIZE;
stddev = sqrt((sum_square - square_sum)/(POPSIZE - 1));
best_val = population[POPSIZE].fitness;
fprintf(galog, "\n%5d, %6.3f, %6.3f, %6.3f \n\n", generation,
best_val, avg, stddev);
}
/**************************************************************/
/* Main function: Each generation involves selecting the best */
/* members, performing crossover mutation and then */
/* evaluating the resulting population, until the terminating */
/* condition is satisfied */
/**************************************************************/
void main(void)
{
int i;
if ((galog = fopen("galog.txt","w"))==NULL)
{
exit(1);
}
generation = 0;
fprintf(galog, "\n generation best average standard \n");
fprintf(galog, " number value fitness deviation \n");
initialize();
evaluate();
keep_the_best();
while(generationMAXGENS)
{
generation++;
select();
crossover();
mutate();
report();
evaluate();
elitist();
}
fprintf(galog,"\n\n Simulation completed\n");
fprintf(galog,"\n Best member: \n");
for (i = 0; i NVARS; i++)
{
fprintf (galog,"\n var(%d) = %3.3f",i,population[POPSIZE].gene[i]);
}
fprintf(galog,"\n\n Best fitness = %3.3f",population[POPSIZE].fitness);
fclose(galog);
printf("Success\n");
}
/***************************************************************/
如何用此遗传算法解决最小生成树的问题呢，要求先随机初始化一个图，然后生成对应的最小生成树。
欢迎推荐小组话题，请先登录或注册
快速注册
你的email地址:
请填写email 用于确认你的身份, 豆瓣绝不会公开你的email。
给自己设一个密码:
请填写长度大于3的密码 你需要用它登录, 请使用英文字母、符号或数字。
给自己起一个名号:
起个名号吧 中、英文均可。
用java写了一个最小生成树问题的程序，在进行快速排序边长的权重时，出现了下面的报错
说明 edges[] edgelist1= g.listedges(graph1); 中的 listedges 方法有问题
class graph {
public double[][] generate(int n) {
return null;
}
public double[] listlength(double[][] d) {
return null;
}
public edges[] listedges(double [][] d) {
return null;
}
}
全返回null的，，，，，，，，，都还没做
题目1:一个简单的算法演示程序(JAVA语言实现)
1. 选择一个算法（提供选择见下），利用各种方法（图形、动画等）演示算法的演示过程。
2. 可以进行手动演示，也可以自动步进式演示。
3. 允许用户设置算法的各个输入参数，以及自动步进式演示中的时间间隔。
4. 不同的算法输入要求见下。
界面要求：
1. 尽量使用图形界面实现，要符合日常软件使用规范来设计菜单和界面。
2. 如果无法实现图形界面，则在命令行方式下也需要提供菜单，方便用户操作。
其他要求：
1. 标识符命名遵循Windows命名规范。
2. 能够注意各种异常处理，注重提高程序运行效率。
提交内容：
1. 全部源代码。
2. 软件设计和使用说明书（UML类图；实现的功能、主要技术；使用帮助文档）
参考算法：
1. 最小生成树算法：Prim算法、Kruskal算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
2. 单源最短路算法：Dijkstra算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
3. 最优编码算法：Huffman编码算法。允许用户输入一段英文文字，或者打开一个txt文档（英文内容），据此文档内容进行编码。要求动态列出每个字符的出现概率统计结果以及对应编码。
4. 其他可供演示的具有一定难度的算法，如关键路径问题、有向图的极大连通分支等。
分享标题：最小生成树的java代码 最小生成树的java代码是什么
标题路径：http://azwzsj.com/article/hpjpji.html
