【数据结构】图的存储和遍历
发布时间:2020-12-15 06:33:17 所属栏目:安全 来源:网络整理
导读:////2012.03.26 by zhengshihao#includestdio.h#define GRAPHMAX 10#define FALSE 0#define TRUE 1#define Error printf#define QueueSize 30typedef struct{char vexs[GRAPHMAX];int edges[GRAPHMAX][GRAPHMAX];int n,e;}Mgraph;int visited[10];typedef st
////2012.03.26 by zhengshihao #include<stdio.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==0; } 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("ntt请输入定点数,边数并按回车(格式如:3,4):"); scanf("%d,%d",&(g->n),&(g->e)); for(i=0;i<g->n;i++) { getchar(); printf("ntt请输入第%d个定点并回车:",i+1); scanf("%c",&(g->vexs[i])); } for(i=0;i<g->n;i++) for(j=0;j<g->n;j++) g->edges[i][j]=0; for(k=0;k<g->e;k++) { getchar(); printf("ntt请输入第%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("ntt深度优先遍历序列:%cn",g->vexs[i]); visited[i]=TRUE; for(j=0;j<g->n;j++) if(g->edges[i][j]==1&&!visited[j])DFSM(g,j); } void BFSM(Mgraph *g,int k) { int i,j; CirQueue q; InitQueue(&q); printf("ntt广度优先遍历序列:%cn",g->vexs[k]); visited[k]=TRUE; EnQueue(&q,k); while(!QueueEmpty(&q)) { i=DeQueue(&q); for(j=0;j<g->n;j++) if(g->edges[i][j]==1&&!visited[j]) { visited[j]=TRUE; printf("ntt广度优先遍历序列:%cn",g->vexs[j]); EnQueue(&q,j); } } } void DFSTraverseM(Mgraph* g) //深度优先遍历 { int i; for(i=0;i<g->n;i++) visited[i]=FALSE; for(i=0;i<g->n;i++) if(!visited[i])DFSM(g,i); } void BFSTraverseM(Mgraph* g) //广度优先遍历 { int i; for(i=0;i<g->n;i++) visited[i]=FALSE; for(i=0;i<g->n;i++) if(!visited[i])BFSM(g,i); } int main() { Mgraph *g,a; char ch1; int i,ch2; g=&a; printf("ntt建立一个有向图的邻接矩阵表示n"); CreateMGraph(g); printf("已建立一个有向图的邻接矩阵存储n"); for(i=0;i<g->n;i++) { printf("ntt"); for(j=0;j<g->n;j++) printf("%5d",g->edges[i][j]); } getchar(); ch1='y'; while(ch1=='y'||ch1=='Y') { printf("n"); printf("ntt 图的存储和遍历 "); printf("ntt*****************************"); printf("ntt 1----更新邻接矩阵 "); printf("ntt 2----深度优先遍历 "); printf("ntt 3----广度优先遍历 "); printf("ntt 0----退 出 "); printf("ntt*****************************"); printf("ntt 请选择菜单号(0--3):"); 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';break; default:printf("ntt输出错误!请重新输入!"); } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |