实训七 图的邻接矩阵和遍历.doc

姓名：刘草草 学号：201010520143 专业：10信息实训七 图的邻接矩阵和遍历一：实训目的1 掌握图的基本概念和邻接矩阵的存储结构。2 掌握图的邻接矩阵存储结构的算法实现。3 掌握图在邻接矩阵存储结构上遍历算法的实现。二：实训内容1 给定图如下，用邻接矩阵实现该图的深度优先搜索遍历。312457862 对第1题给定的图，用邻接矩阵实现它的广度优先搜索遍历。#includeconst int n=8;const int e=15;#define elemtype intbool visitedn+1;class graphpublic:elemtype vn+1;int arcsn+1n+1;void creatadj()int i,j,k;cout请输入n个顶点信息endl;for(k=1;kvk;for(i=1;i=n;i+)for(j=1;j=n;j+)arcsij=0;for(k=1;k=e;k+)cout请输入第k条边，共eij;coutendl;arcsij=1;arcsji=1;void dfs(int i)int j;coutvi ;visitedi=true;for(j=1;j=n;j+)if(arcsij=1)&(!visitedj)dfs(j);void bfs(int i)int qn+1;int f,r,j;f=r=0;coutvi ;visitedi=true;r+;qr=i;while(fr)f+;i=qf;for(j=1;j=n;j+)if(arcsij=1)&(!visitedj)coutvj ;visitedj=true;r+;qr=j;void main()int i,j;graph g;int yn=1;g.creatadj();for(i=0;i=n;i+)for(j=1;j=n;j+)coutg.arcsij ;coutendl;while(yn=1)for(i=1;i=n;i+)visitedi=false;couti;coutendl;cout从i出发的深度优先搜索遍历序列为endl;g.dfs(i);coutendlyn;yn=1;while(yn=1)for(i=1;i=n;i+)visitedi=false;couti;coutendl;cout从i出发的广度优先搜索遍历序列为endl; g.dfs(i); coutendlyn;实验结果：实训八、图的邻接表和遍历一：实训目的4 掌握图的基本概念和邻接表的存储结构。5 掌握图的邻接表存储结构的算法实现。6 掌握图在邻接表存储结构上遍历算法的实现。二：实训内容3 给定图如下，用邻接表实现该图的深度优先搜索遍历。4 对第1题给定的图，用邻接表实现它的广度优先搜索遍历。#includeconst int n=8;const int e=15;typedef int elemtype;bool visitedn+1;class linkpublic:elemtype data;link *next;class GRAPHpublic:link an+1;void creatlink()int i,j, k;link *s;for(i=1;i=n;i+)ai.data=i;ai.next=NULL;for(k=1;k=e;k+)coutij;coutdata=j;s-next=ai.next;ai.next=s;s=new link;s-data=i;s-next=aj.next;aj.next=s;void dfs1(int i)link *p;coutai.datadata)dfs1(p-data);p=p-next;void bfs1(int i)int qn+1;int f,r;link *p;f=r=0;coutai.data ;visitedi=true;r+;qr=i;while(fdata)coutdata.datadata=true;r+;qr=p-data;p=p-next;void main()link *p;int yn=1;GRAPH G;G.creatlink();while(yn=1)for(int i=1;i=n;i+)p=G.ai.next;coutG.ai.data;while(p-next!=NULL)coutdata;p=p-next;coutdataendl;for(i=1;i=n;i+)visitedi=false;couti;coutendl; cout从i出发的深度优先搜索遍历序列endl;G.dfs1(i);coutendl;for(i=1;i=n;i+)visitedi=false;couti;coutendl;cout从