關(guān)鍵路徑算法ppt課件(編輯修改稿)
2025-06-02 06:28 本頁面
【文章內(nèi)容簡介】 ? int i,j,count=0,top=1。 ? int indegree[MAXVEX]。 ? FindInDegree(G,indegree)。 /* 求出圖中所有頂點的入度 */ ? for(i=0。i。i++) ? if(indegree[i]==0) / / 將入度為零的頂點入棧 ? { indegree[i]=top。 ? top=i。 ? } ? while(top!=1) /* 棧不為空 */ ? { j=top。 ? top=indegree[top]。 /* 取出當(dāng)前棧頂元素 */ ? topo[count++]=j。 /*ptopo數(shù)組存放拓撲序列 */ ? p=[j].firstarc。 ? //取該元素邊表中的第一個邊結(jié)點，刪除該結(jié)點 ,構(gòu)造新的 AOV網(wǎng) ? makeNewAOV(p,indegree,top)。 //對 indegree數(shù)組進行修改 ? } ? if(count) /* AOV網(wǎng)中存在回路 */ ? { printf(The aov work has a cycle\n)。 ? return FALSE。 ? } ? printf(拓撲序列為： )。 //輸出拓撲序列 ? for(i=0。i。i++) printf(V%1d ,topo[i]+1)。 printf(\n)。 ? return TRUE。 ? } ? void insert(ALGraph amp。G,int a,int b,float weight) ? /*在表尾插入表結(jié)點 */ ? { ArcNode *p,*temp。 ? temp=(ArcNode *)malloc(sizeof(ArcNode))。 ? tempadjvex=b。 ? tempnextarc=NULL。 ? tempweight=weight。 ? p=[a].firstarc。 ? if(p==NULL) ? [a].firstarc=temp。 ? else ? { while(pnextarc!=NULL) p=pnextarc。 /*找表尾 */ ? pnextarc=temp。 ? } ? } ? void makeList(ALGraph amp。G) /*鄰接表的構(gòu)造 */ ? { int i。 ? =9。 ? for(i=0。i。i++) //給頂點指針域賦初值 ? [i].firstarc=NULL。 ? insert(G,0,1,6)。 insert(G,0,2,4)。 insert(G,0,3,5)。 ? insert(G,1,4,1)。 insert(G,2,4,1)。 insert(G,3,5,2)。 ? insert(G,4,6,9)。 insert(G,4,7,7)。 insert(G,5,7,4)。 ? insert(G,6,8,2)。 insert(G,7,8,4)。 ? } ? define MAXEDGE 100 /*MAXEDEG為邊的最大數(shù)目 */ ? void countve(ALGraph G,int *topo,AdjType *ve) /* 計算各事件的最早發(fā)生時間 */ ? { int i,j,k。 ? ArcNode *p。 ? for(i=0。i。i++) ve[i]=0。 /*ee數(shù)組賦
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1