非線性數(shù)據(jù)結(jié)構(gòu)hppt課件-資料下載頁
2025-05-07 08:25本頁面
【正文】 lass T2 static Link_GPT1,T2::dfs(gpnodeT1,T2* q, int k , int * mark) { nodeT1 *p。 cout(q+k)data“ ”。 mark[k] = 1。 p= (q+k)link。 while ( p!= NULL ) { if (mark[(pnum)1] == 0) dfs(q , pnum1,mark)。 p=pnext。 } return。 } 課堂練習(xí) 2. 廣度優(yōu)先遍歷算法 ? 先訪問第 1個頂點(diǎn)所有鄰接點(diǎn)后，再訪問下一個頂點(diǎn)所有未被訪問的鄰接點(diǎn) 。 ? 算法思想： ? step1 從圖中某個頂點(diǎn) V0出發(fā)，并訪問此頂點(diǎn)； ? step2 從 V0出發(fā)，訪問 V0的各個未曾訪問的鄰接點(diǎn) W1， W2， … ,Wk。然后 ,依此從 W1,W2,… ,Wk出發(fā)訪問各自未被訪問的鄰接點(diǎn)。 ? step3 重復(fù) step2，直到全部頂點(diǎn)都被訪問為止。 廣度（寬度）優(yōu)先搜索 : 圖的廣度優(yōu)先的訪問次序： 1 1 9 適用的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列 1 2 12 11 3 6 7 10 4 5 8 9 1 2 12 11 3 6 7 10 4 5 8 9 遍歷產(chǎn)生的結(jié)果 ? 廣度優(yōu)先遍歷 G6所走過的序列： V1? V3 ? V2 ? V4 ? V5 ? V6 ? 所走過的邊： (V1， V3） ， （ V1， V2） ， （ V1， V4） ， （ V3， V5） ， （ V4， V6） V1 V3 V5 V4 V6 G6 V2 課堂練習(xí) template class T1,class T2 void Link_GPT1,T2:: BFS_link_GP() { int *mark 。 nodeT1 * p。 sq_Queueint q(nn) 。 mark = new int[nn]。 for(k=0 。 k nn 。 k ++ ) mark[ k ]= 0。 for (k = 0。 k nn 。 k ++) if(mark[k] == 0) { mark [k]=1。 cout(gp+k) data 。 (k)。 while(() ) { k=()。 p=(gp+k)link。 while (p!= NULL) { k = pnum 1。 if(mark[k] == 0) { cout (gp+k)data “ ”。 mark[k] =1。 (k)。 } p = p next } } }// end of if cout endl 。delete mark 。 return 。} 總結(jié) 1. 圖的定義 2. 圖的基本概念 3. 圖的遍歷
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1