干货数据结构作业图 [复制链接]

要求

1，创建有向图

2，输出拓扑排序

3，输出深度遍历次序

4，输出广度遍历次序

#includebits/stdc++.husingnamespacestd;constintmaxn=1e5+10;intin[maxn];intf[maxn];//队列typedefstructqnode{intx;structqnode*nex;}qnode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;//邻接表typedefstructNode{intx;Node*nex;}*ve;/************入队********/voidPush(linkqueueq,intx){qnode*p;p=newqnode;p-x=x;p-nex=NULL;q.rear-nex=p;q.rear=p;}/*******************得到对顶元素****************/intTop(linkqueueq){returnq.front-nex-x;}/***************出队************************/voidPop(linkqueueq){qnode*p;p=q.front-nex;q.front-nex=p-nex;if(q.rear==p)q.rear=q.front;deletep;}/*****************判空*******************/intEmpty(linkqueuel){if(l.front==l.rear)return1;elsereturn0;}/*********************将元素防放入邻接表之中*******/voidPush(Nodel,intx){Node*p;p=newNode;p-nex=l.nex;p-x=x;l.nex=p;}/**************************深度优先搜索******************************/voidDFS(ve*vec,intx){Node*now;now=newNode;now=vec[x]-nex;if(f[x])return;f[x]=1;while(now!=NULL)//遍历这个节点指向的节点{inty=now-x;now=now-nex;if(f[y]==0){//如果没有标记过输出printf("%d-%d\n",x,y);DFS(vec,y);}}}/*******************************************广度优先搜索************************************************/voidBFS(ve*vec,intx){//初始化队列linkqueue*qu;qu=newlinkqueue;qu-front=qu-rear=newqnode;qu-front-nex=NULL;Push(*qu,x);while(Empty(*qu)==0){intx=Top(*qu);Pop(*qu);f[x]=1;Node*now;now=newNode;now=vec[x]-nex;while(now!=NULL)//遍历这个节点指向的节点{inty=now-x;now=now-nex;if(f[y])continue;printf("%d-%d\n",x,y);Push(*qu,y);}}deletequ;}/********************************拓扑排序************************************/voidtuo_pu(ve*vec,intn,intm){//初始化队列linkqueue*qu;qu=newlinkqueue;qu-front=qu-rear=newqnode;qu-front-nex=NULL;for(inti=1;i=n;i++)if(in==0)Push(*qu,i);//把入度为零的节点放进队列去intsum=0;/*******************************开始遍历拓扑序列************************************/while(Empty(*qu)==0){intx=Top(*qu);coutx"";Pop(*qu);sum++;Node*now;now=newNode;now=vec[x]-nex;while(now!=NULL)//遍历这个节点指向的节点{inty=now-x;in[y]--;//将他指向的节点的入度减1if(in[y]==0)//如果为零就放进队列去{Push(*qu,y);}now=now-nex;}}if(sum!=n)puts("剩下的节点有环的出现，请你自习检查！");//如果sum不等于n那么说明有环的存在elseputs("");deletequ;}voidchang_jian(ve*vec,intn,intm){intx,y;puts("请输入该图一共有n个顶点，m条边，n和m的值：");scanf("%d%d",n,m);for(inti=1;i=n;i++){//初始化邻接表in=0;vec=newNode;vec-nex=NULL;}puts("请输入m条边，注意顶点值不能大于n");while(m--)//存边{while(1){scanf("%d%d",x,y);if(x0x=ny0y=n)break;elseputs("输入数据不合法，超出了范围请重新输入");}Push(*(vec[x]),y);in[y]++;//入度加一}}voidzhu_cai_dan(){puts("\n返回主菜单请输输入1");puts("创建有向图请输入2");puts("进行拓扑排序请输入3");puts("进行深度优先搜索请输入4");puts("进行广度优先搜索请输入5");puts("退出程序请输入6");}intmain(){intn,m;intx,y;vevec[];//创建邻接表intflag=1;intF=0;zhu_cai_dan();while(1){scanf("%d",x);switch(x){case1:zhu_cai_dan();break;case2:if(flag==0){puts("你已经创建过有向图了，请进行其他操作");break;}chang_jian(vec,n,m);puts("创建成功");flag=0;break;case3:if(flag){puts("你还为创建有向图请先创建再进行操作谢谢");break;}tuo_pu(vec,n,m);//拓扑函数break;case4:if(flag){puts("你还为创建有向图请先创建再进行操作谢谢");break;}printf("请输入开始深度遍历的第一个节点是多少节点大小在1~%d之间\n",n);while(1){scanf("%d",x);if(x0x=n)break;elseputs("输入数据不合法，超出了范围请重新输入");}for(inti=1;i=n;i++)f=0;DFS(vec,x);break;case5:if(flag){puts("你还为创建有向图请先创建再进行操作谢谢");break;}printf("请输入开始深度遍历的第一个节点是多少节点大小在1~%d之间\n",n);while(1){scanf("%d",x);if(x0x=n)break;elseputs("输入数据不合法，超出了范围请重新输入");}for(inti=1;i=n;i++)f=0;BFS(vec,x);break;case6:F=1;puts("感谢老师指导，谢谢使用");break;defalut:puts("数据不合法请重新输入");}if(F)break;}return0;}

更多有趣的内容

请长按

?

长按