腾讯校园招聘笔试试题大全(4)
3、拓扑排序
学习啦在线学习网 解:1、在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,称为AOV网。
2、设G = (V,E)是一个具有n个顶点的有向图,V中的顶点序列v1,v2,.......,vn,满足若从顶点vi到vj有一条路径,则在顶点序列中vi必在顶点vj之前,则我们称这样的顶点序列为一个拓扑序列。
3、所谓拓扑排序,其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果,如果此网的全部顶点都输出,则说明它是不存在环(回路)的AOV网;如果输出顶点数少了,哪怕是少了一个,也说明这个网存在环(回路),不是AOV网。
4、对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出,然后删除此顶点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或AOV网中不存在入度为0的顶点为止。
拓扑排序设计的结构代码如下所示。
学习啦在线学习网 在算法中,我还需要辅助的数据结构一栈,用来存储处理过程中入度为0的顶点,目的是为了避免每个查找时都要去遍历顶点表找有没有入度为0的顶点。
现在看代码,并且进行模拟它。
学习啦在线学习网 //拓扑排序,若GL无回路,则输出拓扑排序序列并返回OK,若有回路,返回ERROR 学习啦在线学习网 statusTopologicalSort(GraphAdjListGL) { EdgeNode*e; inti,k,gettop; 学习啦在线学习网 inttop=0;//用于栈指针下标 intcount=0;//用于统计输出顶点的个数 int*stack;//建栈存储入度为0的顶点 stack=(int*)malloc(GL->numVertexes*sizeof(int)); for(i=0;i<GL->numVertexes;i++) { if(GL->adjList[i].in==0) { stack[++top]=i;//将入度为0的顶点入栈 } } while(top!=0) { gettop=stack[top--];//出栈 学习啦在线学习网 printf("%d->",GL->adjList[gettop].data);//打印此结点 count++; for(e=GL->adjList[gettop].firstedge;e;e=e->next) { //对此顶点弧表遍历 k=e->adjvex; 学习啦在线学习网 if(!(--GL->adjList[k].in)) { 学习啦在线学习网 //将k号顶点邻接点的入度减1 学习啦在线学习网 stack[++top]=k;//若为0,则入栈,以便于下次循环输出 } } } 学习啦在线学习网 if(count<GL->numVertexes)//如果count小于顶点数,说明存在环 { returnERROR; } else { returnOK; } } |
腾讯校园招聘笔试试题大全(4)
上一篇:腾讯校园招聘产品类笔试论述题
下一篇:腾讯技术类校园招聘笔试试题及答案