❶ 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最小生成樹演算法。
通俗的來說呢，就是先假設結論錯誤，即最小生成樹的最大邊比瓶頸生成樹的最大邊大，然後刪掉最小生成樹的最大邊，這時候最小生成樹會被分成兩個部分（兩顆樹）。
那麼，在瓶頸生成樹中肯定存在連接這兩個部分並且比最小生成樹最大邊小的邊（因為畢竟瓶頸生成樹人家也是生成樹，任意兩個部分是肯定有邊相連的），那麼用這條邊替換掉最小生成樹的最大邊，就會與最小生成樹的定義矛盾。