实验四图的操作及应用

1、实验四 图的操作及应用实验课程名： 数据结构与算法一、实验目的及要求1、理解图的基本概念及术语。2、掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法。3、熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列。二、实验内容任务一：构造如图1所示的图的邻接矩阵存储结构和邻接表存储结构。图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<<"邻接矩阵数组为：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)邻接矩阵(无向网)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）运行结果：（3） 运行结果分析： 运用数组与链表的结合来实现任务二：用邻接表的存储结构创建一个如图2所示的图a，分别

19、打印出这两个图的深度优先遍历和广度优先遍历的结点信息序列。图 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; /当前图的vexnum顶点数和arcnum弧数 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<<"请输入图的顶点数和弧数："<<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<<"图构建成功！"/-深度优先遍历-/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<<"深度优先搜索："<<en

26、dl; for(v=0;v<G.vexnum;v+) if(!visitedv) DFS(G,v); /-广度优先遍历-/void BFSTraverse(ALGraph &G) int v; int w; queue<int> q; /STL队列 for(v=0;v<G.vexnum;v+) visitedv=false;/ InitQueue(Q); cout<<"广度优先搜索：" for(v=0;v<G.vexnum;v+) if(!visitedv) visitedv=true; VisitFuc(G,v); q.push(v); /v进队 while(q.em