《采用邻接表实现图的dfs和bfs》由会员分享，可在线阅读，更多相关《采用邻接表实现图的dfs和bfs（8页珍藏版）》请在金锄头文库上搜索。
1、#includestdio.h#includestdlib.h#define MVNum 30#define QueueSize 30 #define VexType inttypedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VexNodeVexType data;ArcNode *firstarc;VexNode,AdjListMVNum;typedef structint vexnum,arcnum;AdjList vertices;ALGraph;int LocateVex(ALG
2、raph *G, VexType v)int i;for(i=0;ivexnum;i+)if(G-verticesi.data=v)return i;return -1;void CreateGraph(ALGraph *G)int i,j,k;int v1,v2;ArcNode *p=NULL,*q=NULL;printf(请输入顶点数和边数( 输入格式为:顶点数 边数)：n);scanf(%d%d,printf(请输入顶点信息( 顶点以 1 为起始，每个顶点以回车作为结束):n);for(i=1;ivexnum;i+)scanf(%d,G-verticesi.firstarc=NULL;p
3、rintf(请输入边的信息( 输入格式为:i,j) ：n);for(k=1;karcnum;k+)scanf(%d,%d,i=LocateVex(G,v1);j=LocateVex(G,v2);p=(ArcNode*)malloc(sizeof(ArcNode);if(!p) exit(1);p-adjvex=j;p-nextarc=G-verticesi.firstarc;G-verticesi.firstarc=p;q=(ArcNode*)malloc(sizeof(ArcNode);if(!q) exit(1);q-adjvex=i;q-nextarc=G-verticesj.first
4、arc;G-verticesj.firstarc=q;void PrintGraph(ALGraph *G)int i;ArcNode *p=NULL;for(i=1;ivexnum;i+)printf(%d,G-verticesi.data);p=(ArcNode*)malloc(sizeof(ArcNode);if(!p) exit(1);p=G-verticesi.firstarc;while(p)printf(%d,p-adjvex);p=p-nextarc;printf(n);typedef enumFALSE,TRUE Boolean;Boolean visitedMVNum;/深
5、度优先搜索void DFS(ALGraph *G,int i) ArcNode *p; printf(nvisit data:%dn,G-verticesi.data); / 访问顶点 vi visitedi=TRUE; /标记 vi 已访问 p=G-verticesi.firstarc; /取 vi 边表的头指针 while(p) /依次搜索 vi 的邻接点 vj，这里 j=p-adjvex if (!visitedp-adjvex) /若 vi 尚未被访问 DFS(G,p-adjvex); /则以 Vj 为出发点向纵深搜索 p=p-nextarc; /找 vi 的下一邻接点 void DF
6、SM(ALGraph *G) int i; for(i=1;ivexnum ;i+) visitedi=FALSE; for(i=1;ivexnum ;i+) if(!visitedi) DFS(G,i); /广度优先遍历 typedef struct int front; int rear; int count; int dataQueueSize; CirQueue; void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0; int QueueEmpty(CirQueue *Q) return Q-count=QueueSize; i
7、nt QueueFull(CirQueue *Q) return Q-count=QueueSize; void EnQueue(CirQueue *Q,int x) if (QueueFull(Q) printf(Queue overflow); else Q-count+; Q-dataQ-rear=x; Q-rear=(Q-rear+1)%QueueSize; int DeQueue(CirQueue *Q) int temp; if(QueueEmpty(Q) printf(Queue underflow); return NULL; else temp=Q-dataQ-front;
8、Q-count-; Q-front=(Q-front+1)%QueueSize; return temp; void BFS(ALGraph*G,int k) int i; CirQueue Q; /须将队列定义中 DataType 改为 int ArcNode *p; InitQueue( /队列初始化 printf(n visit data:%dn,G-verticesk.data); /访问源点 vk visitedk=TRUE; EnQueue( /vk 已访问，将其人队。（实际上是将其序号人队） while(!QueueEmpty(&Q) /队非空则执行 i=DeQueue( /相当
9、于 vi 出队 p=G-verticesi.firstarc; /取 vi 的边表头指针 while(p) /依次搜索 vi 的邻接点 vj(令 p-adjvex=j) if(!visitedp-adjvex) /若 vj 未访问过 printf(nvisit data:%dn,G-verticesp-adjvex.data); /访问 vj visitedp-adjvex=TRUE; EnQueue( /访问过的 vj 人队 p=p-nextarc; /找 vi 的下一邻接点 void BFSM(ALGraph *G) int i; for (i=1;ivexnum ;i+) visitedi=FALSE; for (i=1;ivexnum ;i+) if (!visitedi) BFS(G,i); void main() int i,x;ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph);CreateGraph(G);PrintGraph(G);printf(深度优先遍历：); DFSM(G);printf(n); printf(广度优先遍历：); BFSM(G); printf(n);
