《数据结构图的深度和广度优先遍历》由会员分享，可在线阅读，更多相关《数据结构图的深度和广度优先遍历（7页珍藏版）》请在金锄头文库上搜索。
1、标题：图的深度和广度优先遍历时 限： 2000 ms 内存限制： 5000 K 总时限： 3000 ms 描述：以邻接矩阵给出一张以整数编号为顶点的图，其中0表示不相连，1表示相连。按深度和广度优先进行遍历，输出全部结果。要求，遍历时优先较小的顶点。如，若顶点0与顶点2，顶点3，顶点4相连，则优先遍历顶点2.输入：顶点个数邻接矩阵输出：DFS 深度遍历输出WFS 广度遍历输出输入样例：3 0 1 1 1 0 1 1 1 0 输出样例：DFS 0 1 2 1 0 2 2 0 1 WFS 0 1 2 1 0 2 2 0 1 提示：顶点整数从0 开始来源：教材#include “stdlib.h“
2、#include “stdio.h“ #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define MAXQSIZE 100 typedef struct int amount; int *vex; int *matrix; Graph; typedef struct int *base; int *top; int stacksize; SqStack; void InitStack(SqStack S.top = S.base; S.stacksize = STACK_INIT_SIZE; void Push(SqStack S
3、.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; bool Pop(SqStack return false; else e = *-S.top; return true; bool GetTopS(SqStack S,int else e = *-S.top; return true; typedef struct int *base; int front; int rear; SqQueue; void InitQueue(SqQueue Q.front = Q.rear = 0; bool E
4、nQueue(SqQueue return false; else Q.baseQ.rear = e; Q.rear = (Q.rear + 1)%MAXQSIZE; return true; bool DeQueue(SqQueue return false; else e = Q.baseQ.front; Q.front = (Q.front + 1)%MAXQSIZE; return true; bool GetTopQ(SqQueue else e = Q.baseQ.front; return true; void Init(Graph G.vex = NULL; G.matrix
5、= NULL; void Create(Graph G.vex = (int*)calloc(G .amount,sizeof(int); for(int i = 0; i G.amount | index G.amount | index 0) puts(“ERROR!“); exit(0); int i; bool *IsVisited; IsVisited = (bool*)calloc(G .amount,sizeof(bool); for(i = 0; i G .amount; +i) IsVisitedi = false; SqQueue Q; InitQueue(Q); prin
6、tf(“%d “,G .vexindex); IsVisitedindex = true; EnQueue(Q,index); while(Q.front != Q.rear) for(i = 0; i G .amount; +i) if(G.matrixiindex = 1 IsVisitedi = true; EnQueue(Q,i); DeQueue(Q,index); GetTopQ(Q,index); puts(“); int main(void) Graph G; Init(G); Create(G); puts(“DFS“); for(int i = 0; i G .amount; +i) DFS(G,i); puts(“WFS“); for(int i = 0; i G .amount; +i) WFS(G,i); Destory(G); return 0;
