騰訊校園招聘筆試試題大全(4)
3、拓?fù)渑判?/p>
解：1、在一個(gè)表示工程的有向圖中，用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)，稱為AOV網(wǎng)。
2、設(shè)G = (V,E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，V中的頂點(diǎn)序列v1，v2，.......，vn，滿足若從頂點(diǎn)vi到vj有一條路徑，則在頂點(diǎn)序列中vi必在頂點(diǎn)vj之前，則我們稱這樣的頂點(diǎn)序列為一個(gè)拓?fù)湫蛄小?/p>
3、所謂拓?fù)渑判?，其?shí)就是對(duì)一個(gè)有向圖構(gòu)造拓?fù)湫蛄械倪^程。構(gòu)造時(shí)會(huì)有兩個(gè)結(jié)果，如果此網(wǎng)的全部頂點(diǎn)都輸出，則說明它是不存在環(huán)(回路)的AOV網(wǎng);如果輸出頂點(diǎn)數(shù)少了，哪怕是少了一個(gè)，也說明這個(gè)網(wǎng)存在環(huán)(回路)，不是AOV網(wǎng)。
4、對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判虻幕舅悸肥牵簭腁OV網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)輸出，然后刪除此頂點(diǎn)，并刪除以此頂點(diǎn)為尾的弧，繼續(xù)重復(fù)此步驟，直到輸出全部頂點(diǎn)或AOV網(wǎng)中不存在入度為0的頂點(diǎn)為止。
拓?fù)渑判蛟O(shè)計(jì)的結(jié)構(gòu)代碼如下所示。
在算法中，我還需要輔助的數(shù)據(jù)結(jié)構(gòu)一棧，用來存儲(chǔ)處理過程中入度為0的頂點(diǎn)，目的是為了避免每個(gè)查找時(shí)都要去遍歷頂點(diǎn)表找有沒有入度為0的頂點(diǎn)。
現(xiàn)在看代碼，并且進(jìn)行模擬它。
//拓?fù)渑判?，若GL無回路，則輸出拓?fù)渑判蛐蛄胁⒎祷豋K，若有回路，返回ERROR statusTopologicalSort(GraphAdjListGL) { EdgeNode*e; inti,k,gettop; inttop=0;//用于棧指針下標(biāo) intcount=0;//用于統(tǒng)計(jì)輸出頂點(diǎn)的個(gè)數(shù) int*stack;//建棧存儲(chǔ)入度為0的頂點(diǎn) stack=(int*)malloc(GL->numVertexes*sizeof(int)); for(i=0;i<GL->numVertexes;i++) { if(GL->adjList[i].in==0) { stack[++top]=i;//將入度為0的頂點(diǎn)入棧 } } while(top!=0) { gettop=stack[top--];//出棧 printf("%d->",GL->adjList[gettop].data);//打印此結(jié)點(diǎn) count++; for(e=GL->adjList[gettop].firstedge;e;e=e->next) { //對(duì)此頂點(diǎn)弧表遍歷 k=e->adjvex; if(!(--GL->adjList[k].in)) { //將k號(hào)頂點(diǎn)鄰接點(diǎn)的入度減1 stack[++top]=k;//若為0，則入棧，以便于下次循環(huán)輸出 } } } if(count<GL->numVertexes)//如果count小于頂點(diǎn)數(shù)，說明存在環(huán) { returnERROR; } else { returnOK; } } |
騰訊校園招聘筆試試題大全(4)
