1、程序清單：#includetypedef int VertexType;const int MaxVertexNum=20;/ 圖的最大頂點數，它應不小于具體圖的頂點數 n;const int MaxEdgeNum=30;/ 圖的最大邊數，它應不小于具體圖的最大邊數 e;typedef VertexType vexlistMaxVertexNum;/ 定義 vexlist 為存儲頂點信息的數組 類型struct edgenode/ 定義鄰接表中的邊結點類型int adjvex;/ 鄰接點域edgenode *next;/ 指向下一個邊結點的鏈域;typedefedgenode*adjlistM

2、axVertexNum;/ 這義 adjlist 為存儲 n 個表頭指針 的數組類型voidCreate2(vexlistGV,adjlistGL,intn,inte) / 看看 GL 到底是什么： GLi-adjvex/通過從鍵盤上輸入的n個頂點信息和e條有向邊的信息/建立頂點數組GV和鄰接表GLint i,j,k,w;/ 建立頂點數組cout輸入n個頂點endl;for(i=0;iGVi;/ 初始化鄰接表，即將表頭向量中的每個域置空for(i=0;in;i+)GLi=NULL;/ 建立鄰接表cout輸入vvevv條邊e ndl;for(k=1;k=e;k+)/ 輸入一條邊 cinij;/w

3、;/ 由系統分配一個新結點edgenode *p=new edgenode;/ 將 j 的值賦給新結點的鄰接點域p-adjvex=j;/p-weight=w;/ 將新結點插入到 vi 鄰接表的表頭p-next=GLi;GLi=p;7voidToposort(adjlistGL,intn)/ 此算法的時間復雜度為 o(n+e)/n 為頂點數 ,e 為 邊數/利用鄰接表GL表示的有向圖進行拓樸排序int i,j,k,top,m=0;/m 用來統計拓樸序列中的頂點/top 的值為一個入度為 0的頂點序號， top 指向的值為下一個入度為 0的 頂點序號edgenode *p;/ 定義存儲圖中每個頂點

4、入度的一維整型數組 dint *d=new intn;/ 初始化數組 d 中的每個元素值為 0for(i=0;in;i+)di=0;/ 利用數組 d 中的對應元素統計出每個頂點的入度for(i=0;iadjvex;dj+;p=p-next;top 為-1/ 初始化用于鏈接入度為 0 的元素的棧的棧頂指針 top=-1;/ 建立初始化棧for(i=0;in;i+)if(di=0)di=top;top=i;/ 每循環一次刪除一個頂點及所有出邊cout 拓樸序列如下 :endl; while(top!=-1)j=top;/j 的值為一個入度為 0 的頂點序號 top=dtop;/ 刪除棧頂點元素 coutjadjvex;/vk 是 vj 的一個鄰接點dk-;/vk 的入度減 1 if(dk=0)/ 把入度為 0 的元素進棧dk=top; top=k;p=p-next;/p 指向 vj 鄰接點表的下一個結點 coutendl;(拓樸圖是if(mn)/ 當輸出的頂點數小于圖中的頂點數時，輸出有回路信息 無回路的，因/ 為若帶有回路，則回路上的所有活動都無法進行 )coutThe network has a cycle!endl;void main()vexlist GV;adjlist GL;int