數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五圖的遍歷

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

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

2、的格式是.txt文件，其中存儲的數(shù)據(jù)組成如下:第一行:MN，M是圖中結(jié)點(diǎn)的個(gè)數(shù)，N是圖中弧的條數(shù)第二行:D，D是1或0,1表示該圖是一個(gè)有向圖，0表示該圖是一個(gè)無向圖第三行:M個(gè)互不相同的字符，代表每個(gè)結(jié)點(diǎn)的字符數(shù)據(jù)接下來的N行，每行有2個(gè)字母P1、P2，對于有向圖，表示存在一條從P1到P2的有向邊；對于無向圖，表示在P1和P2之間存在一條邊；1、程序中采用的圖的存儲結(jié)構(gòu)為鄰接表，對于有向圖，一條弧將存儲一個(gè)弧結(jié)點(diǎn)，對于無向圖，一條弧將存儲兩條弧結(jié)點(diǎn);2、測試數(shù)據(jù)：（1）、Graph1.txt891ABCDEFGHABACBDBECFCGEHGFHD（2）Graph2.txt761A

3、BCDEFGACBACBDEDFE（3）Graph3.txt980ABCDEFGHIABBCBHDHEHFHGHIH（4）Graph4.txt11120ABCDEFGHIJKABADBCCDEJEKFGFKGHHKIJIK一、概要設(shè)計(jì)1、圖的鄰接表的定義structArcNode//弧結(jié)點(diǎn)的定義{intadjvex;//鄰接點(diǎn)的位置ArcNode*nextarc;//下一條弧};structVNode//頂點(diǎn)結(jié)點(diǎn)的定義{chardata;//該頂點(diǎn)的數(shù)據(jù)域，這里簡化為一個(gè)字符boolvisited;//是否被訪問的標(biāo)志域，0未訪問，1已訪問ArcNode*firstarc;//指向第

4、一條以該頂點(diǎn)為出發(fā)點(diǎn)的弧//的指針域};structAlGraph//定義鄰接表表示的圖的數(shù)據(jù)結(jié)構(gòu){VNodevexs[MAXSIZE];//頂點(diǎn)向量intarcnum;//弧的數(shù)目intvexnum;//頂點(diǎn)的數(shù)目boolisDirected;//是否為有向圖的標(biāo)志域,1為有向，0為無//向};1、圖的鄰接表創(chuàng)建模塊StatuscreateAlGraph(AlGraph&g,stringfile)初始條件:file所指文件路徑是正確的參數(shù):g傳入要創(chuàng)建的鄰接表，file傳入圖的數(shù)據(jù)所在文件操作結(jié)果:創(chuàng)建一個(gè)鄰接表intlocateVex(AlGraphg,charvexdata)初

5、始條件:鄰接表g已經(jīng)初始化參數(shù):g傳入圖的鄰接表，vexdata傳入頂點(diǎn)字符數(shù)據(jù)，操作結(jié)果:返回所查詢頂點(diǎn)在鄰接表的頂點(diǎn)向量中的位置，若查詢失敗，返回-1StatusaddArc(AlGraph&g,intfrom,intto)初始條件:鄰接表g已經(jīng)初始化，from所指頂點(diǎn)位置合法，to所指頂點(diǎn)位置合法參數(shù):g傳入圖的鄰接表，from傳入起點(diǎn)的位置，to傳入終點(diǎn)的位置操作結(jié)果:在鄰接表中添加一條弧，如果是雙向圖，將通過添加2條弧來表示無向邊3、深度優(yōu)先遍歷和廣度優(yōu)先遍歷模塊voidDFS(AlGraph&g,intv,vector&edges)初始條件:g已經(jīng)初始化，v所

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

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