java生成树算法_图的最小生成树算法

⑴ 用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指定了端口的角色和端口状态，并且采用提议/同意的控制机制。具体参考下 http://it.kswchina.com/skrz/zh/507188.html

⑵ 图的最小生成树算法

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

⑶ 怎样用Java实现网桥自学习算法

网桥的自学习算法原理

珞辰

网桥：在数据链路层可以用网桥设备来扩展以太网。网桥工作在数据链路层，它根据MAC 帧的目的地址对收到的帧进行存储转发和过滤。当网桥收到一个数据帧时，并不是向所有的接口转发这个数据帧，而是会进行有条件的转发（网桥会丢弃CRC检验有差错的帧以及帧长过短和过长的无效帧）再根据此帧的目的MAC地址，然后查找转发表（网桥会自己维护转发表，转发表中每一条目都记录了到达某个目的MAC地址的数据帧可以从那个接口进行转发）根据转发表中的条目逐步匹配看该从那个接口转发或是否需要丢弃该数据帧。最简单的网桥只有两个接口（这里所讲的网桥都是两个接口的网桥）。

使用网桥设备的优点：

1，过滤通信量，增大吞吐量（网桥可以隔离碰撞域提高网络的吞吐量）

2，扩大了物理网络的范围（扩展以太网）

3，提供了可靠性（只影响单个网段）

4，可以互连不同的物理层，不同MAC子层和不同速率

使用网桥设备的缺点：

1，使用CMSA/CD算法增加了时延

2，不能进行流量控制，缓存存储空间可能会发生溢出

3，会产生广播风暴

网桥自学习和转发帧的一般步骤：

1，网桥收到一帧后先进行自学习。查找转发表中与收到数据帧的源地址有无匹配的项目。如果没有，就在转发表中增加一个项目（记录数据帧的源地址，进入网桥的接口和时间）。如果有，则把原来的项目进行更新。

2，转发帧。查找转发表中与收到数据帧的目的地址有无相匹配的项目。如果没有，则通过其他的接口（但进入网桥的接口除外）进行转发。如果有，则按转发表中给出的接口进行转发。但应当注意，若转发表中给出的接口就是该帧进入网桥的接口，则应该丢弃这个数据帧（因为这种情况不需要经过网桥进行转发）。

3，使用生成树算法，即互连载一起的网桥在进行彼此通信后，就能找出原来的网络拓扑的一个子集。在这个子集里，整个连通的网络中不存在回路，即在任何两个站点之间只有一条路径。

for example：如图所示，6个站点通过透明网桥B1和B2连接到一个扩展的局域网上。初始时网桥B1和B2的转发表都为空。假设需要传输的帧序列如下：H2传输给H1；H5传输给H4；H3传输给H5；H1传输给H2；H6传输给H5。请给出这些帧传输完后网桥B1和网桥B2的转发表。假设转发表表项的格式为：[ 站点，端口 ]。

发送的帧B1转发表 B1的处理 B2转发表 B2的处理

H2--->H1 H2，1 登记，转发 H2，1 登记，转发

H5--->H4 H5，2 登记，转发 H5，2 登记，转发

H3--->H5 H3，2 登记，丢弃 H3，1 登记，转发

H1--->H2 H1，1 登记，丢弃

H6--->H5 H6，2 登记，丢弃

解释说明：

1，H2主机向H1主机发送帧。连接在同一个局域网上的主机H1和网桥B1都能收到H2主机发送的数据帧。网桥B1收到这个数据帧后，先按源地址H2查找转发表。这时因为网桥B1的转发表为空，于是就把地址H2和收到此帧的接口1 写入到转发表中。这就表示，以后若收到要发给H2的帧，应当从网桥B1的这个接口1 转发出去。接着再按目的地址H1查找转发表。转发表中没有H1的地址，于是通过除收到此帧的接口1 以外的所有接口转发此帧。网桥B2 从其接口1 收到这个转发过来的帧。网桥B2按同样的方式处理收到的帧。网桥B2的转发表中没有H2的地址，因此在网桥B2的转发表中写入地址H2 和接口1 。网桥B2的转发表中没有H1的地址，因此网桥B2会通过除接收此帧的接口1 以外的所有接口转发这个帧。（H1本来就可以直接收到H2发送的数据帧，为什么还要让网桥B1和B2盲目地转发这个帧呢？？？答案是：这两个网桥当时并不知道网络的拓扑结构，因此要通过自学习过程才能逐步弄清所连接的网络拓扑，建立起自己的转发表）

2，H3主机向H5主机发送数据帧。首先看网桥B1，网桥B1从其接口2收到这个数据帧。网桥B1的转发表中没有H3，因此在B1的转发表中写入地址H3 和接口2。再查找目的地址H5。现在网桥B1的转发表中可以查询到H5，其转发的接口是2，和这个帧进入网桥B1的接口一样。于是网桥B1知道，不用自己转发这个帧，H5也能收到H3发送的帧。于是网桥B1把这个帧丢弃，不再继续转发了。再看网桥B2，网桥B2从其借口1 收到这个帧。网桥B2的转发表中没有H3，因此在B2的转发表中写入地址H3 和接口 1。再查找目的地址H5。现在网桥B2的转发表中可以查询到H5，其转发的接口是 2 ，于是网桥B2直接将这个帧从接口2 转发出去。

3，H6主机向H5主机发送数据帧。首先看网桥B2，网桥B2从其接口2 收到这个数据帧。网桥B2的转发表中没有H6，因此在B2的转发表中写入地址H6 和接口 2。再查找目的地址H5。现在网桥B2的转发表中可以查询到H5，其转发的接口是2，和这个帧进入网桥B2的接口一样。于是网桥B2知道，不用自己转发这个帧，H5也能收到H6发送的帧。于是网桥B2把这个帧丢弃，不再继续转发了。再看网桥B1，其根本不会收到H6主机向H5发送的数据帧，所以不会有任何其他操作。

PS：在网桥的转发表中写入的信息除了地址和接口外，还有帧进入该网桥的时间。网桥中的接口管理软件周期性的扫描转发表中的项目。只要在一定时间以前登记的都要删除。这样就使得网桥中的转发表能反映当前网络的最新拓扑状态。还有一点网桥是一种工作在数据链路层的网络设备，它能对于接收到的数据帧进行有条件的转发并且能隔离冲突域。

⑷ 如何在Java Jsp页面中动态生成树

JSP

<!DOCTYPEhtmlPUBLIC"-//W3C//DTDXHTML1.0Strict//EN""http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html>

<head>
<title>Destroydrop»Javascripts»Tree</title>

<linkrel="StyleSheet"href="dtree.css"mce_href="dtree.css"type="text/css"/>
<mce:scripttype="text/javascript"src="dtree.js"mce_src="dtree.js"></mce:script>

</head>

<body>

<h1><ahref="/"mce_href="">Destroydrop</a>»<ahref="/javascripts/"mce_href="javascripts/">Javascripts</a>»<ahref="/javascripts/tree/"mce_href="javascripts/tree/">Tree</a></h1>

<h2>Example</h2>

<divclass="dtree">

<p><ahref="javascript:d.openAll();"mce_href="javascript:d.openAll();">openall</a>|<ahref="javascript:d.closeAll();"mce_href="javascript:d.closeAll();">closeall</a></p>

<mce:scripttype="text/javascript"><!--
d=newdTree('d');

d.add(0,-1,'Myexampletree');
d.add(1,0,'Node1','example01.html');
d.add(2,0,'Node2','example01.html');
d.add(3,1,'Node1.1','example01.html');
d.add(4,0,'Node3','example01.html');
d.add(5,3,'Node1.1.1','example01.html');
d.add(6,5,'Node1.1.1.1','example01.html');
d.add(7,0,'Node4','example01.html');
d.add(8,1,'Node1.2','example01.html');
d.add(9,0,'MyPictures','example01.html','PicturesI/'vetakenovertheyears','','','img/imgfolder.gif');
d.add(10,9,'ThetriptoIceland','example01.html','PicturesofGullfossandGeysir');
d.add(11,9,'Mom/'sbirthday','example01.html');
d.add(12,0,'RecycleBin','example01.html','','','img/trash.gif');

document.write(d);
//--></mce:script>

</div>

<p><ahref="mailto:[email protected]"mce_href="mailto:[email protected]">©2002-2003GeirLandrö</a></p>

</body>

</html>

⑸ JAVA问题求解求速度 http://.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二叉树家谱实现

mport java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Random;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTree;
import javax.swing.tree.DefaultMutableTreeNode;

public class Randomtree extends JFrame {

private JTree tree;
public static String[] school = { "初中课程", "高中课程", "大学课程" };
public static String[] color = { "颜色", "运动", "食物" };
public static String[] plant = { "植物", "动物", "人" };

public static String[][] school2= {
{ "初中一年级", "初中二年级", "初中三年级"}, {"高中一年级", "高中二年级",
"高中三年级"}, {"大学一年级", "大学二年级", "大学三年级", "大学四年级"} };
public static String[][] color2 = {
{ "绿色", "白色", "红色"}, {"足球", "篮球",
"羽毛球"}, {"面包", "牛奶", "披萨", "热狗"} };
public static String[][] plant2 = {
{ "玫瑰花", "月季花", "海棠花"}, {"猪", "狗",
"猫"}, {"黄种人", "黑种人", "白种人", } };

public static void main(String[] args) {
// TODO 自动生成方法存根
new Randomtree();
}
public Randomtree() {
super();
final Random random=new Random();
setVisible(true);
setSize(300,400);
tree = new JTree();
final JPanel panel = new JPanel();
panel.setPreferredSize(new Dimension(0, 40));
getContentPane().add(panel, BorderLayout.NORTH);
final JScrollPane scrollPane = new JScrollPane();
scrollPane.setPreferredSize(new Dimension(300, 350));
getContentPane().add(scrollPane, BorderLayout.CENTER);
final JButton button = new JButton();
button.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
int k=random.nextInt(3);
tree=getTree(k);
scrollPane.setViewportView(tree);
}
});

scrollPane.setViewportView(null);
button.setText("随机生成树");
panel.add(button);
pack();

}
protected JTree getTree(int n) {
String[] second=null;
String[][] three=null;
if(n==0){second=school; three=school2;}
if(n==1){second=color; three=color2;}
if(n==2){second=plant; three=plant2;}

DefaultMutableTreeNode root=new DefaultMutableTreeNode("root");
for(int i=0;i<second.length;i++){
DefaultMutableTreeNode secondNode=new DefaultMutableTreeNode(second[i]);
for (int j=0;j<three[i].length;j++){
DefaultMutableTreeNode threetNode=new DefaultMutableTreeNode(three[i][j]);
secondNode.add(threetNode);
}
root.add(secondNode);
}
JTree tree=new JTree(root);
tree.expandRow(1);
tree.expandRow(5);
tree.expandRow(9);
return tree;
}

}
简单的例子你可以模仿一下

⑺ 什么是生成树协议是怎么样实现生成树协议的。

生成树协议——STP
STP(Spanning Treep Protocol)能够提供路径冗余，使用STP可以使两个终端中只有一条有效路径。STP在大的网络中定义了一个树，并且迫使一定的备份路径处于备用状态。如果生成树中的网络一部分不可达，或者STP值变化了，生成树算法会重新计算生成树拓扑，并且通过启动备份路径来重新建立连接。STP操作对于终端来说是透明的，而不管终端连在LAN的某一部分或者多个部分。当创建网络时，网络中所有节点存在多条路径。生成树中的算法计算出最佳路径。因为每个VLAN是一个逻辑LAN部分，所以网管员能使STP一次工作在最多64个VLAN中。如果要配置超过64个VLAN，网管员需要将其他VLAN的STP禁止，因为默认的STP可以支持1-64个VLAN。

⑻ java 最小生成树

publicclassAbstractGraph<V>
{
publicAbstractGraph(List<?extendsEdge>edges,List<V>vertices)
{

}
publicstaticclassEdge
{

}
}
<Float>
{

publicWeightedGraph(List<WeightedEdge>edges,List<Float>vertices)
{
super(edges,vertices);
}

{

}

}

试试这种？

导航:首页 > 编程语言 > java生成树算法

java生成树算法

与java生成树算法相关的资料