數(shù)據(jù)結(jié)構(gòu)電子科技第四章圖

4.3圖的遍歷深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點V0出發(fā)，訪問此頂點；然后依次從V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V3V6V7V5深度優(yōu)先遍歷算法遞歸算法開始訪問V0,置標志求V0鄰接點有鄰接點w求下一鄰接點wV0W訪問過結(jié)束NYNYDFS開始標志數(shù)組初始化Vi=1Vi訪問過DFSVi=Vi+1Vi==Vexnums結(jié)束NNYYCh6_1.cV1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdatafirstarc2783^^^adjvexnext55641^51282^678678736354^^^V3V7V6V2V5V8V4V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍歷：V1V3V7V6V2V4V8V5廣度優(yōu)先遍歷(BFS)方法：從圖的某一頂點V0出發(fā)，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8廣度遍歷：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V6V7V8V5廣度優(yōu)先遍歷算法開始標志數(shù)組初始化Vi=1Vi訪問過BFSVi=Vi+1Vi==Vexnums結(jié)束NNYYCh6_2.c開始訪問V0,置標志求V鄰接點ww存在嗎V下一鄰接點ww訪問過結(jié)束NYNYBFS初始化隊列V0入隊隊列空嗎隊頭V出隊訪問w,置標志w入隊NaaY例1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^220123451fr遍歷序列：10123454fr遍歷序列：1401234543fr遍歷序列：143例1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^22012345432fr遍歷序列：143201234532fr遍歷序列：1432012345325fr遍歷序列：1432501234525fr遍歷序列：143250123455fr遍歷序列/p>

fr遍歷序列：