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

////-------------------------------------图的邻接表的建立--拓扑排序---关键路径-------------

#include<stdio.h>#include<stdlib.h>#defineMax20//最大结点数
//--------------------------------------邻接表结构定义------------------------------typedefstructarcnode//---表结点{intadj;//与之邻接的节点的存放位置intquan;//结点与邻接结点之间的权值structarcnode*next;//存放下一个相邻接的结点}arcnode;
typedefstructvnode///----头结点{chardata;//存放结点名称arcnode*first;//第一个与此节点邻接的结点}vnode,list[Max];
typedefstruct/////////----整个结构的定义{listvertices;//包括表intve;//顶点数intar;//弧数}map;
////---------------------------------图的创建及相关函数-----------------------
intlocate(mapp,charu)/////////locate定位函数，返回字符u在图p中的位置{for(inti=0;i<p.ve;i++){if(p.vertices[i].data==u)returni;}}
voidcreate(map&p)///////////创建图P{printf("输入顶点数，弧数：");scanf("%d%d%*c",&p.ve,&p.ar);
printf("输入各结点名称：\n");//名称为单个字符for(inti=0;i<p.ve;i++){scanf("%c%*c",&p.vertices[i].data);p.vertices[i].first=NULL;}
for(intk=0;k<p.ar;k++){printf("输入相关联的一对结点的名称及权值：");charv1,v2;intm1,m2;intm;scanf("%c%*c%c%*c%d%*c",&v1,&v2,&m);m1=locate(p,v1);m2=locate(p,v2);
arcnode*z=(arcnode*)malloc(sizeof(arcnode));//申请arcnode结点存放关系arcnode*zz;zz=p.vertices[m1].first;p.vertices[m1].first=z;z->next=zz;z->adj=m2;z->quan=m;}}//----------------------------------------拓扑排序----------------------------intS[Max];//辅助栈，存放入度为零的点intT[Max];//栈，放拓扑序列intls=0;//栈S的长度intl=0;//栈T的长度intindegree[Max];//各点的入度intve[Max];//------求关键路径，放结点最早开始时间-----
inttuopu(mapp){for(inti=0;i<Max;i++)ve[i]=0;for(i=0;i<Max;i++)//初始化{S[i]=0;T[i]=0;indegree[i]=0;}for(i=0;i<p.ve;i++)//indegree中存放各结点的入度{arcnode*z=p.vertices[i].first;while(z!=NULL){indegree[z->adj]++;z=z->next;}}for(i=0;i<p.ve;i++)//找出入度为零的结点入栈S{if(indegree[i]==0)S[ls++]=i;}intcount=0;while(ls!=0)//栈不为空时{i=S[--ls];//出栈T[l++]=i;//入栈，拓扑序列栈//printf("拓扑序列：\n%4d---%4c\n",i,p.vertices[i].data);count++;for(arcnode*z=p.vertices[i].first;z;z=z->next)//此节点去掉，与他有关的入度减一{intk=z->adj;if(!(--indegree[k]))//减一后，如入度为零，进栈S[ls++]=k;if(ve[i]+z->quan>ve[k])ve[k]=ve[i]+z->quan;}}if(count<p.ve)return0;return1;}
//---------------------