《图的深度和广度遍历(采用邻接表存储)》由会员分享，可在线阅读，更多相关《图的深度和广度遍历(采用邻接表存储)（6页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上/图的深度遍历和广度遍历/采用邻接表存储#include#include#define INFINITY 100#define MAX_VERTEX_NUM 20#define OK 1#define ERROR -1typedef char VertexType;typedef char InfoType;typedef VertexType QElemType;bool visitedMAX_VERTEX_NUM;/ 访问标志数组 typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueueP
2、tr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) return ERROR;Q.front-next=NULL;return OK;int DestroyQueue(LinkQueue &Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;/DestroyQueu
3、eint EnQueue(LinkQueue &Q,QElemType e)QueuePtr p; /p=(QueuePtr)malloc(sizeof(QNode);if(!p) return ERROR;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;int DeQueue(LinkQueue &Q,QElemType &e)if(Q.front=Q.rear) return ERROR;QueuePtr p;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.re
4、ar=Q.front;free(p);return OK;int QueueEmpty(LinkQueue Q)if(Q.rear=Q.front) return 1;else return 0;typedef struct ArcNodeint adjvex;struct ArcNode * nextarc;int weight;InfoType *info;ArcNode;typedef struct VNodeVertexType data;ArcNode *firstarc;int vexnum,arcnum; VNode,AdjListMAX_VERTEX_NUM;typedef s
5、tructAdjList vertices;int vexnum,arcnum;ALGraph;int LocateVex(ALGraph G,VertexType v)int i;for(i=0;iG.vexnum;i+)if(G.verticesi.data=v ) return i; return OK;int FirstAdjVex(ALGraph G,VertexType v)/返回顶点所在位置 int i; for(i=0;iadjvex; /返回第一个邻接点所在的位置 break; return ERROR;int NextAdjVex(ALGraph G,VertexType
6、v,VertexType w)/返回顶点所在位置int i,j;i=LocateVex(G,v);j=LocateVex(G,w);int flag=0;ArcNode *p; p=G.verticesi.firstarc; while(p) if(p-adjvex=j) flag=1; break; p=p-nextarc; if(flag & p-nextarc) return p-nextarc-adjvex; else return ERROR;/*构造图，采用邻接表存储*/int CreatUDG(ALGraph &G) /构造无向图int i,j,k;VertexType v1,v
7、2;ArcNode *p,*q; printf(请输入顶点数和弧数：); scanf(%d%d,&G.vexnum,&G.arcnum); printf(请输入顶点（顶点之间不需要加空格）：); getchar();/吃掉多余的回车键， for(i=0;iG.vexnum;i+)scanf(%c,&G.verticesi.data);G.verticesi.firstarc=NULL;/初始化firstarc指针 getchar(); for (k=0; knextarc=G.verticesi.firstarc; q-nextarc=G.verticesj.firstarc; G.verti
8、cesi.firstarc=p; p-adjvex=j; G.verticesj.firstarc=q; q-adjvex=i; / if (IncInfo) scanf(G.arcsij.info); / 输入弧含有相关信息 return 0;/*图的深度遍历*/ void DFS(ALGraph G, int i) / 从第i个顶点出发递归地深度优先遍历图G。 int j; visitedi = true; printf(%c ,G.verticesi.data);/ 访问第i个顶点 for (j=FirstAdjVex(G,G.verticesi.data); j!=ERROR; j=N
9、extAdjVex(G,G.verticesi.data,G.verticesj.data)/ if (!visitedj) DFS(G,j); / 对尚未访问的邻接顶点递归调用DFS void DFSTraverse(ALGraph G) / 对图G作深度优先遍历。 int i; for (i=0; iG.vexnum; +i) visitedi = false; / 访问标志数组初始化 for (i=0; iG.vexnum; +i) if (!visitedi) DFS(G,i); / 对尚未访问的顶点调用DFS /*图的广度遍历*/void BFSTraverse(ALGraph G)
10、 / 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。 int i,j; VertexType u ; LinkQueue Q; InitQueue(Q); / 置空的辅助队列Q for (i=0; iG.vexnum; +i) visitedi = false; for (i=0; iG.vexnum; +i) if (!visitedi) / i尚未访问 visitedi = true; printf(%c ,G.verticesi.data);/ 访问第i个顶点 / 访问 EnQueue(Q,G.verticesi.data); /顶点入队列 while (!QueueEmpty(Q) DeQueue(Q,u); / 队头元素出队并置为u for (j=FirstAdjVex(G, u); j!=ERROR; j=NextAdjVex(G, u,G.verticesj.data) if (!visitedj) / u的尚未访问的邻接顶点j入队列Q visitedj = true; printf(%c ,G.verticesj.data);/ 访问第j个顶点 EnQueue(Q, G.verticesj.data); /if /while /if / BFSTraverseint main() ALGraph G;CreatUDG(
