實驗7 圖及圖的操作實驗

1、實驗報告七 圖及圖的操作實驗班級： 姓名： 學號： 專業(yè)： 一、 實驗目的：1、掌握圖的基本概念和術(shù)語2、掌握圖的存儲結(jié)構(gòu)及創(chuàng)建算法。3、掌握圖的遍歷算法（遞歸算法）。二、 實驗內(nèi)容：1、圖鄰接矩陣存儲結(jié)構(gòu)表示及基本操作算法實現(xiàn)實現(xiàn)提示 （同時可參見教材及ppt上的算法）函數(shù)、類名稱等可自定義，部分變量請加上學號后3位。也可自行對類中所定義的操作進行擴展。所加載的庫函數(shù)或常量定義及類的定義：（1）鄰接矩陣存儲結(jié)構(gòu)類定義：自定義如下：const int MaxSize=4;const int INFINITY=65535;template <class T>class Mgraphp

2、ublic: Mgraph(T a,int n,int e); void PGraph();private: T vertexMaxSize; int arcMaxSizeMaxSize; int vertexNum,arcNum; void createUG(T a,int n,int e); void createUW(T a,int n,int e); void createHG(T a,int n,int e); void createHW(T a,int n,int e); ;（2）創(chuàng)建鄰接矩陣算法創(chuàng)建無向圖鄰接矩陣算法：template <class T>void Mg

3、raph<T>:createUG(T a,int n,int e) vertexNum=n; arcNum=e; int i,j,k; for (i=0; i<vertexNum; i+) vertexi=ai; for (i=0; i<vertexNum; i+) for (j=0; j<vertexNum; j+) arcij=0; for (k=0; k<arcNum; k+) cout<<"請輸入第"<<k+1<<"條邊(格式：頂點1 頂點2):" cin>>i&

4、gt;>j; arcij=1; arcji=1; 創(chuàng)建無向網(wǎng)鄰接矩陣算法：template <class T>void Mgraph<T>:createUW(T a,int n,int e) int w; vertexNum=n; arcNum=e; int i,j,k; for (i=0; i<vertexNum; i+) vertexi=ai; for (i=0; i<vertexNum; i+) for (j=0; j<vertexNum; j+) arcij=INFINITY; for (k=0; k<arcNum; k+) cou

5、t<<"請輸入第"<<k+1<<"條邊(格式：頂點1 頂點2 權(quán)值):" cin>>i>>j>>w; arcij=w; arcji=w; 創(chuàng)建有向圖鄰接矩陣算法：template <class T>void Mgraph<T>:createHG(T a,int n,int e) vertexNum=n; arcNum=e; int i,j,k; for (i=0; i<vertexNum; i+) vertexi=ai; for (i=0; i<v

6、ertexNum; i+) for (j=0; j<vertexNum; j+) arcij=0; for (k=0; k<arcNum; k+) cout<<"請輸入第"<<k+1<<"條邊(格式：頂點1 頂點2):" cin>>i>>j; arcij=1; 創(chuàng)建有向網(wǎng)鄰接矩陣算法：template <class T>void Mgraph<T>:createHW(T a,int n,int e) int w; vertexNum=n; arcNum=e;

7、int i,j,k; for (i=0; i<vertexNum; i+) vertexi=ai; for (i=0; i<vertexNum; i+) for (j=0; j<vertexNum; j+) arcij=INFINITY; for (k=0; k<arcNum; k+) cout<<"請輸入第"<<k+1<<"條邊(格式：頂點1 頂點2 權(quán)值):" cin>>i>>j>>w; arcij=w;（3）輸出鄰接矩陣結(jié)果算法template <

8、class T>void Mgraph<T>:PGraph()int i,j;for(i=0;i<vertexNum;i+)for(j=0;j<vertexNum;j+)cout<<arcij<<endl;cout<<endl;測試結(jié)果粘貼如下：無向圖無向網(wǎng)有向圖有向網(wǎng)2、圖鄰接表存儲結(jié)構(gòu)表示及基本操作算法實現(xiàn)實現(xiàn)提示函數(shù)、類名稱等可自定義，部分變量請加上學號后3位。也可自行對類中所定義的操作進行擴展。所加載的庫函數(shù)或常量定義及類的定義：（1）鄰接表存儲結(jié)構(gòu)類定義：自定義如下：#include<iostream>us

9、ing namespace std;const int MaxSize=4;class ArcNodepublic: int adjvex; ArcNode *nextarc; int info;template <class T> class BGraph;template <class T>class VertexNode friend class BGraph<T> T vex; ArcNode *firstarc;template <class T>class BGraphpublic: BGraph(T a , int n, int e

10、); BGraph(); void pGraph();private: VertexNode<T> adjlistMaxSize; int vertexNum, arcNum;（2）創(chuàng)建鄰接表算法創(chuàng)建無向網(wǎng)鄰接表算法：template <class T>BGraph<T>:BGraph(T a , int n, int e)int i,j,k,w;ArcNode *E;vertexNum=n;arcNum=e; for(i=0;i<vertexNum;i+)adjlisti.vex=ai; adjlisti.firstarc=NULL;for(k=0;

11、k<arcNum;k+) cout<<"請輸入第"<<k+1<<"條弧的信息（格式為：頂點1 頂點2 權(quán)值）" cin>>i>>j>>w;E=new ArcNode;E->info=w;E->adjvex=j;E->nextarc=adjlisti.firstarc;adjlisti.firstarc=E;E=new ArcNode;E->info=w;E->adjvex=i;E->nextarc=adjlistj.firstarc;adjl

12、istj.firstarc=E;創(chuàng)建有向網(wǎng)鄰接表算法：template <class T>BGraph<T>:BGraph(T a , int n, int e)int i,j,k,w;ArcNode *E;vertexNum=n;arcNum=e; for(i=0;i<vertexNum;i+)adjlisti.vex=ai; adjlisti.firstarc=NULL;for(k=0;k<arcNum;k+) cout<<"請輸入第"<<k+1<<"條弧的信息（格式為：頂點1 頂點2 權(quán)值）" cin>>i>>j>>w;E=new ArcNode;E->info=w;E->adjvex=j;E->nextarc=adjlisti.firstarc;adjlisti.firstarc=E;（3）輸出鄰接表結(jié)果算法template <class T>void BGraph<T>:pGraph()for(int i=0;i<vertexNum;i+)ArcNode *E;E=adjlisti.firstarc;while(E) cout<<E-