《数据结构》实验报告3

实验三 图一、 实验目的1. 掌握图的基本概念；2. 掌握图的存储结构及其建立算法；3. 熟练掌握图的两种遍历算法及其应用。二、 实验内容1. 对给定的图G，设计算法输出从V0出发深（广）度遍历图G的深（广）度优先搜索序列；2. 设计算法输出给定图G的连通分量个数及边（或弧）的数目。三、 实验预习内容在实验中要用到这几个函数：typedef struct 邻接矩阵的创建，Locate函数去查找，create函数创建图，定义两个指针firstadj,nextadj找寻临接点和下一个临接点，void dfs函数从某一点开始遍历，void dfsgraph进行图的遍历算法，然后就是main 函数。四、 上机实验1. 实验源程序。#include#define max 80int num1=0,num2=0;bool visitedmax; /标记数组typedef struct /邻接矩阵char vexsmax;int arcsmaxmax;int vexnum,arcnum; graph;int locate(graph G,char v) /定位int i;for(i=0;iG.vexnum;i+)if(G.vexsi=v)return i;if(i=G.vexnum)return -1;void creat(graph &G) /创建图int i,j,k;char v1,v2;coutG.vexnumG.arcnum;coutPlease iput the chars in sequence:;for(i=0;iG.vexsi;for(i=0;iG.vexnum;i+) /二维数组初始化for(j=0;jG.vexnum;j+)G.arcsij=0;coutCreate the relationship between chars:n;for(k=1;k=G.arcnum;k+) /创建关系coutv1v2;i=locate(G,v1);j=locate(G,v2);G.arcsij=G.arcsji=1;int firstadj(graph G,int v) /第一个邻接点int i;for(i=0;iG.vexnum;i+)if(G.arcsvi)return i;if(i=G.vexnum)return -1;int nextadj(graph G,int v,int w) /下一个邻接点int i;for(i=w+1;iG.vexnum;i+)if(G.arcsvi)return i;if(i=G.vexnum)return -1;void dfsv(graph G,int v) /从某一点遍历int w;cout=0)num2+;if(!visitedw)dfsv(G,w);w=nextadj(G,v,w);void dfsgraph(graph G) /图的遍历int i;for(i=0;iG.vexnum;i+)visitedi=false;for(i=0;iG.vexnum;i+)if(!visitedi)dfsv(G,i);num1+;int main()graph G;int choice,flag=1; char ctinue;for(;flag=1;) coutt1.creat graphnt2.output graphnt3.the number of.nt4.the number of bianendl; coutchoice; switch(choice) case 1:creat(G);break;case 2:dfsgraph(G);coutendl;break; case 3:coutnum1endl;break; case 4:coutnum2/2endl;break; coutctinue; if(ctinue=Y|ctinue=y) flag=1; else flag=0;2. 实验结果（截图）。开始界面：创建函数界面：输出创建的函数：输出创建函数的连通分量：输出创建函数的边数：五、 实验总结（实验过程中出现的问题、解决方法、结果或其它）在这两个实验中，对locate 函数的编写存在问题，不知道自己怎么去定位，函数该怎么样编写后来用这样编写就可以了。int locate(graph G,char v) /定位int i;for(i=0;iG.vexnum;i+)if(G.vexsi=v)return i;if(i