中國(guó)研究生入學(xué)考試(簡(jiǎn)稱(chēng)：考研)，是高級(jí)大學(xué)(大學(xué)高級(jí)階段)的入學(xué)考試，其英文表述是“Take part in the entrance exams for postgraduate schools”。中國(guó)研究生入學(xué)考試是在中國(guó)進(jìn)入研究生學(xué)習(xí)必須進(jìn)行的考試，類(lèi)似于進(jìn)入大學(xué)階段的高考;參加研究生考試的人員必須符合教育部《研究生入學(xué)考試招生簡(jiǎn)章》的相關(guān)規(guī)定，其中最重要的標(biāo)準(zhǔn)是對(duì)學(xué)歷的要求，其次按照程序：與學(xué)校聯(lián)系、先期準(zhǔn)備、報(bào)名、初試、調(diào)劑、復(fù)試、復(fù)試調(diào)劑、錄取、畢業(yè)生就業(yè)、其他等方面依次進(jìn)行。2016年全國(guó)碩士研究生招生考試初試時(shí)間為：2015年12月26日至12月27日(每天上午8:30-11:30，下午14:00-17:00)。
Status ToplogicalSort(ALGraph G)
{
FindIndegree(G,indegree);//求各點(diǎn)的入度放在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
}
算法分析：求各頂點(diǎn)的入度的時(shí)間復(fù)雜度為O(e)，入度為零的點(diǎn)入棧O(n)，在循環(huán)中，每個(gè)頂點(diǎn)進(jìn)一次棧，出棧一次，入度減1操作在while共執(zhí)行了e次，所以總的時(shí)間復(fù)雜度為O(n+e).
當(dāng)圖中無(wú)環(huán)時(shí)，也可以利用深度優(yōu)先遍歷進(jìn)行拓?fù)渑判颍驗(yàn)閳D中無(wú)環(huán)，所以最先退出DFS函數(shù)的頂點(diǎn)即出度為零的點(diǎn)，是拓?fù)渑判蛑凶詈笠粋�(gè)頂點(diǎn)。由此，按DFS函數(shù)的先后記錄下來(lái)的頂點(diǎn)序列即為逆向的拓?fù)溆行蛐蛄小?/p>
Dijkstra算法
首先引進(jìn)一個(gè)輔助向量, Dist[i]表示當(dāng)前找到的從源點(diǎn)到vi的最短路徑長(zhǎng)度。
final[v]為true，即已經(jīng)求得從v0到v的最短路徑。p[v][w]為true，則w是從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)。該算法弧上的權(quán)出現(xiàn)__負(fù)數(shù)__情況時(shí)，不能正確產(chǎn)生最短路徑
void ShortestPath_DIJ( MGraph G, int v0, PathMatrix&p,ShortPathTable& Dist )
{ // 用 Dijkstra 算法求有向網(wǎng)G從源點(diǎn) u 到其余頂點(diǎn)的最短路徑
for (v=0; v
{
final[v] = FALSE; dist[v] = G.arcs[v0][v];
for(w=0;w