實驗四圖的操作及應(yīng)用

1、實驗四 圖的操作及應(yīng)用實驗課程名： 數(shù)據(jù)結(jié)構(gòu)與算法一、實驗?zāi)康募耙?、理解圖的基本概念及術(shù)語。2、掌握圖的兩種存儲結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法。3、熟練掌握圖的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲結(jié)構(gòu)上按上述兩種遍歷算法得到的序列。二、實驗內(nèi)容任務(wù)一：構(gòu)造如圖1所示的圖的鄰接矩陣存儲結(jié)構(gòu)和鄰接表存儲結(jié)構(gòu)。圖1解答：（1）源代碼：#include<iostream.h>#include <malloc.h> #include <conio.h> #define INFINITY 1000 #define M

2、AX_VERTEX_NUM 20 #define OK 1 #define STARTS "*" typedef enumDG,DN,UDG,UDN GraphKind; typedef int EType; typedef int InfoType; typedef int VertexType; typedef struct ArcCell /define structure MGraph EType adj; InfoType *info; ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct Ve

3、rtexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind; MGraph; int CreatUDN(MGraph &G) /CreatUDN() sub-function int IncInfo,i,j,k,v1,v2,w; cout<<endl<<"Please input the number of G.vexnum (eg,G.vexnum=4): " cin>>G.vexnum; /input the number of

4、vex cout<<"Please input the number of G.arcnum (eg,G.arcnum=4): " cin>>G.arcnum; /input the number of arc cout<<"Please input IncInfo (0 for none) : " cin>>IncInfo; for(i=0;i<G.vexnum;+i) for(j=0;j<G.vexnum;+j) G.arcsij.adj=INFINITY; /initial G.arcsi

5、j.adj G.=NULL; /initial G. cout<<"Plese input arc(V1->V2), For example: (V1=1,V2=3),(V1=2,V2=4)."<<endl; for(k=0;k<G.arcnum;+k) /input arc(v1,v2) cout<<endl<<"Please input the "<<k+1<<"th arc's v1 (0<v1&l

6、t;G.vexnum) :" cin>>v1; /input v1 cout<<"Please input the "<<k+1<<"th arc's v2 (0<v2<G.vexnum) :" cin>>v2; /input v2 cout<<"Please input the "<<k+1<<"th arc's weight :" cin>>w; /input wei

7、ght i=v1; j=v2;while(i<1|i>G.vexnum|j<1|j>G.vexnum) /if (v1,v2) illegal,again cout<<"Please input the "<<k+1<<"th arc's v1 (0<v1<G.vexnum) :" cin>>v1; cout<<"Please input the "<<k+1<<"th arc's v2 (

8、0<v1<G.vexnum) :" cin>>v2; cout<<"Please input the "<<k+1<<"th arc's weight :" cin>>w; i=v1; j=v2; /while end i-; j-; G.arcsij.adj=G.arcsji.adj=w; /weight cout<<"G.arcs"<<i+1<<""<<j+1<<

9、".adj="<<"G.arcs"<<j+1<<""<<i+1<<".adj="<<w<<endl; if(IncInfo) cout<<"Please input the "<<k+1<<"th arc's Info :" cin>>*G.; /for end return (OK); /CreatUDN() en

10、d void Gprintf(MGraph G) /打印鄰接矩陣 cout<<"鄰接矩陣數(shù)組為：n" for(int i=0;i<G.vexnum;i+) for(int k=0;k<G.vexnum;k+) cout<<G.arcsik.adj<<"t" cout<<endl; /*鄰接表*/ typedef struct ArcNode /define structure ALGraph int adjvex; struct ArcNode *nextarc; InfoType *info;

11、 ArcNode; typedef struct VNode VertexType data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum,arcnum; int kind; ALGraph; int CreateDG(ALGraph &G) /CreateDG() subfunction int IncInfo,i,j,k,v1,v2,w; cout<<endl<<"Please input the number

12、 of G.vexnum (eg,G.vexnum=4): " cin>>G.vexnum; /input the number of vex cout<<"Please input the number of G.arcnum (eg,G.arcnum=4): " cin>>G.arcnum; /input the numbe of arc cout<<"Please input the number of IncInfo (0 for none) : " cin>>IncInfo;

13、 /if no information, input 0 for(i=0;i<G.vexnum;+i) G.verticesi.data=i; /initial G.verticesi.data G.verticesi.firstarc=NULL; /initial G.verticesi.firstarc cout<<"Plese input arc(V1->V2), For example: (V1=1,V2=3),(V1=2,V2=4)."<<endl; for(k=0;k<G.arcnum;+k) /input arc(v1

14、,v2) cout<<endl<<"Please input the "<<k+1<<"th arc's v1 (0<v1<G.vexnum): " cin>>v1; cout<<"Please input the "<<k+1<<"th arc's v2 (0<v2<G.vexnum): " cin>>v2; i=v1; j=v2; while(i<1|i>

15、;G.vexnum|j<1|j>G.vexnum) /if (v1,v2) illegal cout<<endl<<"Please input the "<<k+1<<"th arc's v1 (0<v1<G.vexnum): " cin>>v1; cout<<"Please input the "<<k+1<<"th arc's v2 (0<v2<G.vexnum): &quo

16、t; cin>>v2; i=v1; j=v2; /while end i-; j-; ArcNode *p; p=(ArcNode *)malloc(sizeof(ArcNode); /allocate memory if(!p) cout<<"Overflow!" return (0); p->adjvex=j; /assign p->adjvex p->nextarc=G.verticesi.firstarc; p->info=NULL; G.verticesi.firstarc=p; if(IncInfo) cout&l

17、t;<"Please input the info :" cin>>*(p->info); /input information /for end return (OK); /CreateDG() end int main() MGraph MG; ALGraph AG; int a=-1; while(a!=0) cout<<STARTS<<STARTS<<endl; cout<<"(1)鄰接矩陣(無向網(wǎng))t"<<"(2)鄰接表(有向圖)t"<

18、<"(3)退出"<<endl; cout<<"選擇存儲方式:" cin>>a; switch(a) case 1: CreatUDN(MG);Gprintf(MG);break; case 2: CreateDG(AG);break; case 3: a=0;break; default:cout<<"選擇錯誤n"<<endl; return 0; （2）運行結(jié)果：（3） 運行結(jié)果分析： 運用數(shù)組與鏈表的結(jié)合來實現(xiàn)任務(wù)二：用鄰接表的存儲結(jié)構(gòu)創(chuàng)建一個如圖2所示的圖a，分別

19、打印出這兩個圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的結(jié)點信息序列。圖 20165948372(a)603451278(b)解答：（1）源代碼：#include<iostream>#include<string>#include<queue>using namespace std;#define ERROR 1#define MAX_VERTEX_NUM 100typedef struct ArcNode int adjvex; struct ArcNode *nextarc; string info;ArcNode;typedef struct VNode char

20、 date; ArcNode * firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum; /當(dāng)前圖的vexnum頂點數(shù)和arcnum弧數(shù) int kind;ALGraph;int LocateVex(ALGraph &G,char &v1) int i; for(i=0;i<G.vexnum;i+) if(G.verticesi.date=v1) return i; if(i>=G.vexnum) return ERROR; else retur

21、n 0;void CreateDG(ALGraph &G) ArcNode *p,*q; char v1,v2; char v; int i,j,k,n; cout<<"請輸入圖的頂點數(shù)和弧數(shù)："<<endl; cin>>G.vexnum; cin>>G.arcnum; cout<<"請輸入頂點："<<endl; for(i=0;i<G.vexnum;i+) cin>>v; G.verticesi.date=v; G.verticesi.firstarc=N

22、ULL; cout<<"請輸入弧尾和弧頭：" for(k=0;k<G.arcnum;k+) cin>>v1; cin>>v2; i=LocateVex(G,v1);j=LocateVex(G,v2); if(G.verticesi.firstarc=NULL) p=(ArcNode *)new ArcNode; G.verticesi.firstarc=p; q=G.verticesi.firstarc; else q=G.verticesi.firstarc; for(n=0;n<G.arcnum;n+,q=q->ne

23、xtarc) if(!q->nextarc) break; p=(ArcNode *)new ArcNode; q->nextarc=p; q=q->nextarc; q->adjvex=j; q->nextarc=NULL; cout<<"圖構(gòu)建成功！"/-深度優(yōu)先遍歷-/bool visitedMAX_VERTEX_NUM;int FirstAdjVex(ALGraph &G,int v) int i; int n=-1; ArcNode*p; p=G.verticesv.firstarc; if(p) i=p->

24、adjvex; if(visitedi=false) n=i; return n;int NextAdjVex(ALGraph &G,int v) int i; int n=-1; ArcNode *p; p=G.verticesv.firstarc; for(i=p->adjvex;i<G.vexnum,p!=NULL;) i=p->adjvex; if(visitedi=false) n=i; break; else p=p->nextarc; return n;void VisitFuc(ALGraph &G,int v) cout<<

25、G.verticesv.date<<" "void DFS(ALGraph &G,int v) int w; visitedv=true; VisitFuc(G,v); for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v) if(!visitedw) DFS(G,w);void DFSTraverse(ALGraph &G) int v; for(v=0;v<G.vexnum;v+) visitedv=false; cout<<"深度優(yōu)先搜索："<<en

26、dl; for(v=0;v<G.vexnum;v+) if(!visitedv) DFS(G,v); /-廣度優(yōu)先遍歷-/void BFSTraverse(ALGraph &G) int v; int w; queue<int> q; /STL隊列 for(v=0;v<G.vexnum;v+) visitedv=false;/ InitQueue(Q); cout<<"廣度優(yōu)先搜索：" for(v=0;v<G.vexnum;v+) if(!visitedv) visitedv=true; VisitFuc(G,v); q.push(v); /v進(jìn)隊 while(q.em