实验3--图的基本操作.docx

《实验3--图的基本操作.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验3图的基本操作实验目的1.掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。2.遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。3.掌握以邻接矩阵作为存储结构的生成图的最小生成树的普里姆算法。实验内容1.输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。2.输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图3.深度优先遍历第一步中构造的图G，输出得到的节点序列函

2、数说明1.typedefstructarc{intadjvex;structarc*next;}ArcNode;typedefstructVexNode{intvertex;ArcNode*firstarc;}VerNode;typedefVerNodeAdjList[MAXNODE];/邻接表的结点类型*/2.voidCreatAdjlist(AdjListGL)/*建立图的邻接表*/3.voidDfsAdjlist(AdjListGL,intv)/*从初始点v出发深度优先遍历邻接表GL表示的图*

3、/4.voidBfsAdjlist(AdjListGL,intv)/*从初始点v出发广度优先遍历邻接表GL表示的图*/实验过程实验代码#include#include#includeusingnamespacestd;typedefstructedgenode{intadjvex;edgenode*next;}edgenode;//定义表结点typedefstructvexnode{stringdata;edgenode*link;}vexnode,

4、AdjList[100];//定义头结点typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;//定义图intLocateVex(ALGraphG,stringu){for(inti=0;i

5、入结点个数，边数：";cin>>G.vexnum>>G.arcnum;cout<<"请输入点：";for(i=0;i>G.vertices[i].data;G.vertices[i].link=NULL;}cout<<"输入边（V1，V2）：";cout<>v1>>v2;i=LocateVex(G,v1);j=LocateVex(G,v2);edgenode*p=newedgenode;p->a

6、djvex=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;}//头与否，是的话返回nextintNe

7、xtAdjVex(ALGraphG,intv,intw){edgenode*p=G.vertices[v].link;while(p){if(p->adjvex==w)break;p=p->next;}if(p->adjvex!=w

8、

9、!p->next)return-1;returnp->next->adjvex;}//下一个结点boolvisited[10];//数组，保存是否访问过voidDFS(ALGraphG,intv){visited[v]=true;cout<

10、.data<<"";for(intw=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);}//深度voidDFSS(ALGraphG){for(inti=0;i