騰訊校園招聘筆試試題大全(4)
3、拓撲排序
解：1、在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優(yōu)先關(guān)系，這樣的有向圖為頂點表示活動的網(wǎng)，稱為AOV網(wǎng)。
2、設(shè)G = (V,E)是一個具有n個頂點的有向圖，V中的頂點序列v1，v2，.......，vn，滿足若從頂點vi到vj有一條路徑，則在頂點序列中vi必在頂點vj之前，則我們稱這樣的頂點序列為一個拓撲序列。
3、所謂拓撲排序，其實就是對一個有向圖構(gòu)造拓撲序列的過程。構(gòu)造時會有兩個結(jié)果，如果此網(wǎng)的全部頂點都輸出，則說明它是不存在環(huán)(回路)的AOV網(wǎng);如果輸出頂點數(shù)少了，哪怕是少了一個，也說明這個網(wǎng)存在環(huán)(回路)，不是AOV網(wǎng)。
4、對AOV網(wǎng)進行拓撲排序的基本思路是：從AOV網(wǎng)中選擇一個入度為0的頂點輸出，然后刪除此頂點，并刪除以此頂點為尾的弧，繼續(xù)重復(fù)此步驟，直到輸出全部頂點或AOV網(wǎng)中不存在入度為0的頂點為止。
拓撲排序設(shè)計的結(jié)構(gòu)代碼如下所示。
在算法中，我還需要輔助的數(shù)據(jù)結(jié)構(gòu)一棧，用來存儲處理過程中入度為0的頂點，目的是為了避免每個查找時都要去遍歷頂點表找有沒有入度為0的頂點。
現(xiàn)在看代碼，并且進行模擬它。
//拓撲排序，若GL無回路，則輸出拓撲排序序列并返回OK，若有回路，返回ERROR statusTopologicalSort(GraphAdjListGL) { EdgeNode*e; inti,k,gettop; inttop=0;//用于棧指針下標 intcount=0;//用于統(tǒng)計輸出頂點的個數(shù) 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);//打印此結(jié)點 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，則入棧，以便于下次循環(huán)輸出 } } } if(count<GL->numVertexes)//如果count小于頂點數(shù)，說明存在環(huán) { returnERROR; } else { returnOK; } } |
騰訊校園招聘筆試試題大全(4)
