【数据结构】图的存储和遍历实验报告.doc

《数据结构B》实验报告 系 计算机与电子 专业 级 01 __班 姓名学号2010年1 0月 9日 上机题目： 图的存储和遍历 详细设计 #includestdio.h #define GRAPHMAX 10 #define FALSE 0 #define TRUE 1 #define error printf #define QueueSize 30 typedef struct { char vexs[GRAPHMAX]; int edges[GRAPHMAX][GRAPHMAX]; int n,e; }MGraph; int visited[10]; typedef struct { int front,rear,count; int data[QueueSize]; }CirQueue; void InitQueue(CirQueue *Q) { Q-front=Q-rear=0; Q-count=0; } int QueueEmpty(CirQueue *Q) { return Q-count=QueueSize; } int QueueFull(CirQueue *Q) { return Q-count==QueueSize; } void EnQueue(CirQueue *Q,int x) { if(QueueFull(Q)) error(Queue overflow); else { Q-count++; Q-data[Q-rear]=x; Q-rear=(Q-rear+1)%QueueSize; } } int DeQueue(CirQueue *Q) { int temp; if(QueueEmpty(Q)) { error(Queue underflow); return NULL; } else { temp=Q-data[Q-front]; Q-count--; Q-front=(Q-front+1)%QueueSize; return temp; } } void CreateMGraph(MGraph *G) { int i,j,k; char ch1,ch2; printf(\n\t\t请输入定点数，边数并按回车（格式如：3，4）：); scanf(%d,%d,(G-n),(G-e)); for(i=0;iG-n;i++) { getchar(); printf(\n\t\t请输入第%d个定点数并按回车：,i+1); scanf(%c,(G-vexs[i])); } for(i=0;iG-n;i++) for(j=0;jG-n;j++) G-edges[i][j]=0; for(k=0;kG-e;k++) { getchar(); printf(\n\t\t请输入第%d条边的顶点序号（格式如：i,j）：,k+1); scanf(%c,%c,ch1,ch2); for(i=0;ch1!=G-vexs[i];i++); for(j=0;ch2!=G-vexs[j];j++); G-edges[i][j]=1; } } void DFSM(MGraph *G,int i) { int j; printf(\n\t\t深度优先遍历序列： %c\n,G-vexs[i]); visited[i]=TRUE; for(j=0;jG-n;j++) if(G-edges[i][j]==1 visited[j]!=1) //////////////// DFSM(G,j); } void BFSM(MGraph *G,int k) { int i,j; CirQueue Q; InitQueue(Q); printf(\n\t\t广度优先遍历序列：%c\n,G-vexs[k]); visited[k]=TRUE; EnQueue(Q,k); while(!QueueEmpty(Q)) { i=DeQueue(Q); for(j=0;jG-n;j++) if(G-edges[i][j]==1 visited[j]!=1) { visited[j]=TRUE; EnQueue(Q,j); } } } void DFSTraverseM(MGraph *G) { int i; for(i=0;iG-n;i++) visited[i]=FALSE; for(i=0;iG-n;i++) if(!visited[i]) DFSM(G,i); } void BFSTraverseM(MGr