图的遍历C程序.doc

#include#include#define Max 10#define FALSE 0#define TRUE 1#define Error printf#define QueueSize 30typedef struct char vexsMax; int edgesMaxMax; int n,e;MGraph;int visitedMax;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; /队列满int QueueFull(CirQueue *Q) return Q-count=QueueSize; /进队void EnQueue(CirQueue *Q,int x) if(QueueFull(Q) Error(Queue overflow); else Q-count+; Q-dataQ-rear=x; Q-rear=(Q-rear+1)%QueueSize; /出队int DeQueue(CirQueue *Q) int temp; if(QueueEmpty(Q) Error(Queue underflow); else temp=Q-dataQ-front; Q-count-; Q-front=(Q-front+1)%QueueSize; return temp; /建立图矩阵void CreateMGraph(MGraph *G) int i,j,k; char ch1,ch2; printf(ntt请输入顶点数，边数并按回车键（格式：3，4）:); scanf(%d,%d,&(G-n),&(G-e); for(i=0;in;i+) getchar(); printf(ntt请输入第%d个顶点序号并按回车键,i+1); scanf(%c,&(G-vexsi); for(i=0;in;i+) for(j=0;jn;j+) G-edgesij=0; for(k=0;ke;k+) getchar(); printf(ntt请输入第%d条边的顶点序号并按回车键（格式：i，j）:,k+1); scanf(%c,%c,&ch1,&ch2); for(i=0;ch1!=G-vexsi;i+); for(j=0;ch2!=G-vexsj;j+); G-edgesij=1; /深度优先遍历递归 void DFSM(MGraph *G,int i) int j; printf(ntt深度遍历序列：%cn,G-vexsi); visitedi=TRUE; for(j=0;jn;j+) if(G-edgesij=1&!visitedj) DFSM(G,j); /广度优先遍历递归void BFSM(MGraph *G,int k) int i,j; CirQueue Q; InitQueue(&Q); printf(ntt广度优先遍历序列：%cn,G-vexsk); visitedk=TRUE; EnQueue(&Q,k); while(!QueueEmpty(&Q) i=DeQueue(&Q); for(j=0;jn;j+) if(G-edgesij=1 &! visitedj) visitedj=TRUE; EnQueue(&Q,j); /深度优先遍历void DFSTraverseM(MGraph *G) int i; for(i=0;in;i+) visitedi=FALSE; for(i=0;in;i+) if(!visitedi) DFSM(G,i); /广度优先遍历void BFSTraverseM(MGraph *G) int i; for(i=0;in;i+) visitedi=FALSE; for(i=0;in;i+) if(!visitedi) BFSM(G,i); main() MGraph *G,a; char ch1; int i,j,ch2; G=&a; printf(ntt建立一个图矩阵n); CreateMGraph(G); printf(ntt已建立图的矩阵n); for(i=0;in;i+) printf(ntt ); for(j=0;jn;j+) printf(%5d,G-edgesij); getchar(); ch1=y; while(ch1=y|ch1=Y) printf(n); printf(ntt 图子系统 n); printf(ntt*n); printf(ntt* 1-更新矩阵 *n); printf(ntt* 2-深度优先遍历 *n); printf(ntt* 3-广度优先遍历 *n); printf(ntt* 0-退出 *n); printf(ntt*n); printf(ntt请选择菜单号（03）：); scanf(%d,&ch2); getchar(); switch(ch2) case 1: CreateMGraph(G); printf(ntt图建立完毕！n); break; case 2: DFSTraverseM(G); break; case 3: BFSTraverseM(G); break; case 0: ch1=n; brea