資源描述：
《圖的遍歷及生成樹ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、圖的遍歷與求圖的連通分量圖的遍歷:從給定圖中任意指定的頂點(diǎn)出發(fā),按照某種方式系統(tǒng)地訪問圖中的頂點(diǎn),使每個(gè)頂點(diǎn)僅被訪問一次,所得到的一個(gè)序列訪問標(biāo)志位visit[]遍歷前置visit的各元素為0若頂點(diǎn)vi被訪問過,則置visit[i]為1深度優(yōu)先搜索廣度優(yōu)先搜索深度優(yōu)先搜索首先訪問出發(fā)頂點(diǎn)v0選擇一個(gè)與v0相鄰接的且末訪問過的頂點(diǎn)w訪問再從w開始,按深度優(yōu)先搜索…..每當(dāng)?shù)竭_(dá)一個(gè)其所相鄰接的頂點(diǎn)都已被訪問過的頂點(diǎn),則從最后所訪問的頂點(diǎn)開始,依次退回到尚有鄰接頂點(diǎn)末曾訪問過的頂點(diǎn)u,并從u開始進(jìn)行深序優(yōu)先
2、搜索…..直到所有頂點(diǎn)都訪問過或從任何一個(gè)已訪問過的頂點(diǎn)出發(fā),再也無法到達(dá)末曾訪問過的頂點(diǎn)123456789深度優(yōu)先搜索14253135^124135^234^234^5^12345#include#defineMAXN50#defineMAXN100structl_node{intver;structl_node*link;};typedefstructl_nodeL_NODE;typedefstruct{intver1;intver2;}E_NODE;L_NODE*head[MA
3、XN];intvisit[MAXN];E_NODEe[MAXN];intn,m,u;voidcreat_adj_list(head,n,e,m)L_NODE*head[];E_NODEe[];intn,m;{inti,u,v;L_NODE*p;for(i=1;i<=n;i++)head[i]=NULL;for(i=0;iver=v;p->link=head[u];
4、head[u]=p;p=(L_NODE*)moalloc(sizeof(L_NODE));p->ver=u;p->link=head[v];head[v]=p;}}voidinit(n)intn;{inti;for(i=1;i<=n;i++)visit[i]=0;}voiddfs(u)intu;{L_NODE*t;visit[u]=1;printf(“%d”,u);t=head[u];while(t!=NULL){if(visit[t->ver]==0)dfs(t->ver);t=t->link;}}
5、廣度優(yōu)先搜索法首先訪問出發(fā)點(diǎn)v然后訪問與頂點(diǎn)v鄰接的全部頂點(diǎn)w1,w2,….,wt再依次訪問與w1,w2,….,wt鄰接的全部結(jié)點(diǎn)(已訪問過的頂點(diǎn)除外)再從這些已訪問的頂點(diǎn)出發(fā),依次訪問與它們鄰接的全部頂點(diǎn)(已訪問的頂點(diǎn)除外)依次類推,直到圖中所有頂點(diǎn)都訪問到或出發(fā)頂點(diǎn)V所在的連通分量的所有頂點(diǎn)都有被訪問到為止123456789廣度優(yōu)先搜索法14253135^124135^234^234^5^12345廣度優(yōu)先搜索法把隊(duì)列置空輸出出發(fā)頂點(diǎn),置該頂點(diǎn)已被訪問的標(biāo)志讓出發(fā)頂點(diǎn)進(jìn)隊(duì)若隊(duì)列不空,則取出隊(duì)首中的
6、頂點(diǎn)V在鄰接表中,依次取得與頂點(diǎn)V鄰接的各個(gè)頂點(diǎn)轉(zhuǎn)(4)若隊(duì)列空,則處理過程結(jié)束voidbfs(u)intu;{structqueuetype{intqa;intqe;intitem[MAXN];}typedefstructqueuetypeQTYPE;intv,w;L_NODE*t;QTYPEqueue;printf(“%4d”,u);visit[u]=1;queue.qa=0;queue.qe=0queue.item[0]=u;while(queue.qa<=queue.qe){v=queue.i
7、tem[queue.qa++];t=head[v];while(t!=NULL){w=t->ver;if(visit[w]==0){printf(“%4d”,w);visit[w]=1;queue.item[++queue.qe]=w;}t=t->link;}}}求圖的連通分量對(duì)圖的每一個(gè)頂點(diǎn)進(jìn)行檢驗(yàn)若被訪問過,則該頂點(diǎn)落在已被求出的連通分量上若末被訪問過,則從該頂點(diǎn)出發(fā)遍歷圖,便可求得圖的另一個(gè)連通分量生成樹和最小生成樹生成樹:設(shè)G是一個(gè)連通無向圖,若G’是包含G中所有頂點(diǎn)的一個(gè)無回路的連通子圖,則
8、稱G’是G的一棵生成樹142536879142536879142536879生成樹從G中任一頂點(diǎn)出發(fā),遍歷圖中的所有頂點(diǎn),在遍歷過程中,將E分成兩個(gè)集合T(G)和B(G),其中T(G)是遍歷時(shí)所通過的邊集,B(G)是剩余的邊集,則G’=(V,T(G))是G的一棵生成樹dfs生成樹bfs生成樹14253687914253616918201914511622最小生成樹一個(gè)帶權(quán)連通無向圖G的最小生成樹是G的所有生成樹中邊上的權(quán)之和最小的一棵生成樹MST性質(zhì):設(shè)
