1、數據結構上機報告 4- 圖數據結構上機 4實現最短路徑（單源、每對頂點）和最小生成樹（ Prim ）算法。2015、 5、 23一、需求分析 構造一個圖，實現單源最短路徑和每對頂點之間的最短路徑，并且實現最 小生成樹，將結果顯示在屏幕上輸出。輸入數據類型：構造圖的數據是整型數字。 程序功能：輸入或者從文件讀取構造圖的參數，進行構圖，并計算出單源 最短路徑和每個頂點最短路徑，實現最小生成樹。測試數據：正確輸入：錯誤輸入：二、概要設計圖 ADT 的定義：class Graphpublic:int numVertex;int numEdge;int *Mark;int *Indegree;Graph

2、(int numVert) 度的數組，初始化邊數、度數和訪問 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;/返回與頂點 oneVertex 相關聯的第一條邊virtual Edge NextEdge(Edge preEdge)=0; 聯頂點 oneVertex 的下一條邊int EdgesNum(

3、)return numEdge;int FromVertex(Edge oneEdge) return oneEdge.from;int ToVertex(Edge oneEdge)/返回邊 oneEdge 的終點return oneEdge.to;int Weight(Edge oneEdge)/返回邊 oneEdge 的權return oneEdge.weight;/虛函數，設置邊的起virtual void setEdge(int from,int to,int weight)=0; 點終點以及權值，在子類實例化virtual void delEdge(int from,int to)=

4、0;主程序流程：Main(選正確輸入錯誤輸入錯誤選項正確選項根據選擇執行三、詳細設計1、實現 ADT 的數據類型：整型數字；2、算法描述：單源最短：初始集合 S 只包含源點 s，即 S=s。設 v 是 V 中某頂點，把從 s到 v 且中間只經過集合 S中頂點的路徑稱 “從源到 v 的特殊路徑”，用一維數組 D 記錄當前找到的從 s 到每個頂點的最短特殊 路徑長度。 D 初始，若 s到 v 有弧, Dv存弧的權值，否則存。取最小， 每次從集合 V-S 中取出一個最短特殊路徑長度最小的頂點 u，將 u 加入集 合 S，修改權值 ( 修改 D 中未求出的最短路徑長度 )：由于引入 u ，對未求 出最

5、短路徑的頂點 i 進行判斷，若滿足：Di Du+W u, i 則改為最短， 令 Di = Du+W u, i 另設立存儲最短路徑中當前頂點前驅頂點域 pre ， 用于存頂點 u。每對頂點最短路徑算法： 遞歸地產生一個矩陣序列 adj(0) ， adj(1) ， adj(k) ， adj(n) adj(k)i ，j 等于從頂點 Vi 到頂點 Vj 中間頂點序號不大于 k 的最短路徑長度。 假 設已求得矩陣 adj(k-1) ，那么從頂點 Vi 到頂點 Vj 中間頂點的序號不大于 k 的最 短路徑 有兩 種情況： 一種是 中間不經過頂點 Vk ，那么就 有 adj(k)i ， j=adj(k-1)

6、i ， j 另一種是中間經過頂點 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 最小生成樹算法： 從圖中任意一個頂點開始，首先把這個頂點包括在 MST 里，然后在那些其一個 端點已在 MST 里，另一個端點還未在 MST 里的邊中，找權最小的一條邊，并 把這條邊和其不在 MST 里的那個端點包括進 MST 里。如此進行下去，每次往 MST 里加一個頂點和一條權最小的邊，直到把所有的頂點都包括進 MST 里。四、調試分析 在實現每個頂點最短路徑和最小生成樹的過程中出現好多次錯誤，最后

7、是借鑒參考了好多類似程序才完成。五、使用說明界面有提示會如何輸入數據，選擇相應的選項就會按步驟構建出圖六、測試結果手動輸入數據進行構圖：選擇保存的文件進行構圖：七、源程序#include#include #include #include#define UNVISITED 0#define VISITED 1#define INFINITY 9999999#define ROOT -1 using namespace std;class Edgepublic:int from,to,weight;Edge() from=-1;to=-1;weight=0;Edge(int f,int t,in

8、t w) from=f;to=t;weight=w;class Graphpublic:int numVertex;int numEdge;int *Mark;int *Indegree;Graph(int numVert)/ 有參構造函數，動態創建標記和度的數組，初始化邊數、度數和訪問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

9、 oneVertex)=0;/ 返回與頂點 oneVertex 相關聯的第一條邊virtual Edge NextEdge(Edge preEdge)=0;/返回與邊 PreEdge 有相同關聯頂點 oneVertex 的下一條邊int EdgesNum()/ 返回圖的邊數return numEdge;/ 返回邊 oneEdge 的始點int FromVertex(Edge oneEdge) return oneEdge.from;int ToVertex(Edge oneEdge) return oneEdge.to;/ 返回邊 oneEdge 的終點int Weight(Edge oneE

10、dge)/ 返回邊 oneEdge 的權return oneEdge.weight;/虛函數，設置邊的起點virtual void setEdge(int from,int to,int weight)=0; 終點以及權值，在子類實例化virtual void delEdge(int from,int to)=0; ;template class Link public: Elem element;/ 表目的數據Link *next;/ 表目指針，指向下一個表目Link(const Elem& elemval,Link *nextval=NULL)/ 構造函數element=elemval;

11、next=nextval;Link(Link *nextval=NULL)/ 構造函數next=nextval;/鏈表 templateclass LListpublic:Link* head; /head 指針并不儲存任何實際元素，其存在只是為了操 作方便LList()/構造函數head=new Link();void removeall()/釋放邊表所有表目占據的空間Link *fence; while(head!=NULL)/逐步釋放每個表目占據的空間fence=head;head=head-next;delete fence;LList() removeall(); / 析構函數 ;s

12、truct listUnitint vertex;int weight;/鄰接表表目中數據部分的結構定義/邊的終點/邊的權class Graphl: public Graph friend class Graphdup; 實現方式/Graphdup 是下面我們將討論的鄰接多重表的private:LList *graList; /graList 是保存所有邊表的數組public:Graphl(int numVert):Graph(numVert)graList=new LListnumVertex; / numVertex 個頂點，則有 numVertex 個邊表 /構造函數為 graList

13、數組申請空間， 圖有Graphl()/析構函數delete graList;/釋放空間Edge FirstEdge(int oneVertex) 邊/ 返回頂點 oneVertex 的第一條*temp=graListoneVertex.head;Edge myEdge; 返回值myEdge.from=oneVertex; myEdge 的始點Link/ 邊 myEdge 將作為函數的/ 將頂點 oneVertex 作為邊/graListoneVertex.head 保存的是頂點 oneVertex 的邊表， temp-next 指向頂 點 oneVertex 的第一條邊 ( 如果 temp-n

14、ext 不為 null)if(temp-next!=NULL)/ 如果頂點 oneVertex 的第一條邊確實存在myEdge.to=temp-next-element.vertex;myEdge.weight=temp-next-element.weight;return myEdge;/如果找到了頂點 oneVertex 的第一條邊 ,則返回的 myEdge 確實是一條邊 ; 如果沒有找到頂點 oneVertex 的第一 條邊 ,則 myEdge 的成員變量 to 為-1,根據 IsEdge 函數判斷可知 myEdge 不是一 條邊Edge NextEdge(Edge preEdge) 聯

15、頂點 oneVertex 的下一條邊 Edge myEdge; 回值myEdge.from=preEdge.from; 上一條邊 preEdge 的始點相同Link /graListoneVertex.head 保存的是頂點/ 返回與邊 PreEdge 有相同關/ 邊 myEdge 將作為函數的返/將邊 myEdge 的始點置為與*temp=graListpreEdge.from.head;oneVertex 的邊表， temp-next 指向頂點 oneVertex 的第一條邊 ( 如果 temp-next 不為 null)while(temp-next!=NULL&temp-next-el

16、ement.vertexnext 指針指向下一條邊的表目 temp=temp-next;/邊 preEdge 的下一條邊存在if(temp-next!=NULL)myEdge.to=temp-next-element.vertex; myEdge.weight=temp-next-element.weight;/為圖設定一條邊return myEdge;void setEdge(int from,int to,int weight)Link *temp=graListfrom.head; /graListfrom.head 保存的 是頂點 from 的邊表， temp-next 指向頂點 fr

17、om 的第一條邊 (如果 temp-next 不為 null)while(temp-next!=NULL&temp-next-element.vertexto) / 確定邊 (from,to) 或 在邊表中的位置 ,如果不存在 ,則邊 (from,to) 或 為 新加的一條邊temp=temp-next;if(temp-next=NULL) /邊 (from,to) 或 在邊表 中不存在且在邊表中其后已無其它邊 ,則在邊表中加入這條邊 temp-next=new Link; temp-next-element.vertex=to; temp-next-element.weight=weight

18、; numEdge+;Indegreeto+;return;if(temp-next-element.vertex=to) /邊(from,to) 或 在邊表中已 存在 ,故只需要改變邊的權值 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-el

19、ement.weight=weight; temp-next-next=other;numEdge+;Indegreeto+;void delEdge(int from,int to)/ 刪掉圖的一條邊Link *temp=graListfrom.head; /graListfrom.head 保 存的是頂點 from 的邊表， temp-next 指向頂點 from 的第一條邊 ( 如果 temp-next 不為 null)while(temp-next!=NULL&temp-next-element.vertexto) / 確定邊 (from,to) 或 在邊表中的位置 (如果該邊存在 )

20、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) G.MarkV= VISITED; coutVt;/圖的深度優先周游/標記該點

21、/打印/訪問 V 鄰接到for(Edge e=G.FirstEdge(V);G .IsEdge(e);e=G .NextEdge(e) / 由該點所連的邊 進行深度優先周游if(G .MarkG .ToVertex(e)=UNVISITED)的未被訪問過的頂點，并遞歸地按照深度優先的方式進行周游DFS(G, G.ToVertex(e);void BFS(Graph& G , int V) using std:queue;queue Q;G.MarkV= VISITED; coutVt;/廣度優先周游/初始化廣度優先周游要用到的隊列/訪問頂點/打印V，并標記其標志位while(!Q.empty(

22、)/如果隊列仍然有元素/頂部元素/出隊int V=Q.front();Q.pop();for(Edge e=G.FirstEdge(V);G .IsEdge(e);e=G .NextEdge(e) 相鄰的每一個未訪問點都入隊if(G.MarkG .ToVertex(e)= UNVISITED)/ 訪問 V 鄰接到的所有未被訪問過的頂點/將與該點G.MarkG .ToVertex(e)= VISITED;/訪問頂點 V ，并標記其標志位coutG .ToVertex(e)t;Q.push(G .ToVertex(e);/打印/入隊void graph_traverse(Graph &G ,int

23、 fs)for(int i=0;iG .VerticesNum();i+)G.Marki=UNVISITED;for(i=0;iG .VerticesNum();i+)/選擇周游方式/對圖所有頂點的標志位進行初始化/檢查圖的所有頂點是否被標記過，如果未被標記，則從該未被標記的頂點開始繼續周游if(G .Marki= UNVISITED)if(fs=1)/深度優先搜索DFS(G,i);if(fs=2)/廣度優先搜索BFS(G,i); coutendl; string str;void main()int choice,choice1,choice2;int isDirected;int numV

24、ertex;中被自動修改)int from,to,weight;char filename20; ifstream GraphSou;/標記是否有向圖/圖的頂點個數 （邊數將在 setEdge/讀入每條邊的起點，終點和權/輸入文件流cout 請選擇： endl;cout1 ：輸入構圖的參數進行圖的構造！ endl; cout2 ：選擇已經存好的文件進行圖的構造！ endl; cout 輸入其它數字則無效 choice;if(choice!=1&choice!=2) cout 輸入有誤！ endl; exit(0);if(choice=1)cout*endl;cout0表示構造圖為無向圖，若是 1 則為有向圖endl;cout6表示構造圖的頂點個數 endl;cout0 1 12依次表示為圖的起點、終點以及權值endl;cout1 2 21 endl;coutendl;cout* *endl;cout 按以上格式輸入構圖的參數，并以 #結束： endl; getline(cin,str,#);cout 請輸入想要保存圖的文件名： filename;/ 獲取文件名ofstream GraphSave(filename,ios:trunc);GraphSavestr;GraphSave.close();endl;a.txtendl;b.txten