为图建立邻接表,深度与广度遍历

《为图建立邻接表,深度与广度遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、为一个图建立一个邻接表、编写深度遍历和广度遍历算法#include#include#defineMaxNode40#defineM20typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstruct{intvertex;structArcNode*firstarc;}vernode;typedefvernodeadjlist[MaxNode];intqueue[MaxNode];//在遍历过程中是从右边开始voiddfs

2、(adjlistg,intk,intvisited[])//从顶点k出发，深度优先搜索{ArcNode*p;intw;visited[k]=1;printf("%d->",g[k].vertex);p=g[k].firstarc;while(p!=NULL){w=p->adjvex;if(visited[w]==0)dfs(g,w,visited);p=p->nextarc;}}voidbfs(adjlistg,intk,intvisited[])//从顶点k出发，广度优先搜索{intfront=0,rear=1,w;ArcNode*p;vi

3、sited[k]=1;//访问初始顶点printf("%d->",k);queue[rear]=k;//初始顶点入队列while(front!=rear)//队列不为空{front=(front+1)%M;w=queue[front];//按访问次序依次出队列p=g[w].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){visited[p->adjvex]=1;printf("%d->",p->adjvex);rear=(rear+1)%M;queue[rear]=p->adjvex;;}p

4、=p->nextarc;}}}voidtrave_bfs(adjlistg,intn){inti,visited[MaxNode];//数组visited标志图中的顶点是否已被访问for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)bfs(g,i,visited);printf("bb");}voidtrave_dfs(adjlistg,intn){inti,visited[MaxNode];//数组visited标志图中的顶点是否已被访问for(i=1;i<

5、=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)dfs(g,i,visited);printf("bb");}voidprint(adjlistg,intn){ArcNode*q;inti;printf("输出无向图的邻接链表示：");for(i=1;i<=n;i++){printf("t%dt",i);printf("%d->",g[i].vertex);q=g[i].firstarc;while(q!=NULL){printf("%d->",q->adjvex);

6、q=q->nextarc;}printf("bb");}}voidmain(){ArcNode*p,*q;adjlistg;inti,j,n,k,e;printf("输入图中顶点的个数,边数:");scanf("%d%d",&n,&e);for(k=1;k<=n;k++){getchar();printf("t第%d个顶点信息:",k);scanf("%d",&g[k].vertex);g[k].firstarc=NULL;//对顺序存储部分初始化}for(k=1;k<=e;k++){printf("第%d条边的起点,终点:",k)

7、;scanf("%d%d",&i,&j);q=(ArcNode*)malloc(sizeof(ArcNode));q->adjvex=j;q->nextarc=g[i].firstarc;g[i].firstarc=q;p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;}print(g,n);printf("");printf("图的深度优先搜索:");trave_dfs(g,n);printf("");pr

8、intf("图的广度优先搜索:");trave_bfs(g,n);printf("");