❶ C语言算法求解：对任意给定的网络（顶点数和边数自定），设计算法生成它的最小生成树。
上一个图和代码：
图1为要哪羡创建的图，图2为对应的最小生成树
代码为：
//图论之最小生成树：prim算法实现
#include"stdio.h"
#include"malloc.h"
//声明
voidoutput(structadjacentlisthead*alh,intmapsize);
structadjacentlistson//邻接表项结构体
{
intsonelement;
intquanvalue;
structadjacentlistson*next;
};
structadjacentlisthead//邻接表头结构体
{
charflag;
intelement;
intcurqvalue;
structadjacentlisthead*previous;
structadjacentlistson*startson;
};
structadjacentlisthead*mapinitialnize(intmapsize)//初始化图函数
{
structadjacentlisthead*alh=NULL;
structadjacentlistson*newnode=NULL;
inti,x,y,z;
alh=malloc(sizeof(structadjacentlisthead)*mapsize);
if(alh==NULL)
returnNULL;
for(i=0;i<mapsize;i++)
{
alh[i].flag=0;
alh[i].element=i+1;
alh[i].curqvalue=0;
alh[i].previous=NULL;
alh[i].startson=NULL;
}
scanf("碧缓吵%d%d%d",&x,&y,&z);
while(x&&y)//直到输入的x,y中至少有一个0为止
{
newnode=malloc(sizeof(structadjacentlistson));
newnode->sonelement=y;
newnode->quanvalue=z;
newnode->next=alh[x-1].startson;
alh[x-1].startson=newnode;
scanf("%d%d%d",&x,&y,&z);
}
returnalh;
}
intfindminnode(structadjacentlisthead*alh,intmapsize)//找到最小权值对应的结点
{
inti,minvalue=~(1<<(sizeof(int)*8-1)),minplace=0;
for(i=0;i<mapsize;i++)
{
if(alh[i].flag==0&&alh[i].curqvalue!=0)
{
if(alh[i].curqvalue<minvalue)
{
minvalue=alh[i].curqvalue;
minplace=i+1;//
}
}
}
returnminplace;
}
voidfindthemintree(structadjacentlisthead*alh,intstartplace,intmapsize)//找到最小生成树
{
structadjacentlistson*alstmp=NULL;
intcurplace=startplace;
while(curplace)
{
alstmp=alh[curplace-1].startson;
alh[curplace-1].flag=1;//正在访问
while(alstmp)
{
if(alh[alstmp->sonelement-1].flag==0)
{
if(alh[alstmp->sonelement-1].curqvalue==0||(alh[alstmp->sonelement-1].curqvalue>alstmp->quanvalue))//比较方法与悔侍有权图有一点不同
{
alh[alstmp->sonelement-1].curqvalue=alstmp->quanvalue;
alh[alstmp->sonelement-1].previous=&alh[curplace-1];
}
}
alstmp=alstmp->next;
}
curplace=findminnode(alh,mapsize);//通过函数找到最小的一个结点
}
}
voidoutput(structadjacentlisthead*alh,intmapsize)
{
inti;
for(i=0;i<mapsize;i++)
{
printf("%d点的权值为：%d ",i+1,alh[i].curqvalue);
}
printf("................................................... ");
}
intmain()
{
structadjacentlisthead*alh=NULL;
intmapsize=7,startplace=1;
alh=mapinitialnize(mapsize);
findthemintree(alh,startplace,mapsize);
output(alh,mapsize);
}
输入数据对应第一图：
122
134
141
212
243
2510
314
342
365
411
423
432
457
468
474
5210
547
576
635
648
671
744
756
761
000
❷ 生成树协议的结构思路
生成树协议拓扑结构的思路是: 不论网桥(交换机)之间采用怎样物理联接,网桥(交换机)能够自动发现一个没有环路的拓扑结构的网路，这个逻辑拓扑结构的网路必须是树型的。生成树协议还能够确定有足够的连接通向整个网络的每一个部分。所有网络节点要么进入转发状态，要么进入阻塞状态,这样就建立了整个局域网的生成树。当首次连接网桥或者网络结构发生变化时，网桥都将进行生成树拓扑的重新计算。为稳定的生成树拓扑结构选择一个根桥, 从一点传输数据到另一点, 出现两条以上条路径时只能选择一条距离根桥最短的活动路径。生成树协议这样的控制机制可以协调多个网桥(交换机)共同工作, 使计算机网络可以避免因为一个接点的失败导致整个网络联接功能的丢失, 而且冗余设计的网络环路不会出现广播风暴。
例如，网络中，A点到C点，有两条路可以走，当ABC的路径不通的时候，可以走ADC。C点到A点也是，路径CDA不通的时候可以走CBA。
如果某一时刻的网络，使能生成树协议，阻塞了B到C的端口，那么网络拓扑就会变成下图。如果有广播包，一定会终结于B点或者C点，不会循环转发。
❸ 透明网桥的生成树算法
透明网桥还使贺纤用了一个生成树（spanning tree）算法，即互连在一起的网桥在进行彼此通信后，就能找出原来的网络拓扑的一个子集。在这个子集里握哗，整个连通的网络中不存在回路，即在任何两个站之间只有一条路径。
为了得能够反映网络拓扑发生变化时段拍行的生成树，在生成树上的根网桥每隔一段时间还要对生成树的拓扑进行更新。
❹ 计算机网络 STP
STP （Spanning Tree Protocol）是生成树协议的英文缩写。
生成树协议 运行生成树算法(STA). 生成树 算法很复杂，但是其过程可以归纳为以下3个步骤：
（1）选择根网桥
（2）选择根端口
（3）选择指定端口
First:BID（Bridge ID，网桥ID），因为根交换机的选举是基于BID的，BID由三部分组成——优先级、发送交换机的MAC地址、Extended System ID（扩展系统ID，可选项）
BID = 网桥ID=网桥优先级+网桥MAC地址组成的
First：（PID）=端口ID等于优先级加上端口编号，默认端口优先级是128。
P:每个非根交换机有且只有一个根端口。
选举根端口依照下面的顺序：
首先，最低花费的端口将成为根端口；在花费相同的情况下比较发送者的BID，BID小的将成为根端口。--->
即:到根网桥最低的根路径成本→发送BPDU的网桥ID(BID)较小→端口ID(PID)较小的。端口ID由端口优先级与端口编号组成。
请看下面这张拓扑图:
特殊的: 如果 发送者的BID相同,则比较发送者的PID:
关于选择指定端口：每个网段上选择一个指定端口。
P：每个网段有且只有一个指派端口
选择顺序为：根路径成本较低（花费较低）→发送BPDU的网桥ID值较小→本端口的PID值较小。
根网桥的接口皆为指定端口，因为根网桥上端口的根路径成本为0 。
第一种情况:假设路径花费不同的情况下 :
既不是根端口也不是指派端口的端口将被阻塞。看上图
❺ 生成树算法是怎么解决环路问题的
生成树协议通过SPA（生成树算法）生成一个没有环路的网络，当主要链路出现故障时，能够自动切换到备份链路，保证网络的正常虚饥运通信 每个LAN都会选择一台设备为指定交换机，通过该设备的端口连接到根，该端口为指定端口（ Designated port ） 将交换网络中所有设备的根端口(RP)和指定端口（DP）设为转发状态（Forwarding），将其肢败他端口设为阻塞状态（Blocking） 生成树经过一段时间（默认值是50秒左右）稳定之后，所有端口要么进入转发状态，要么进入阻塞状态。 IEEE 802.1w—快速生成树协议 快差梁速生成树协议概述 快速生成树协议RSTP(Rapid Spannning Tree Protocol) IEEE 802.1w RSTP协议在STP协议基础上做了改进，使得收敛速度快得多（最快1秒以内） 生成树协议的配置 开启生成树协议 Switch(config)#Spanning-tree 关闭生成树协议 Switch(config)#no Spanning-tree 配置生成树协议的类型 Switch(config)#Spanning-tree mode stp/rstp 锐捷全系列交换机默认使用MSTP协议 配置交换机优先级 Switch(config)#spanning-tree priority <0-61440> (“0”或“4096”的倍数、共16个、缺省32768) 恢复到缺省值 Switch(config)# no spanning-tree priority 配置交换机端口的优先级 Switch(config)#interface interface-type interface-number Switch(config-if)#spanning-tree port-priority number 显示生成树状态 Switch#show spanning-tree 显示端口生成树协议的状态 Switch#show spanning-tree interface fastethernet <0-2/1-24>
❻ 生成树算法
“生成树”资料
交换机内的生成树算法（STA）使你可以创建一条备用链路（当网络中存在多台交换机时）。在主链路正常工作时，备用链路处于空闲状态（不工作）；只有在主链路出现问题时，备用链路才不需要任何人工干预自动地接替主链路。
这种自动重构的功能，使得网络上的用户能够最大限度地与网络保持正常的连接。生成树算法较复杂，所以，建议最好在充分研究理解其之后，再更改其一些设置。请仔细阅读并理解下述内容之后，再去更改交换机上的生成树的默认设置。
网络环路的侦测和预防（Network loop detection and prevention）：任何两个局域网之间应该只有一条路径，否则，网络中将出现环路。如果存在着多于一条的路径，那么生成树算法将会侦测到环路的发生，并自动选择开销值（c ost）最低的那条路径作为可使用的路径（主链路），而阻断其它路径，将它们作为备用路径（备用链路）。
自动拓扑重构（Automatic topology re-configuration）：当主链路中厅锋出现故障时，生成树算法将自卖晌动启用备用链路，重构网络结构。
生成树的级别（STA Operation Levels）
生成树有两种工作级别：桥级别（bridge level）和端口级别（port level）。在桥一级上，生成树算法为每台交换机计算桥的标志级数（Bridge Identifier），然后设定根桥（Root Bridge）和指定桥（Designated Bridges）。而在端口一级上，生成树算法设定根端口（Root Port）和指定端口（Designated Ports）。详述如下：
在桥一级上（On the Bridge Level）：
根桥（Root Bridge）：具有最小桥标志级数的（lowest Bridge Identifier）交换机是根桥（Root Bridge）。当然，你希望根桥是环路中所有交换机当中最好的一台（交换机），以保证能够提供最好的网络性能和可靠性。
桥标志级数（Bridge Identifier）：桥标志级数是桥的优先级（Bridge Priority）和交换机的MAC地址的综合数值，其中桥的优先级（Bridge Priority）是一个你可以设定的参数。例如，“4 00 80 C8 00 01 00”中的“4”是桥的优先级，“00 80 C8 00 01 00”是交换机的MAC地址。交换机的桥标志级数越低，则交换机的优先级越高，这样可以增加其成为根桥的可能性。
指定伏尘桥（Designated Bridge）：在每个网段中，到根桥（Root Bridge）的路径开销最低的（lowest Root Path Cost）桥将成为指定桥（Designated Bridge），数据包将通过它转发到网段。一旦所有的交换机具有相同的根路径开销（Root Path Cost），那么具有最低的桥标志级数的（lowest Bridge Identifier）交换机才会被定为指定桥（De signated Bridge）。
根路径开销（Root Path Cost）：一台交换机的根路径开销（Root Path Cost）是根端口（Root Port）的路径开销（Path Cost）与数据包经过的所有交换机的根路径开销（Root Path Cost）之和。根桥（Root Bridge）的根路径开销（Root Path Cost）是零。
桥的优先级（Bridge Priority）：是一个用户可以设定的参数。设定的值越小，优先级越高。交换机具有越高的优先级，才越有可能成为根桥。
在端口一级上（On the Port Level）：
根端口（Root Port）：每台交换机都有一个根端口（Root Port），这个端口到根桥的路径开销最低。一旦多个端口具有相同的到根桥的路径开销时，那么具有最低的端口标志级别的才会成为根端口。
指定端口（Designated Port）：指定端口就是指定桥（Designated Bridge）上的端口。
端口优先级（Port Priority）：数值越小，端口的优先级就越高。具有越高端口优先级，才越有可能成为根端口。
路径开销（Path Cost）：这是一个可变的参数，它将随着生成树中的设定值的变化而变化。依据STA的默认参数值，每个1000Mbps网段有一个指定的路径开销值为4 ，100Mbps网段的路径开销值19，10Mbps网段的路径开销值100.
生成树参数（STA Parameters）
生成树的参数用户可以根据自己的需要进行修改，但是建议最好使用出厂时的默认设置。除非确实需要对出厂设置值进行变动时，再去改动默认值。用户可以改动的生成树参数有如下几个：
桥优先级（Bridge Priority）：数值范围从0到65535.“0”的优先级最高。
呼叫时间（Bridge Hello Time）：数值范围从1秒到10秒。是指根桥向其它所有交换机发出BPDU数据包的时间间隔，以告知其它所有交换机它是根桥。如果你的交换机还未是根桥时为其设置了呼叫时间，那么，一旦你的交换机成为根桥，该呼叫时间就会派上用处。
注意：呼叫时间不能大于桥的最大老化时间（Max. Age），否则，将出现错误信息。
最大的桥老化时间（Bridge Max. Age）：数值范围从6秒到40秒。如果在超出最大老化时间之后，还没有收到根桥发出的BPDU数据包，那么，在允许的条件下你的交换机将充当根桥向其它所有的交换机发出B PDU数据包。如果交换机确实具有最小的桥标志级数，那么，它将随之成为根桥。
桥转发时延（Bridge Forward Delay）：数值范围从4秒到30秒。是指交换机的端口从阻塞状态转为转发状态所用的监听时间。
当你欲变动生成树参数时，请一定记住下述公式：
最大的桥老化时间≤ 2 x（桥转发时延 – 1秒）
即：Max. Age ≤ 2 x （Forward Delay - 1 second）
最大的桥老化时间≥ 2 x（呼叫时间 + 1秒）
即：Max. Age ≥ 2 x （Hello Time + 1 second）
端口优先级（Port Priority）：数值范围从0到255.数值越小，那么该端口越可能成为根端口。
❼ 急！数据结构最小生成树prim算法C语言实现
Kruskal算法：
void Kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXE];
for (i=0;i<n;i++) vset[i]=i; //初始化辅助数组
k=1; //k表示当前构造最小生成树的第吵游几条边,初值为1
j=0; //E中边的下标,初值为0
while (k<n) //生成的边数小于n时循环
{
m1=E[j].u;m2=E[j].v; //取一条边的头尾顶点
sn1=vset[m1];sn2=vset[m2]; //分别得到两个顶点所属的集合编衫碰厅号
if (sn1!=sn2) //两顶点属于不同的集合,该边是最小生成树的一条边
{
printf(" (%d,%d):%d/n",m1,m2,E[j].w);
k++; //生成边数增1
for (i=0;i<n;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++; //扫描下或隐一条边
}
}
Prim算法：
void prim(MGraph g,int v)
{
int lowcost[MAXV],min,n=g.vexnum;
int closest[MAXV],i,j,k;
for (i=0;i<n;i++) //给lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<n;i++) //找出n-1个顶点
{
min=INF;
for (j=0;j<n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf(" 边(%d,%d)权为:%d/n",closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<n;j++) //修改数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}
❽ 什么是生成树
对连通图进行遍改樱历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常核带丛称为生成树。
在图论的数学领域中，如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。
常用的生成树算法有DFS生成树、BFS生成行神树、PRIM最小生成树和Kruskal最小生成树算法。
通俗的来说呢，就是先假设结论错误，即最小生成树的最大边比瓶颈生成树的最大边大，然后删掉最小生成树的最大边，这时候最小生成树会被分成两个部分（两颗树）。
那么，在瓶颈生成树中肯定存在连接这两个部分并且比最小生成树最大边小的边（因为毕竟瓶颈生成树人家也是生成树，任意两个部分是肯定有边相连的），那么用这条边替换掉最小生成树的最大边，就会与最小生成树的定义矛盾。