实验3--图的基本操作

实验3图的基本操作实验目的1.掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。2.遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。3.掌握以邻接矩阵作为存储结构的生成图的最小生成树的普里姆算法。实验内容1.输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。2.输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图3.深度优先遍历第一步中构造的图G，输出得到的节点序列函数说明1.typedefstructarc{intadjvex;structarc*next;}ArcNode;typedefstructVexNode{intvertex;ArcNode*firstarc;}VerNode;typedefVerNodeAdjList[MAXNODE];/邻接表的结点类型*/2.voidCreatAdjlist(AdjListGL)/*建立图的邻接表*/3.voidDfsAdjlist(AdjListGL,intv)/*从初始点v出发深度优先遍历邻接表GL表示的图*/4.voidBfsAdjlist(AdjListGL,intv)/*从初始点v出发广度优先遍历邻接表GL表示的图*/实验过程实验代码#includeiostream#includestring#includequeueusingnamespacestd;typedefstructedgenode{intadjvex;edgenode*next;}edgenode;//定义表结点typedefstructvexnode{stringdata;edgenode*link;}vexnode,AdjList[100];//定义头结点typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;//定义图intLocateVex(ALGraphG,stringu){for(inti=0;iG.vexnum;i++)if(G.vertices[i].data==u)returni;return-1;}//定位voidCreate(ALGraph&G){stringv1,v2;inti,j,k;cout”开始建图“;cout请输入结点个数，边数：;cinG.vexnumG.arcnum;cout请输入点：;for(i=0;iG.vexnum;i++){cinG.vertices[i].data;G.vertices[i].link=NULL;}cout输入边（V1，V2）：;coutendl;for(k=0;kG.arcnum;k++){cinv1v2;i=LocateVex(G,v1);j=LocateVex(G,v2);edgenode*p=newedgenode;p-adjvex=j;p-next=G.vertices[i].link;G.vertices[i].link=p;p=newedgenode;p-adjvex=i;p-next=G.vertices[j].link;G.vertices[j].link=p;}}//创建图intFirstAdjVex(ALGraphG,intv){edgenode*p=G.vertices[v].link;if(p)returnp-adjvex;elsereturn-1;}//头与否，是的话返回nextintNextAdjVex(ALGraphG,intv,intw){edgenode*p=G.vertices[v].link;while(p){if(p-adjvex==w)break;p=p-next;}if(p-adjvex!=w||!p-next)return-1;returnp-next-adjvex;}//下一个结点boolvisited[10];//数组，保存是否访问过voidDFS(ALGraphG,intv){visited[v]=true;coutG.vertices[v].data;for(intw=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);}//深度voidDFSS(ALGraphG){for(inti=0;iG.vexnum;i++)visited[i]=false;for(i=0;iG.vexnum;i++)if(!visited[i])DFS(G,i);}//深度优先准备与调用voidBFS(ALGraphG){queueintq;for(inti=0;iG.vexnum;i++)visited[i]=false;for(i=0;iG.vexnum;i++){if(!visited[i]){q.push(i);visited[i]=true;while(!q.empty()){intv=q.front();q.pop();coutG.vertices[v].data;for(intw=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)){if(!visited[w]){q.push(w);visited[w]=true;}}}}}}//广度voidmain(){ALGraphG;Create(G);cout深度优先遍历结果：endl;DFSS(G);coutendl;cout广度优先遍历结果：endl;BFS(G);coutendl;}//主函数代码调试1.此时的edgenode前漏掉了new,所以表达非法；2.此处应改为edgenode*p=G.vertices[v].link;3.将所有错误修改后运行出以下结果，发现没有广度优先遍历的结果仔细检查广度优先遍历的函数之后发现此处循环的结束条件出错，应改为while(!q.empty())实验结果