编写程序实现图的各种基本运算.doc

《编写程序实现图的各种基本运算.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、仲恺农业工程学院实验报告纸计算机科学与工程学院（院、系）专业班组课学号姓名实验日期教师评定《数据结构》实验报告一、上机实验的问题和要求（需求分析）：[题目]编写程序实现图的各种基本预算，并在此基础上设计主函数，使其完成如下功能：（1）建立无向图。（2）输出无向图对应的邻接矩阵(3)实现深度遍历和广度遍历。二、源程序及注释以及运行结果[源程序]程序名：//text8-2.c#include#include#defineMAXV100inta[MAXV][MAXV];intVisited[MAXV];t

2、ypedefcharInfoType;typedefcharVertex;typedefstructArcNode//弧的结点的数据结构{intadjvex;//该弧所指向的顶点的位置，即终点位置structArcNode*nextarc;//指向下一条弧的指针InfoTypeinfo;//该弧的相关信息}ArcNode;typedefstructVNode{Vertexdata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAXV];typedefstruct{AdjL

3、istadjlist;intn,e;//图中的顶点数n和边数e}ALGraph;//图的类型voidcreateALGraph(ALGraph&G)//创建图{inti;intj;intk;for(i=0;i!=G.n;i++){G.adjlist[i].data=i+1;}printf("请输入某边的相邻顶点(vi-vj)的下标(如:12):");for(i=0;i!=G.e;i++){scanf("%d%d",&j,&k);a[j-1][k-1]=1;a[k-1][j-1]=1;}intmark;ArcNode*p;ArcNod

4、e*q;for(i=0;i!=G.n;i++){mark=0;for(j=0;j!=G.n;j++)if(j==i)continue;elseif(a[i][j]==1){if(mark==0){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=NULL;G.adjlist[i].firstarc=p;mark=1;}else{q=(ArcNode*)malloc(sizeof(ArcNode));q->adjvex=j;q->nextarc=NULL;p->nexta

5、rc=q;p=p->nextarc;q=NULL;}}elsecontinue;}}//createAlGraphintfirstAdjvex(ALGraphG,intv){if(G.adjlist[v].firstarc!=NULL)returnG.adjlist[v].firstarc->adjvex;elsereturn-1;}intnextAdjvex(ALGraphG,intv,intw){ArcNode*r;r=(ArcNode*)malloc(sizeof(ArcNode));r=G.adjlist[v].firstarc

6、;while(r->nextarc!=NULL){if(r->adjvex==w)returnr->nextarc->adjvex;elser=r->nextarc;}r=NULL;return-1;}voidDFS(ALGraphG,intv)//深度优先遍历{intw;Visited[v]=true;printf("%d",G.adjlist[v].data);for(w=firstAdjvex(G,v);w>=0;){if(!Visited[w])DFS(G,w);w=nextAdjvex(G,v,w);}}//深度优先遍历voi

7、dDSTaverse(ALGraphG,intv){inti;for(i=0;i!=G.n;i++)Visited[i]=false;printf("从第一个位置深度优先遍历结果为:");if(!Visited[v])DFS(G,v);for(v=0;v!=G.n;v++)if(!Visited[v])DFS(G,v);}//广度优先遍历voidBFS(ALGraph*G,intv){ArcNode*p;intqueue[MAXV],front=0,rear=0;intvisited[MAXV];intw,i;for(i=0;i

8、->n;i++)visited[i]=0;printf("%d",v);visited[v]=1;rear=(rear+1)%MAXV;queue[rear]=v;while(front!=rear){fr