图-邻接表-拓扑排序---关键路径.doc

/-图的邻接表的建立-拓扑排序-关键路径-#include#include#define Max 20 / 最大结点数/-邻接表 结构定义-typedef struct arcnode/-表结点int adj; / 与之邻接的节点的存放位置int quan; / 结点与邻接结点之间的权值 struct arcnode *next; /存放下一个相邻接的结点arcnode;typedef struct vnode/-头结点char data; /存放结点名称arcnode *first; /第一个与此节点邻接的结点vnode,listMax;typedef struct/-整个结构的定义list vertices; / 包括表int ve; / 顶点数int ar; / 弧数map;/-图的创建及相关函数-int locate(map p,char u)/locate 定位函数，返回字符 u 在图p 中的位置for(int i=0;ip.ve;i+)if(p.verticesi.data=u)return i;void create(map &p)/ 创建图 Pprintf(输入顶点数，弧数：);scanf(%d %d%*c,&p.ve,&p.ar);printf(输入各结点名称：n);/ 名称为单个字符for(int i=0;ip.ve;i+)scanf(%c%*c,&p.verticesi.data);p.verticesi.first=NULL;for(int k=0;knext=zz;z-adj=m2;z-quan=m;/-拓扑排序-int SMax; / 辅助栈，存放入度为零的点int TMax; / 栈， 放拓扑序列int ls=0; / 栈 S 的长度int l=0; / 栈 T 的长度int indegreeMax; / 各点的入度int veMax; /-求关键路径，放结点最早开始时间-int tuopu(map p)for(int i=0;iMax;i+)vei=0;for(i=0;iMax;i+) /初始化Si=0;Ti=0;indegreei=0;for(i=0;iadj+;z=z-next;for(i=0;inext) /此节点去掉，与他有关的入度减一int k=z-adj;if(!(-indegreek) /减一后，如入度为零，进栈Sls+=k;if(vei+z-quanvek)vek=vei+z-quan;if(countp.ve)return 0;return 1;/-关键路径-int vlMax;void lujing(map p)if(!tuopu(p)printf(无关键路径n);return;for(int i=0;inext)int k=z-adj;int dut=z-quan;if(vlk-dutvlj)vlj=vlk-dut;for(int j=0;jnext)int k=z-adj;int dut=z-quan;int ee=vej; / 结点 j的最早开始时间int el=vlk-dut; / 结点 j的最晚开始时间char tag=(ee=el)? *: ; / 关键路径用 * 表示printf(%d-%c-%cn,j,p.verticesj.data,tag);/-主函数-void main()map p;create(p); / 创建 图pif(tuopu(p);/是否拓扑有序for(int i=0