中国研究生入学考试(简称:考研),是高级大学(大学高级阶段)的入学考试,其英文表述是“Take part in the entrance exams for postgraduate schools”。中国研究生入学考试是在中国进入研究生学习必须进行的考试,类似于进入大学阶段的高考;参加研究生考试的人员必须符合教育部《研究生入学考试招生简章》的相关规定,其中最重要的标准是对学历的要求,其次按照程序:与学校联系、先期准备、报名、初试、调剂、复试、复试调剂、录取、毕业生就业、其他等方面依次进行。2016年全国硕士研究生招生考试初试时间为:2015年12月26日至12月27日(每天上午8:30-11:30,下午14:00-17:00)。
Status ToplogicalSort(ALGraph G)
{
FindIndegree(G,indegree);//求各点的入度放在Indegree[vnum];
InitStack(S);
for(i=0;i
if(Indegree[i]= =0)
push(S,i);
count=0;
while(!StackEmpty(S))
{ Pop(S,i); printf(i,G.vex[i].data); ++count;
for(p=G..vex[i].firstarc; p; p=p->nextarc)
{ k=p->adjvex;
Indegree[k]--;
if( Indegree[k]= =0) push(S,k);
}//for
}//while
if(count
return ERROR;
else
return OK
}
算法分析:求各顶点的入度的时间复杂度为O(e),入度为零的点入栈O(n),在循环中,每个顶点进一次栈,出栈一次,入度减1操作在while共执行了e次,所以总的时间复杂度为O(n+e).
当图中无环时,也可以利用深度优先遍历进行拓扑排序,因为图中无环,所以最先退出DFS函数的顶点即出度为零的点,是拓扑排序中最后一个顶点。由此,按DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。
Dijkstra算法
首先引进一个辅助向量, Dist[i]表示当前找到的从源点到vi的最短路径长度。
final[v]为true,即已经求得从v0到v的最短路径。p[v][w]为true,则w是从v0到v当前求得最短路径上的顶点。该算法弧上的权出现__负数__情况时,不能正确产生最短路径
void ShortestPath_DIJ( MGraph G, int v0, PathMatrix&p,ShortPathTable& Dist )
{ // 用 Dijkstra 算法求有向网G从源点 u 到其余顶点的最短路径
for (v=0; v
{
final[v] = FALSE; dist[v] = G.arcs[v0][v];
for(w=0;w