实验7：图的基础实验

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

1、实验7：图的基础实验用深层遍历和广度遍历实现图的遍历操作#include"stdafx.h"#include#include#defineMAX_SIZE100boolVisited[MAX_SIZE];typedefstructarcNode{intadjvex;//该弧所指向的顶点的位置structarcNode*nextarc;//指向下一条弧的指针intinfo;//该弧相关信息的指针}ArcNode;typedefstructvNode{intdata;//顶点信息ArcNode*fi

2、rstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_SIZE];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}AlGraph;typedefstructQNode{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;voidcreateA

3、lGraph(AlGraph&G){printf("请输入图的顶点数：");scanf("%d",&G.vexnum);printf("请输入图的边数：");scanf("%d",&G.arcnum);G.kind=1;inti;intj;intk;for(i=0;i!=G.vexnum;i++){G.vertices[i].data=i+1;}inta[MAX_SIZE][MAX_SIZE];for(i=0;i!=G.arcnum;i++){printf("请输入边的相邻顶点：");scanf("%d%d",&j,&k);if(j

4、==k)continue;else{a[j-1][k-1]=1;a[k-1][j-1]=1;}}intmark;ArcNode*p;ArcNode*q;for(i=0;i!=G.vexnum;i++){mark=0;for(j=0;j!=G.vexnum;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.vertices[i].firstarc=p;

5、mark=1;}else{q=(ArcNode*)malloc(sizeof(ArcNode));q->adjvex=j;q->nextarc=NULL;p->nextarc=q;p=p->nextarc;q=NULL;}}elsecontinue;}}//创建空队列voidInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(1);Q.front->next=NULL;}voidEnQueue(LinkQueue

6、&Q,inte){//将元素e插入到队尾QueuePtro;o=(QueuePtr)malloc(sizeof(QNode));if(!o)exit(1);o->data=e;o->next=NULL;Q.rear->next=o;Q.rear=o;o=NULL;}voidDeQueue(LinkQueue&Q,int&e){//若队列不空，则删除队列的队头元素，并返回队头元素QueuePtro;o=(QueuePtr)malloc(sizeof(QNode));if(Q.front==Q.rear)printf("ERROR");

7、o=Q.front->next;e=o->data;Q.front->next=o->next;if(Q.rear==o)Q.rear=Q.front;free(o);}intQueueEmpty(LinkQueueQ){if(Q.front==Q.rear)return1;elsereturn0;}intfirstAdjvex(AlGraphG,intv){if(G.vertices[v].firstarc!=NULL)returnG.vertices[v].firstarc->adjvex;elsereturn-1;}intne

8、xtAdjvex(AlGraphG,intv,intw){ArcNode*r;r=(ArcNode*)malloc(sizeof(ArcNode));r=G.vertices[v].firstarc;while(r->nextarc!