騰訊校園招聘筆試試題大全(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)
上一篇：騰訊校園招聘產品類筆試論述題
下一篇：騰訊技術類校園招聘筆試試題及答案
