《为图建立邻接表,深度与广度遍历.doc》由会员分享，可在线阅读，更多相关《为图建立邻接表,深度与广度遍历.doc（4页珍藏版）》请在金锄头文库上搜索。
1、为一个图建立一个邻接表、编写深度遍历和广度遍历算法#include #include#define MaxNode 40#define M 20typedef struct ArcNode int adjvex; struct ArcNode *nextarc;ArcNode;typedef struct int vertex; struct ArcNode *firstarc;vernode;typedef vernode adjlistMaxNode;int queueMaxNode;/在遍历过程中是从右边开始void dfs(adjlist g,int k,int visited) /从
2、顶点k出发，深度优先搜索 ArcNode *p; int w; visitedk=1; printf(%d-,gk.vertex); p=gk.firstarc; while(p!=NULL) w=p-adjvex; if(visitedw=0) dfs(g,w,visited); p=p-nextarc; void bfs(adjlist g,int k,int visited) /从顶点k出发，广度优先搜索 int front=0,rear=1,w; ArcNode *p; visitedk=1; /访问初始顶点 printf(%d-,k); queuerear=k; /初始顶点入队列 w
3、hile(front!=rear) /队列不为空 front=(front+1)%M; w=queuefront; /按访问次序依次出队列 p=gw.firstarc; while(p!=NULL) if(visitedp-adjvex=0) visitedp-adjvex=1; printf(%d-,p-adjvex); rear=(rear+1)%M; queuerear=p-adjvex; p=p-nextarc; void trave_bfs(adjlist g,int n) int i,visitedMaxNode; /数组visited标志图中的顶点是否已被访问 for(i=1;i
4、=n;i+) visitedi=0; for(i=1;i=n;i+) if(visitedi=0) bfs(g,i,visited); printf(bb n);void trave_dfs(adjlist g,int n) int i,visitedMaxNode; /数组visited标志图中的顶点是否已被访问 for(i=1;i=n;i+) visitedi=0; for(i=1;i=n;i+) if(visitedi=0) dfs(g,i,visited); printf(bb n);void print(adjlist g,int n) ArcNode *q; int i; prin
5、tf(输出无向图的邻接链表示：n); for(i=1;i,gi.vertex); q=gi.firstarc; while(q!=NULL) printf(%d-,q-adjvex); q=q-nextarc; printf(bb n); void main() ArcNode *p,*q; adjlist g; int i,j,n,k,e; printf(输入图中顶点的个数,边数:); scanf(%d%d,&n,&e); for(k=1;k=n;k+) getchar(); printf(t第%d个顶点信息:,k); scanf(%d,&gk.vertex); gk.firstarc=NULL; /对顺序存储部分初始化 for(k=1;kadjvex=j; q-nextarc=gi.firstarc; gi.firstarc=q; p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=i; p-nextarc=gj.firstarc; gj.firstarc=p; print(g,n); printf(n); printf(图的深度优先搜索:); trave_dfs(g,n); printf(n); printf(图的广度优先搜索:); trave_bfs(g,n); printf(n);
