數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告圖.docVIP

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)習(xí)報(bào)告 題 目：圖的基本操作學(xué) 號：1210522姓 名：何厚華年 級：大二學(xué) 院：計(jì)算機(jī)與控制工程學(xué)院專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)完成日期：2014年5月21日授課教師：辛運(yùn)幃目錄1.題目. 22.要求 . . . . . . . . . . . . . . . . . . . . . . . . 23.程序?qū)崿F(xiàn) . . . . . . . . . . . . . . . . . . . . . 3 3.1程序運(yùn)行及編譯環(huán)境 . . . . . . . . . . . . . . . . 3 3.2程序描述 . . . . . . . . . . . . . . . . . 3 3.3實(shí)現(xiàn)功能 . . . . . . . . . . . . . . . . . . 3 3.3.1子功能模塊 . . . . . . . . . . . . . . . . . 4 3.3.1.1 子功能模塊1 . . . . . . . . . . . . . . . 4 3.3.1.2子功能模塊2. . . . . . . . . . . . . . . 5 3.3.1.3子功能模塊3. . . . . . . . . . . . . . . 5 3.3.1.4子功能模塊4. . . . . . . . . . . . . . 5 3.3.1.5子功能模塊5. . . . . . . . . . . . . . . 5 3.3.2 數(shù)據(jù)結(jié)構(gòu). . . . . . . . . . . . . . . . . . . . 6 3.3.2.1 數(shù)據(jù)結(jié)構(gòu)的操作1 . . . . . . . . . . . . . 7 3.3.2.2 數(shù)據(jù)結(jié)構(gòu)的操作2 . . . . . . . . . . . . . 7 3.3.2.3 數(shù)據(jù)結(jié)構(gòu)的操作3 . . . . . . . . . . . 8 3.3.3算法及程序說明. . . . . . . . . . . . . . . . . . 13 3.4運(yùn)行結(jié)果 . . . . . . . . . . . . . . . . . . . 14 3.5尚未解決的問題 . . . . . . . . . . . . . . . . . . 161. 題目 圖的基本操作給定N個(gè)頂點(diǎn)、E條邊的圖G，完成圖的相關(guān)算法，具體要求如下：1 完成圖的創(chuàng)建方法，即從鍵盤或文件輸入圖的信息，建立圖的鄰接表或是鄰接矩陣存儲結(jié)構(gòu)。2 給出判定圖的性質(zhì)的算法，即能夠判定圖是否是有向圖、無向圖、有向無環(huán)圖、連通圖、哈密爾頓圖等。3 根據(jù)輸入的圖的性質(zhì)，實(shí)現(xiàn)以下算法（選擇其中一兩個(gè)）：l 如果圖是有向無環(huán)圖，則先實(shí)現(xiàn)圖的某種遍歷算法，在此基礎(chǔ)上實(shí)現(xiàn)圖的拓?fù)渑判蛩惴ā 如果圖是連通圖，則求出圖的最大生成樹（不是最小生成樹，參考講授的方法），即得到的生成樹權(quán)值之和最大。l 如果圖是無向圖，則以第一個(gè)頂點(diǎn)當(dāng)做源點(diǎn)，求出單源最短路徑。l 對于哈密爾頓圖，找出其哈密爾頓回路。2.要求：初始輸入數(shù)據(jù)的格式由自己定義，例如，輸入文件中保存的初始數(shù)據(jù)格式有以下兩種：格式一3 3 2 15 解釋：第一行是圖中所含頂點(diǎn)個(gè)數(shù)m，后面是m行m列數(shù)據(jù)，對應(yīng)鄰接矩陣。格式二3 41 2 31 3 22 3 13 1 5解釋：第一行是圖中所含頂點(diǎn)個(gè)數(shù)m和邊數(shù)e，后面是e條邊的信息，如1 2 3表示頂點(diǎn)1到頂點(diǎn)2有權(quán)值為3的邊。3. 程序?qū)崿F(xiàn) 3.1程序運(yùn)行及編譯環(huán)境程序是用Visual Studio 2010即VS10.0 編譯的?？梢栽趙indows系列的操作系統(tǒng)上運(yùn)行。 3.2程序描述 該程序主要用于實(shí)現(xiàn)圖的基本操作,包括：建立鄰接矩陣存儲結(jié)構(gòu)，給出判定圖的性質(zhì)的算法，即能夠判定圖是否是有向圖、無向圖、有向無環(huán)圖、連通圖、哈密爾頓圖等，然后在此基礎(chǔ)上，如果圖是連通圖，則求出圖的最大生成樹，如果圖是無向圖，則以第一個(gè)頂點(diǎn)當(dāng)做源點(diǎn)，求出單源最短路徑。其流程如下： A).程序讀取輸入文件，并生成相應(yīng)的數(shù)據(jù)結(jié)構(gòu)a. 用二維數(shù)組來聲明并存儲圖，完成初始化的工作b.建立圖的鄰接矩陣存儲c.生成圖的一步可達(dá)矩陣B).輸出相關(guān)信息 a.判斷圖是否是有向圖 b.判斷圖是否是無向圖 c.判斷圖是否是連通圖 d.判斷圖是否是有向無環(huán)圖 e.判斷圖是否是哈密頓圖C).編碼以及譯碼a.如果圖是連通圖，則求出圖的最大生成樹。b.如果圖是無向圖，則以第一個(gè)頂點(diǎn)當(dāng)做源點(diǎn)，求出單源最短路徑。D).完成3.3實(shí)現(xiàn)功能建立鄰接矩陣存儲結(jié)構(gòu)，給出判定圖的性質(zhì)的算法，即能夠判定圖是否是有向圖、無向圖、有向無環(huán)圖、連通圖、哈密爾頓圖等，然后在此基礎(chǔ)上，如果圖是連通圖，則求出圖的最大生成樹，如果圖是無向圖，則以第一個(gè)頂點(diǎn)當(dāng)做源點(diǎn)，求出單源最短路徑。3.3.1 子功能模塊 子功能按照是否對象的方法分類：數(shù)組的處理以及樹的處理；3.3.1.1 子功能模塊1/*函數(shù)原型：int Pow(int x,int base=10);*函數(shù)參數(shù)：x 表示指數(shù)*函數(shù)功能：求base的冪次*/int Pow(int x,int base=10)if(x=0) return 1;return base*Pow(x-1);3.3.1.2子功能模塊2/*函數(shù)原型：float Convert2Num(char* str)*函數(shù)參數(shù)：str 是文件流中的字符串*函數(shù)功能：把一個(gè)數(shù)字字符串轉(zhuǎn)化為一個(gè)數(shù)字*/float Convert2Num(char* str)float num=0;int i=0,dot=0;if(*str)=I)return INF;while(*(str+i)if(dot!=0) dot+;if(*(str+i)!=.)num=10*num+*(str+i)-0;else dot=1;i+;return dot=0?num:num/Pow(dot-1);3.3.1.3子功能模塊3函數(shù)功能：Mul矩陣平方放到result矩陣中Void SquareMatrix (int MulMAXNODESMAXNODES,int resultMAXNODESMAXNODES,int n) for(int k=0;kn;k+) for(int l=0;ln;l+) resultkl=0; for(int m=0;mn;m+) if(Mulkm*Mulml!=0) resultkl=1; break; 3.3.2 數(shù)據(jù)結(jié)構(gòu)/*圖這個(gè)數(shù)據(jù)結(jié)構(gòu)的定義，從文件讀入，用鄰接矩陣存儲NodesCount表示結(jié)點(diǎn)個(gè)數(shù)， AdjMatrixMAXNODESMAXNODES是鄰接矩陣 ConnectMAXNODESMAXNODES表示一步可達(dá)矩陣，其中點(diǎn)到自身為可達(dá)*/class Graphint NodesCount;float AdjMatrixMAXNODESMAXNODES;int ConnectMAXNODESMAXNODES;public:Graph(ifstream &fin);/從文件讀入圖的元素，建立鄰接矩陣bool IsUnDirectedGraph();/判斷是否是無向圖bool IsDirectedGraph();/判斷是否是有向圖bool IsDirectWithoutLoop();/判斷是否是有向無環(huán)圖bool IsConnected();/判斷是否是連通圖void Prim(int v);/從節(jié)點(diǎn)v開始，用類似prim算法的方法生成最大生成樹void floyd();/用floyd算法求任意兩個(gè)點(diǎn)之間的最短距離int GetNodesCount();/;3.3.2.1 數(shù)據(jù)結(jié)構(gòu)的操作1/*函數(shù)原型：Graph:Graph(ifstream &fin)*函數(shù)參數(shù)：fin 存放圖的文件*函數(shù)功能：構(gòu)造函數(shù)，把一個(gè)圖從文件讀入*/Graph:Graph(ifstream &fin)char a MAXLENGTH;. NodesCount=0;while(!fin.eof()i=0;while(fin.get(ch). if(!NodesCount)/NodesCount有數(shù)即不再讀入 NodesCount=Convert2Num(a); else num=Convert2Num(a); AdjMatrixidx/NodesCountidx%NodesCount=num;/鄰接矩陣 Connectidx/NodesCountidx%NodesCount=(num=INF&(idx/NodesCount!=idx%NodesCount)?0:1);/一步可達(dá)矩陣 idx+; 3.3.2.2 數(shù)據(jù)結(jié)構(gòu)的操作2/*函數(shù)原型：bool Graph:IsUnDirectedGraph()*函數(shù)參數(shù)：判斷圖是否是無向圖*實(shí)現(xiàn)方法：判斷鄰接矩陣是否是對稱的，如對稱，則無向*/bool Graph:IsUnDirectedGraph() for(int k=0;k NodesCount-1;k+) for(int l=k+1;lNodesCount;l+) if(AdjMatrixkl!=AdjMatrixlk) return false; return true;3.3.2.3 數(shù)據(jù)結(jié)構(gòu)的操作3/*函數(shù)原型：bool Graph:IsConnected()*實(shí)現(xiàn)方法：將一步可達(dá)矩陣依次平方，直到該乘積收斂得到的* 就是這個(gè)圖的可達(dá)矩陣，這個(gè)算法復(fù)雜度是o(n2lgn)由于一步可達(dá)矩陣的對角線的元素全為1，而且矩陣的乘法是邏輯乘，所以，這個(gè)矩陣原來的某個(gè)位置如果為1，那么一直為1，最后一定會收斂，這里是將這個(gè)矩陣平方后再平方，加快收斂速度，從而快速判斷這個(gè)圖是否是連通的*/bool Graph:IsConnected()int temp1MAXNODESMAXNODES;int temp2MAXNODESMAXNODES;int temp; for(int k=0;k NodesCount;k+) for(int l=0;lNodesCount;l+) temp1kl=Connectkl;/初始化temp1矩陣 doSquareMatrix(&temp10,&temp20,NodesCount);/temp2=temp12 for(int k=0;k NodesCount;k+) for(int l=0;lNodesCount;l+) temp=temp1kl; temp1kl=temp2kl; temp2kl=temp; while(!IsSameMatrix(&temp10,&temp20,NodesCount);/直到收斂，也即temp2=temp22 cout可達(dá)矩陣如下：endl;printMatrix(&temp20,NodesCount); if(IsFull(&temp20,NodesCount)/任兩點(diǎn)可達(dá)，圖是連通的 return true; return false;3.3.2.4 數(shù)據(jù)結(jié)構(gòu)的操作4/*函數(shù)原型：bool Graph:IsDirectWithoutLoop()*函數(shù)功能：判斷一個(gè)圖是否是有向無環(huán)圖*實(shí)現(xiàn)方法：把一步可達(dá)矩陣對角線的元素變成0，然后這些矩陣 依次平方,直到收斂，如果是有向無環(huán)圖，則對角線 上有非零的元素*/bool Graph:IsDirectWithoutLoop()if(IsUnDirectedGraph()|NodesCount=1)/單個(gè)結(jié)點(diǎn)或者無向圖，就不是有向無環(huán)圖return false;int AdjMAXNODESMAXNODES;int tempMAXNODESMAXNODES;int temp1, count=1; for(int k=0;k NodesCount;k+) for(int l=0;lNodesCount;l+) if(k!=l) Adjkl=Connectkl; else Adjkl=0;/對角元素為0 doSquareMatrix(&Adj0,&temp0,NodesCount);/temp=Adj2 count*=2; for(int k=0;k NodesCount;k+) if(tempkk!=0) return false; for(int l=0;lNodesCount;l+) temp1=tempkl; tempkl=Adjkl; Adjkl=temp1; while(count=NodesCount);/ cout如果下面矩陣對角線有非零元素，說明它是有環(huán)圖endl; printMatrix(&temp0,NodesCount); for(int n=0;nNodesCount;n+) if(tempnn!=0) return false; if(!IsFull(&temp0,NodesCount,0)/如果如果這個(gè)矩陣全部是0，那么這是一個(gè)哈密頓圖 cout這是一個(gè)哈密頓圖！endl; return true;3.3.2.5 數(shù)據(jù)結(jié)構(gòu)的操作5/*函數(shù)原型：void Graph:Prim(int v)*函數(shù)功能：仿照Prim算法，構(gòu)建最大生成樹*實(shí)現(xiàn)方法：從頂點(diǎn)v開始，選擇剩下的頂點(diǎn)中與v相連的具有最小權(quán)值的邊 加入到S集合中，然后不斷在這兩個(gè)集合里面找到兩個(gè)點(diǎn)使得它們之間的權(quán)重是這個(gè)二分圖里面最小的，直到集合S等于原來的頂點(diǎn)集為止*/void Graph:Prim(int v)bool IsUsedMAXNODES;/標(biāo)記這個(gè)點(diǎn)是在哪個(gè)集合中float max=0;/記錄最大權(quán)值int i,j,k,col,row;for(i=0;iNodesCount;i+)/NodesCount次循環(huán)IsUsedi=false;/初始化IsUsedv=true;for(i=1;iNodesCount;i+)max=0;for(j=0;jNodesCount;j+)for(k=0;kmax&AdjMatrixjkINF)/在兩個(gè)集合里挑出兩個(gè)元素，使得它們之間權(quán)值盡可能大max=AdjMatrixjk;/更新max的值row=j;col=k;IsUsedrow=IsUsedcol=true;/更新集合cout(row,col)權(quán)值為：maxendl;/輸出邊和權(quán)的構(gòu)造過程3.3.2.6 數(shù)據(jù)結(jié)構(gòu)的操作6/*函數(shù)原型：void Graph:floyd()*實(shí)現(xiàn)方法：弗洛伊德算法求任意兩個(gè)點(diǎn)之間的最短距離*/void Graph:floyd