java可视化最小生成树演示,最小生成树模型

本文目录一览：

• 1、java 最小生成树
• 2、一个简单的算法演示程序(JAVA语言实现)
• 3、如何用动态规划法解决最小生成树问题
• 4、图的最小生成树算法？
• 5、JAVA问题求解求速度 http://zhidao.baidu.com/question/206204688.html
• 6、用Java实现生成树协议

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

    {

    }

}

试试这种？

一个简单的算法演示程序(JAVA语言实现)

还真敢要，别说5分了，5块钱也没人帮你做，自己想办法吧，懒鬼

如何用动态规划法解决最小生成树问题

标题： 最小生成树

时 限： 1000 ms

内存限制： 10000 K

总时限： 3000 ms

描述：

有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。假定所有输入的根节点或者源为第一个城市或第一组数据。

请使用prim算法求解。

输入：

n（城市数，1=n=100）；

e（边数）；

以下e行，每行3个数i,j,wij，表示在城市i,j之间修建高速公路的造价。

输出：

n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。

输入样例：

5

8

1 2 2

1 3 12

1 4 10

2 3 8

2 5 9

3 4 6

3 5 3

4 5 7

输出样例：

1 2

2 3

3 5

3 4

提示：

import java.util.Scanner;

public class Main {

public static void prim(int n,float [][]c)

{

float []lowcost = new float [n+1];

int [] closest = new int [n+1];

boolean [] s = new boolean [n+1];

s[1] = true;

for(int i=2;i=n;i++)

{

lowcost[i] = c[1][i];

closest[i] = 1;

s[i] = false ;

}

for(int i=1;in;i++)

{

float min = Float.MAX_VALUE;

int j =1;

for(int k =2;k=n;k++)

if((lowcost[k]min)(!s[k]))

{

min = lowcost[k];

j =k;

}

System.out.println(closest[j]+” “+j);

s[j] = true;

for(int k =2; k=n;k++)

if((c[j][k]lowcost[k])(!s[k]))

{

lowcost[k] = c[j][k];

closest[k] = j;

}

}

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n =sc.nextInt();

int m = sc.nextInt();

float [][]c = new float [n+1][n+1];

for(int i = 0;im ;i++)

{

int x =sc.nextInt();

int y = sc.nextInt();

float z = sc.nextFloat();

c[x][y] = z;

}

for(int i =0;i=n;i++)

for(int j =0;j=n;j++)

if(c[i][j]==0)

c[i][j] =Float.MAX_VALUE;

图的最小生成树算法？

图的生成树和最小生成树生成树(SpanningTree):如果一个图的子图是一个包含图所有节点的树,那这个子图就称为生成树.

JAVA问题求解求速度 http://zhidao.baidu.com/question/206204688.html

功能要求：

1. 选择一个算法（提供选择见下），利用各种方法（图形、动画等）演示算法的演示过程。

2. 可以进行手动演示，也可以自动步进式演示。

3. 允许用户设置算法的各个输入参数，以及自动步进式演示中的时间间隔。

4. 不同的算法输入要求见下。

界面要求：

1. 尽量使用图形界面实现，要符合日常软件使用规范来设计菜单和界面。

2. 如果无法实现图形界面，则在命令行方式下也需要提供菜单，方便用户操作。

其他要求：

1. 标识符命名遵循Windows命名规范。

2. 能够注意各种异常处理，注重提高程序运行效率。

提交内容：

1. 全部源代码。

2. 软件设计和使用说明书（UML类图；实现的功能、主要技术；使用帮助文档）

参考算法：

1. 最小生成树算法：Prim算法、Kruskal算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。

2. 单源最短路算法：Dijkstra算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。

3. 最优编码算法：Huffman编码算法。允许用户输入一段英文文字，或者打开一个txt文档（英文内容），据此文档内容进行编码。要求动态列出每个字符的出现概率统计结果以及对应编码。

4. 其他可供演示的具有一定难度的算法，如关键路径问题、有向图的极大连通分支等。

用Java实现生成树协议

　快速生成树协议(RSTP)STP并不是已经淘汰不用，实际上不少厂家目前还仅支持STP。STP的最大缺点就是他的收敛时间太长，对于现在网络要求靠可靠性来说，这是不允许的，快速生成树的目的就是加快以太网环路故障收敛的速度。1.RSTP 5种端口类型STP定义了4种不同的端口状态，监听(Listening)，学习(Learning)，阻断(Blocking)和转发(Forwarding)，其端口状态表现为在网络拓扑中端口状态混合(阻断或转发)，在拓扑中的角色(根端口、指定端口等等)。在操作上看，阻断状态和监听状态没有区别，都是丢弃数据帧而且不学习MAC地址，在转发状态下，无法知道该端口是根端口还是指定端口。表8-20中看RSTP的端口状态只有三种状态，Discarding、Leaning和Forwarding。表8-20 STP和RSTP端口状态比较RSTP有五种端口类型。根端口和指定端口这两个角色在RSTP中被保留，阻断端口分成备份和替换端口角色。生成树算法(STA)使用BPDU来决定端口的角色，端口类型也是通过比较端口中保存的BPDUB来确定哪个比其他的更优先。1)根端口非根桥收到最优的BPDU配置信息的端口为根端口，即到根桥开销最小的端口，这点和STP一样。请注意图8-16上方的交换机，根桥没有根端口。按照STP的选择根端口的原则，SW-1和SW-2和根连接的端口为根端口。2)指定端口与STP一样，每个以太网网段段内必须有一个指定端口。假设SW-1的BID比SW-2 优先，而且SW-1的P1口端口ID比P2优先级高，那么P1为指定端口，如图8-17所示。 图8-16 RSTP根端口 图8-17 指定端口的选择3)替换端口如果一个端口收到另外一个网桥的更好的 BPDU，但不是最好的，那么这个端口成为替换端口，如图8-18所示。对于SW-2来说，端口P3收到的BPDU比自己优先，自己为次优先，P3为替换端口。4)备份端口如果一个端口收到同一个网桥的更好 BPDU，那么这个端口成为备份端。当两个端口被一个点到点链路的一个环路连在一起时，或者当一个交换机有两个或多个到共享局域网段的连接时，一个备份端口才能存在。如图8-19所示，SW-1的P1和P2口同时接入到以太网的同一网段，P1为指定端口，P2 优先级低，则P2端口为备份端口。 图8-18 替换端口的选择 图8-19 备份端口的选择5)禁用端口在快速生成树协议应用的网络运行中不担当任何角色。2.BPDU更新与变化RSTP添加标志位，如图8-20所示。在STP中，标志位只有0为TC和7为TCA使用，RSTP使用其中保留的6位。另外，RSTP在BPDU指定了端口的角色和端口状态，并且采用提议/同意的控制机制。 具体 参考 下