數(shù)據(jù)結(jié)構(gòu)上機(jī)報(bào)告4圖.doc

數(shù)據(jù)結(jié)構(gòu)上機(jī)4實(shí)現(xiàn)最短路徑（單源、每對頂點(diǎn)）和最小生成樹（Prim）算法。2015、5、231、 需求分析 構(gòu)造一個(gè)圖，實(shí)現(xiàn)單源最短路徑和每對頂點(diǎn)之間的最短路徑，并且實(shí)現(xiàn)最小生成樹，將結(jié)果顯示在屏幕上輸出。 輸入數(shù)據(jù)類型：構(gòu)造圖的數(shù)據(jù)是整型數(shù)字。 程序功能：輸入或者從文件讀取構(gòu)造圖的參數(shù)，進(jìn)行構(gòu)圖，并計(jì)算出單源最短路徑和每個(gè)頂點(diǎn)最短路徑，實(shí)現(xiàn)最小生成樹。測試數(shù)據(jù)：正確輸入：錯(cuò)誤輸入：2、 概要設(shè)計(jì)圖ADT的定義：class Graphpublic:int numVertex;int numEdge;int *Mark;int *Indegree;Graph(int numVert) /有參構(gòu)造函數(shù)，動(dòng)態(tài)創(chuàng)建標(biāo)記和度的數(shù)組，初始化邊數(shù)、度數(shù)和訪問numVertex=numVert;numEdge=0; Indegree=new intnumVertex;Mark=new intnumVertex;for(int i=0;i0&ed.weight=0)return true;return false;virtual Edge FirstEdge(int oneVertex)=0; /返回與頂點(diǎn)oneVertex相關(guān)聯(lián)的第一條邊 virtual Edge NextEdge(Edge preEdge)=0; /返回與邊PreEdge有相同關(guān)聯(lián)頂點(diǎn)oneVertex的下一條邊 int EdgesNum() /返回圖的邊數(shù)return numEdge;int FromVertex(Edge oneEdge) /返回邊oneEdge的始點(diǎn)return oneEdge.from;int ToVertex(Edge oneEdge) /返回邊oneEdge的終點(diǎn)return oneEdge.to;int Weight(Edge oneEdge) /返回邊oneEdge的權(quán)return oneEdge.weight;virtual void setEdge(int from,int to,int weight)=0; /虛函數(shù)，設(shè)置邊的起點(diǎn)終點(diǎn)以及權(quán)值，在子類實(shí)例化virtual void delEdge(int from,int to)=0;Main()開始主程序流程：根據(jù)選擇執(zhí)行單源最短、頂點(diǎn)最短還是生成樹結(jié)束 選擇2 選擇1 錯(cuò)誤輸入 正確輸入錯(cuò)誤選項(xiàng) 正確選項(xiàng)3、 詳細(xì)設(shè)計(jì) 1、實(shí)現(xiàn)ADT的數(shù)據(jù)類型：整型數(shù)字； 2、算法描述：單源最短：初始集合S只包含源點(diǎn)s，即S=s。設(shè)v是V中某頂點(diǎn)，把從s到v且中間只經(jīng)過集合S中頂點(diǎn)的路徑稱“從源到v的特殊路徑”，用一維數(shù)組D記錄當(dāng)前找到的從s到每個(gè)頂點(diǎn)的最短特殊路徑長度。D初始，若s到v有弧, Dv存弧的權(quán)值，否則存。取最小，每次從集合V-S中取出一個(gè)最短特殊路徑長度最小的頂點(diǎn)u，將u加入集合S，修改權(quán)值(修改D中未求出的最短路徑長度)：由于引入u，對未求出最短路徑的頂點(diǎn)i進(jìn)行判斷，若滿足：Di Du+W u, i 則改為最短，令Di = Du+W u, i 另設(shè)立存儲最短路徑中當(dāng)前頂點(diǎn)前驅(qū)頂點(diǎn)域pre，用于存頂點(diǎn)u。 每對頂點(diǎn)最短路徑算法： 遞歸地產(chǎn)生一個(gè)矩陣序列adj(0)，adj(1)， adj(k) ， adj(n)adj(k)i，j等于從頂點(diǎn)Vi到頂點(diǎn)Vj中間頂點(diǎn)序號不大于k的最短路徑長度。假設(shè)已求得矩陣adj(k-1)，那么從頂點(diǎn)Vi到頂點(diǎn)Vj中間頂點(diǎn)的序號不大于k的最短路徑有兩種情況： 一種是中間不經(jīng)過頂點(diǎn)Vk，那么就有adj(k)i，j=adj(k-1)i，j另一種是中間經(jīng)過頂點(diǎn)Vk，那么adj(k)i，j adj(k-1)i，j，且adj(k)i，j= adj(k-1)i，k+ adj(k-1)k，j。 Prim最小生成樹算法： 從圖中任意一個(gè)頂點(diǎn)開始，首先把這個(gè)頂點(diǎn)包括在MST里，然后在那些其一個(gè)端點(diǎn)已在MST里，另一個(gè)端點(diǎn)還未在MST里的邊中，找權(quán)最小的一條邊，并把這條邊和其不在MST里的那個(gè)端點(diǎn)包括進(jìn)MST里。如此進(jìn)行下去，每次往MST里加一個(gè)頂點(diǎn)和一條權(quán)最小的邊，直到把所有的頂點(diǎn)都包括進(jìn)MST里。4、 調(diào)試分析在實(shí)現(xiàn)每個(gè)頂點(diǎn)最短路徑和最小生成樹的過程中出現(xiàn)好多次錯(cuò)誤，最后是借鑒參考了好多類似程序才完成。5、 使用說明界面有提示會如何輸入數(shù)據(jù)，選擇相應(yīng)的選項(xiàng)就會按步驟構(gòu)建出圖。6、 測試結(jié)果手動(dòng)輸入數(shù)據(jù)進(jìn)行構(gòu)圖：選擇保存的文件進(jìn)行構(gòu)圖：7、 源程序#include#include #include #include#define UNVISITED 0#define VISITED 1#define INFINITY 9999999#define ROOT -1using namespace std;class Edgepublic:int from,to,weight;Edge()from=-1;to=-1;weight=0;Edge(int f,int t,int w)from=f;to=t;weight=w;class Graphpublic:int numVertex;int numEdge;int *Mark;int *Indegree;Graph(int numVert) /有參構(gòu)造函數(shù)，動(dòng)態(tài)創(chuàng)建標(biāo)記和度的數(shù)組，初始化邊數(shù)、度數(shù)和訪問numVertex=numVert;numEdge=0; Indegree=new intnumVertex;Mark=new intnumVertex;for(int i=0;i0&ed.weight=0)return true;return false;virtual Edge FirstEdge(int oneVertex)=0; /返回與頂點(diǎn)oneVertex相關(guān)聯(lián)的第一條邊 virtual Edge NextEdge(Edge preEdge)=0; /返回與邊PreEdge有相同關(guān)聯(lián)頂點(diǎn)oneVertex的下一條邊 int EdgesNum() /返回圖的邊數(shù)return numEdge;int FromVertex(Edge oneEdge) /返回邊oneEdge的始點(diǎn)return oneEdge.from;int ToVertex(Edge oneEdge) /返回邊oneEdge的終點(diǎn)return oneEdge.to;int Weight(Edge oneEdge) /返回邊oneEdge的權(quán)return oneEdge.weight;virtual void setEdge(int from,int to,int weight)=0; /虛函數(shù)，設(shè)置邊的起點(diǎn)終點(diǎn)以及權(quán)值，在子類實(shí)例化virtual void delEdge(int from,int to)=0;templateclass Linkpublic:Elem element; /表目的數(shù)據(jù)Link *next; /表目指針，指向下一個(gè)表目Link(const Elem& elemval,Link *nextval=NULL) /構(gòu)造函數(shù) element=elemval; next=nextval; Link(Link *nextval=NULL) /構(gòu)造函數(shù) next=nextval; ;/鏈表templateclass LListpublic:Link* head; /head指針并不儲存任何實(shí)際元素，其存在只是為了操作方便LList() /構(gòu)造函數(shù)head=new Link();void removeall() /釋放邊表所有表目占據(jù)的空間Link *fence;while(head!=NULL) /逐步釋放每個(gè)表目占據(jù)的空間 fence=head;head=head-next;delete fence;LList() removeall(); /析構(gòu)函數(shù);struct listUnit /鄰接表表目中數(shù)據(jù)部分的結(jié)構(gòu)定義int vertex; /邊的終點(diǎn)int weight; /邊的權(quán);class Graphl: public Graph friend class Graphdup; /Graphdup是下面我們將討論的鄰接多重表的實(shí)現(xiàn)方式private:LList *graList; /graList是保存所有邊表的數(shù)組public:Graphl(int numVert):Graph(numVert) /構(gòu)造函數(shù)graList=new LListnumVertex; /為graList數(shù)組申請空間，圖有numVertex個(gè)頂點(diǎn)，則有numVertex個(gè)邊表Graphl() /析構(gòu)函數(shù)delete graList;/釋放空間Edge FirstEdge(int oneVertex) /返回頂點(diǎn)oneVertex的第一條邊Edge myEdge; /邊myEdge將作為函數(shù)的返回值myEdge.from=oneVertex; /將頂點(diǎn)oneVertex作為邊myEdge的始點(diǎn)Link *temp=graListoneVertex.head; /graListoneVertex.head保存的是頂點(diǎn)oneVertex的邊表，temp-next指向頂點(diǎn)oneVertex的第一條邊(如果temp-next不為null)if(temp-next!=NULL) /如果頂點(diǎn)oneVertex的第一條邊確實(shí)存在myEdge.to=temp-next-element.vertex;myEdge.weight=temp-next-element.weight;return myEdge; /如果找到了頂點(diǎn)oneVertex的第一條邊,則返回的myEdge確實(shí)是一條邊;如果沒有找到頂點(diǎn)oneVertex的第一條邊,則myEdge的成員變量to為-1,根據(jù)IsEdge函數(shù)判斷可知myEdge不是一條邊Edge NextEdge(Edge preEdge) /返回與邊PreEdge有相同關(guān)聯(lián)頂點(diǎn)oneVertex的下一條邊Edge myEdge; /邊myEdge將作為函數(shù)的返回值myEdge.from=preEdge.from; /將邊myEdge的始點(diǎn)置為與上一條邊preEdge的始點(diǎn)相同Link *temp=graListpreEdge.from.head; /graListoneVertex.head保存的是頂點(diǎn)oneVertex的邊表，temp-next指向頂點(diǎn)oneVertex的第一條邊(如果temp-next不為null)while(temp-next!=NULL&temp-next-element.vertexnext指針指向下一條邊的表目temp=temp-next;if(temp-next!=NULL) /邊preEdge的下一條邊存在 myEdge.to=temp-next-element.vertex;myEdge.weight=temp-next-element.weight;return myEdge;void setEdge(int from,int to,int weight) /為圖設(shè)定一條邊Link *temp=graListfrom.head; /graListfrom.head保存的是頂點(diǎn)from的邊表，temp-next指向頂點(diǎn)from的第一條邊(如果temp-next不為null)while(temp-next!=NULL&temp-next-element.vertexto) /確定邊(from,to)或在邊表中的位置,如果不存在,則邊(from,to)或?yàn)樾录拥囊粭l邊temp=temp-next;if(temp-next=NULL) /邊(from,to)或在邊表中不存在且在邊表中其后已無其它邊,則在邊表中加入這條邊temp-next=new Link;temp-next-element.vertex=to;temp-next-element.weight=weight;numEdge+;Indegreeto+;return;if(temp-next-element.vertex=to) /邊(from,to)或在邊表中已存在,故只需要改變邊的權(quán)值 temp-next-element.weight=weight;return;if(temp-next-element.vertexto) /邊(from,to)或在邊表中不存在,但在邊表中其后存在其它邊,則在邊表中插入這條邊Link *other=temp-next;temp-next=new Link;temp-next-element.vertex=to;temp-next-element.weight=weight;temp-next-next=other;numEdge+;Indegreeto+;void delEdge(int from,int to) /刪掉圖的一條邊Link *temp=graListfrom.head; /graListfrom.head保存的是頂點(diǎn)from的邊表，temp-next指向頂點(diǎn)from的第一條邊(如果temp-next不為null)while(temp-next!=NULL&temp-next-element.vertexto) /確定邊(from,to)或在邊表中的位置(如果該邊存在)temp=temp-next;if(temp-next=NULL) return; /邊(from,to)或在邊表中不存在,則不需要做任何操作if(temp-next-element.vertex=to) /邊(from,to)或在邊表中存在且確定了該邊在邊表中的位置,則從邊表中將其刪掉Link *other=temp-next-next;delete temp-next;temp-next=other;numEdge-;Indegreeto-;void DFS(Graph& G, int V) /圖的深度優(yōu)先周游G.MarkV= VISITED; /標(biāo)記該點(diǎn)coutVt; /打印for(Edge e=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e) /由該點(diǎn)所連的邊進(jìn)行深度優(yōu)先周游if(G.MarkG.ToVertex(e)=UNVISITED) /訪問V鄰接到的未被訪問過的頂點(diǎn)，并遞歸地按照深度優(yōu)先的方式進(jìn)行周游DFS(G, G.ToVertex(e);void BFS(Graph& G, int V) /廣度優(yōu)先周游using std:queue;queue Q; /初始化廣度優(yōu)先周游要用到的隊(duì)列G.MarkV= VISITED; /訪問頂點(diǎn)V，并標(biāo)記其標(biāo)志位coutVt; /打印Q.push(V); /V入隊(duì)while(!Q.empty() /如果隊(duì)列仍然有元素int V=Q.front(); /頂部元素Q.pop(); /出隊(duì)for(Edge e=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e) /將與該點(diǎn)相鄰的每一個(gè)未訪問點(diǎn)都入隊(duì)if(G.MarkG.ToVertex(e)= UNVISITED) /訪問V鄰接到的所有未被訪問過的頂點(diǎn)G.MarkG.ToVertex(e)= VISITED; /訪問頂點(diǎn)V，并標(biāo)記其標(biāo)志位 coutG.ToVertex(e)t; /打印Q.push(G.ToVertex(e); /入隊(duì)void graph_traverse(Graph &G,int fs) /選擇周游方式for(int i=0;iG.VerticesNum();i+) /對圖所有頂點(diǎn)的標(biāo)志位進(jìn)行初始化G.Marki=UNVISITED;for(i=0;iG.VerticesNum();i+) /檢查圖的所有頂點(diǎn)是否被標(biāo)記過，如果未被標(biāo)記，則從該未被標(biāo)記的頂點(diǎn)開始繼續(xù)周游 if(G.Marki= UNVISITED)if(fs=1)DFS(G,i); /深度優(yōu)先搜索if(fs=2)BFS(G,i); /廣度優(yōu)先搜索coutendl;void main()int choice,choice1,choice2;int isDirected; /標(biāo)記是否有向圖int numVertex; /圖的頂點(diǎn)個(gè)數(shù)（邊數(shù)將在setEdge中被自動(dòng)修改）int from,to,weight; /讀入每條邊的起點(diǎn)，終點(diǎn)和權(quán)char filename20;ifstream GraphSou; /輸入文件流string str;cout請選擇：endl;cout1：輸入構(gòu)圖的參數(shù)進(jìn)行圖的構(gòu)造！endl;cout2：選擇已經(jīng)存好的文件進(jìn)行圖的構(gòu)造！endl;cout輸入其它數(shù)字則無效choice;if(choice!=1&choice!=2)cout輸入有誤！endl;exit(0);if(choice=1)cout*endl;cout 0 表示構(gòu)造圖為無向圖，若是1則為有向圖endl;cout 6 表示構(gòu)造圖的頂點(diǎn)個(gè)數(shù)endl;cout 0 1 12 依次表示為圖的起點(diǎn)、終點(diǎn)以及權(quán)值endl;cout 1 2 21 endl;cout .endl;cout*endl;cout按以上格式輸入構(gòu)圖的參數(shù)，并以#結(jié)束：endl;getline(cin,str,#);cout請輸入想要保存圖的文件名：filename; /獲取文件名ofstream GraphSave(filename,ios:trunc);GraphSavestr;GraphSave.close();if(choice=2)cout請選擇文件：endl;cout1：a.txtendl;cout2：b.txtendl;cout3：c.txtchoice1;if(choice1=1)strcpy(filename,a.txt);if(choice1=2)strcpy(fi