圖-鄰接表-拓?fù)渑判?--關(guān)鍵路徑

1、/圖的鄰接表的建立 -拓?fù)渑判?- 關(guān)鍵路徑#include<stdio.h> #include<stdlib.h> #define Max 20 / 最大結(jié)點(diǎn)數(shù)/鄰接表 結(jié)構(gòu)定義typedef struct arcnode/- 表結(jié)點(diǎn)int adj;/ 與之鄰接的節(jié)點(diǎn)的存放位置int quan;/ 結(jié)點(diǎn)與鄰接結(jié)點(diǎn)之間的權(quán)值struct arcnode *next; / 存放下一個(gè)相鄰接的結(jié)點(diǎn)arcnode;typedef struct vnode/ 頭結(jié)點(diǎn)char data;/存放結(jié)點(diǎn)名稱arcnode *first;/第一個(gè)與此節(jié)點(diǎn)鄰接的結(jié)點(diǎn) vnode,listM

2、ax;typedef struct/ 整個(gè)結(jié)構(gòu)的定義list vertices;/ 包括表int ve;/ 頂點(diǎn)數(shù)int ar;/ 弧數(shù)map;/圖的創(chuàng)建及相關(guān)函數(shù)int locate(map p,char u)/locate定位函數(shù)，返回字符 u 在圖 p 中的位置for(int i=0;i<p.ve;i+)if(p.verticesi.data=u)return i;void create(map &p)/ 創(chuàng)建圖 Pprintf(" 輸入頂點(diǎn)數(shù)，弧數(shù)： "); scanf("%d %d%*c",&p.ve,&p.ar)

3、;printf(" 輸入各結(jié)點(diǎn)名稱： n");/ 名稱為單個(gè)字符for(int i=0;i<p.ve;i+)scanf("%c%*c",&p.verticesi.data);p.verticesi.first=NULL;for(int k=0;k<p.ar;k+)printf（" 輸入相關(guān)聯(lián)的一對(duì)結(jié)點(diǎn)的名稱 及權(quán)值： "）; char v1,v2;int m1,m2;int m;scanf("%c%*c %c%*c %d%*c",&v1,&v2,&m);m1=locate

4、(p,v1);申請(qǐng) arcnode 結(jié)點(diǎn)存放關(guān)系m2=locate(p,v2);arcnode *z=(arcnode*)malloc(sizeof(arcnode);/ arcnode *zz;zz=p.verticesm1.first;p.verticesm1.first=z;z->next=zz;z->adj=m2;z->quan=m;/int SMax; 拓?fù)渑判?/ 輔助棧，存放入度為零的點(diǎn)int TMax;int ls=0;/ 棧， 放拓?fù)湫蛄? 棧 S 的長(zhǎng)度int l=0;/ 棧 T 的長(zhǎng)度int indegreeMax; / 各點(diǎn)的入度int veMax;/

5、 求關(guān)鍵路徑，放結(jié)點(diǎn)最早開(kāi)始時(shí)間int tuopu(map p) for(int i=0;i<Max;i+)vei=0;for(i=0;i<Max;i+)/初始化Si=0;Ti=0;indegreei=0;for(i=0;i<p.ve;i+)/indegree 中存放各結(jié)點(diǎn)的入度arcnode *z=p.verticesi.first;while(z!=NULL)indegreez->adj+;z=z->next;for(i=0;i<p.ve;i+) / 找出入度為零的結(jié)點(diǎn)入棧 Sif(indegreei=0)Sls+=i;int count=0;while

6、(ls!=0)/棧不為空時(shí)i=S-ls;/出棧/入棧 ，拓?fù)湫蛄袟?printf(" 拓?fù)湫蛄校?n %4d-%4cn",i,p.verticesi.data);Tl+=i;count+;for(arcnode *z=p.verticesi.first;z; z=z->next) /此節(jié)點(diǎn)去掉，與他有關(guān)的入度減一int k=z->adj;if(!(-indegreek)Sls+=k;/減一后，如入度為零，進(jìn)棧if(vei+z->quan>vek)vek=vei+z->quan;if(count<p.ve)return 0;return 1

7、;/關(guān)鍵路徑int vlMax;void lujing(map p)if(!tuopu(p)printf(" 無(wú)關(guān)鍵路徑 n");return;for(int i=0;i<p.ve;i+) / vl 初始化 vli=vep.ve-1;/ 各結(jié)點(diǎn)的最晚開(kāi)始時(shí)間while(l!=0)int j=T-l;arcnode *z=p.verticesj.first;for(; z; z=z->next)int k=z->adj;int dut=z->quan;if(vlk-dut<vlj)vlj=vlk-dut;for(int j=0;j<p.ve

8、;j+)/ 求出 ve 個(gè)頂點(diǎn)中的關(guān)鍵路徑arcnode *z;for(z=p.verticesj.first; z; z=z->next)int k=z->adj;int dut=z->quan;/ 結(jié)點(diǎn) j 的最早開(kāi)始時(shí)間 int el=vlk-dut; / 結(jié)點(diǎn) j 的最晚開(kāi)始時(shí)間 / 關(guān)鍵路徑用int ee=vej;char tag=(ee=el)? '*':' '* 表示printf("%d-%c-%cn",j,p.verticesj.data,tag);/主函數(shù)void main() map p;create(p);/ 創(chuàng)建 圖 pif(tuopu