數(shù)據(jù)結(jié)構(gòu)實驗五(圖的遍歷).doc

《數(shù)據(jù)結(jié)構(gòu)實驗五(圖的遍歷).doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)實驗五實驗報告實驗名稱：圖的遍歷姓名：黃州龍班級：08軟件工程A班學(xué)號：0825121022一、需求分析1、本實驗要求要利用圖論的一些基本概念和算法來實現(xiàn)對無向圖和有向圖的2種遍歷，分別是深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)，通過本實驗對圖遍歷算法的實現(xiàn)來幫助了解圖這一特殊(多對多)的數(shù)據(jù)結(jié)構(gòu)，以便在以后的實際應(yīng)用中可以以此為基礎(chǔ)來進行更好的軟件程序開發(fā)；2、該程序開始時是通過用戶輸入的圖的數(shù)據(jù)文件(.txt)所在的路徑來讀取對應(yīng)文件中的圖的數(shù)據(jù)，以此來構(gòu)建，進而調(diào)用遍歷算法函數(shù)來對圖進行遍歷，如果

2、文件不存在或路徑不正確，程序?qū)蟾驽e誤并終止；3、本程序讀取的文件的格式是.txt文件，其中存儲的數(shù)據(jù)組成如下:第一行:MN，M是圖中結(jié)點的個數(shù)，N是圖中弧的條數(shù)第二行:D，D是1或0,1表示該圖是一個有向圖，0表示該圖是一個無向圖第三行:M個互不相同的字符，代表每個結(jié)點的字符數(shù)據(jù)接下來的N行，每行有2個字母P1、P2，對于有向圖，表示存在一條從P1到P2的有向邊；對于無向圖，表示在P1和P2之間存在一條邊；1、程序中采用的圖的存儲結(jié)構(gòu)為鄰接表，對于有向圖，一條弧將存儲一個弧結(jié)點，對于無向圖，一條弧將存儲兩條弧結(jié)點

3、;2、測試數(shù)據(jù)：（1）、Graph1.txt891ABCDEFGHABACBDBECFCGEHGFHD（2）Graph2.txt761ABCDEFGACBACBDEDFE（3）Graph3.txt980ABCDEFGHIABBCBHDHEHFHGHIH（4）Graph4.txt11120ABCDEFGHIJKABADBCCDEJEKFGFKGHHKIJIK一、概要設(shè)計1、圖的鄰接表的定義structArcNode//弧結(jié)點的定義{intadjvex;//鄰接點的位置ArcNode*nextarc;//下一條弧};st

4、ructVNode//頂點結(jié)點的定義{chardata;//該頂點的數(shù)據(jù)域，這里簡化為一個字符boolvisited;//是否被訪問的標(biāo)志域，0未訪問，1已訪問ArcNode*firstarc;//指向第一條以該頂點為出發(fā)點的弧//的指針域};structAlGraph//定義鄰接表表示的圖的數(shù)據(jù)結(jié)構(gòu){VNodevexs[MAXSIZE];//頂點向量intarcnum;//弧的數(shù)目intvexnum;//頂點的數(shù)目boolisDirected;//是否為有向圖的標(biāo)志域,1為有向，0為無//向};1、圖的鄰接表創(chuàng)建模

5、塊StatuscreateAlGraph(AlGraph&g,stringfile)初始條件:file所指文件路徑是正確的參數(shù):g傳入要創(chuàng)建的鄰接表，file傳入圖的數(shù)據(jù)所在文件操作結(jié)果:創(chuàng)建一個鄰接表intlocateVex(AlGraphg,charvexdata)初始條件:鄰接表g已經(jīng)初始化參數(shù):g傳入圖的鄰接表，vexdata傳入頂點字符數(shù)據(jù)，操作結(jié)果:返回所查詢頂點在鄰接表的頂點向量中的位置，若查詢失敗，返回-1StatusaddArc(AlGraph&g,intfrom,intto)初始條件:鄰接表g已經(jīng)

6、初始化，from所指頂點位置合法，to所指頂點位置合法參數(shù):g傳入圖的鄰接表，from傳入起點的位置，to傳入終點的位置操作結(jié)果:在鄰接表中添加一條弧，如果是雙向圖，將通過添加2條弧來表示無向邊3、深度優(yōu)先遍歷和廣度優(yōu)先遍歷模塊voidDFS(AlGraph&g,intv,vector&edges)初始條件:g已經(jīng)初始化，v所指頂點位置存在參數(shù):g傳入圖的鄰接表，v傳入深度優(yōu)先搜索的起點位置，edges傳入用來存儲生成樹的邊的向量操作結(jié)果:從v位置的頂點遞歸地深度優(yōu)先搜索圖voidDFSVisit(AlG

7、raph&g,int&count)初始條件:g已經(jīng)初始化參數(shù):g傳入圖的鄰接表，count傳入深度優(yōu)先搜索使用的次數(shù)計數(shù)器操作結(jié)果:對整個圖進行深度優(yōu)先遍歷voidBFS(AlGraph&g,intv,vector&edges)初始條件:g已經(jīng)初始化，v所指頂點位置存在參數(shù):g傳入圖的鄰接表，v傳入廣度優(yōu)先搜索的起點位置edges傳入用來存儲生成樹邊的向量操作結(jié)果:從v位置的頂點遞歸地廣度優(yōu)先搜索圖voidBFSVisit(AlGraph&g,int&count)初始條件:g已經(jīng)初始化參數(shù):g傳入圖的鄰接

8、表，count傳入廣度優(yōu)先搜索使用的次數(shù)計數(shù)器操作結(jié)果:對整個圖進行廣度優(yōu)先遍歷一、詳細設(shè)計1、圖的鄰接表創(chuàng)建模塊StatuscreateAlGraph(AlGraph&g,stringfile){ifstreamis(file.c_str());is>>g.vexnum>>g.arcnum;//讀入定點數(shù)和弧的數(shù)目intisDirected=