實(shí)驗(yàn)7 圖及圖的操作實(shí)驗(yàn)

1、實(shí)驗(yàn)報(bào)告七 圖及圖的操作實(shí)驗(yàn)班級(jí)： 姓名： 學(xué)號(hào)： 專(zhuān)業(yè)： 一、 實(shí)驗(yàn)?zāi)康模?、掌握?qǐng)D的基本概念和術(shù)語(yǔ)2、掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)及創(chuàng)建算法。3、掌握?qǐng)D的遍歷算法（遞歸算法）。二、 實(shí)驗(yàn)內(nèi)容：1、圖鄰接矩陣存儲(chǔ)結(jié)構(gòu)表示及基本操作算法實(shí)現(xiàn)實(shí)現(xiàn)提示 （同時(shí)可參見(jiàn)教材及ppt上的算法）函數(shù)、類(lèi)名稱(chēng)等可自定義，部分變量請(qǐng)加上學(xué)號(hào)后3位。也可自行對(duì)類(lèi)中所定義的操作進(jìn)行擴(kuò)展。所加載的庫(kù)函數(shù)或常量定義及類(lèi)的定義：（1）鄰接矩陣存儲(chǔ)結(jié)構(gòu)類(lèi)定義：自定義如下：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)建無(wú)向圖鄰接矩陣算法：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<<"請(qǐng)輸入第"<<k+1<<"條邊(格式：頂點(diǎn)1 頂點(diǎn)2):" cin>>i&

4、gt;>j; arcij=1; arcji=1; 創(chuàng)建無(wú)向網(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<<"請(qǐng)輸入第"<<k+1<<"條邊(格式：頂點(diǎn)1 頂點(diǎn)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<<"請(qǐng)輸入第"<<k+1<<"條邊(格式：頂點(diǎn)1 頂點(diǎn)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<<"請(qǐng)輸入第"<<k+1<<"條邊(格式：頂點(diǎn)1 頂點(diǎn)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;測(cè)試結(jié)果粘貼如下：無(wú)向圖無(wú)向網(wǎng)有向圖有向網(wǎng)2、圖鄰接表存儲(chǔ)結(jié)構(gòu)表示及基本操作算法實(shí)現(xiàn)實(shí)現(xiàn)提示函數(shù)、類(lèi)名稱(chēng)等可自定義，部分變量請(qǐng)加上學(xué)號(hào)后3位。也可自行對(duì)類(lèi)中所定義的操作進(jìn)行擴(kuò)展。所加載的庫(kù)函數(shù)或常量定義及類(lèi)的定義：（1）鄰接表存儲(chǔ)結(jié)構(gòu)類(lèi)定義：自定義如下：#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ú)向網(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<<"請(qǐng)輸入第"<<k+1<<"條弧的信息（格式為：頂點(diǎn)1 頂點(diǎn)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<<"請(qǐng)輸入第"<<k+1<<"條弧的信息（格式為：頂點(diǎn)1 頂點(diǎn)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-