数据结构课程设计报告(完整版本)-

数据结构课程设计报告(完整版本)-

int i;

for(i=0;inextarc) indegree[p->adjvex]++; }

return 0; }

//拓扑排序同时求出各活动的最早发生时间

int ToPoOrder(ALGraph &G,Stack &T) {

int count=0;

int i,j,k; Stack S1; ArcNode *p;

int indegree[MAX_V_NUM]; InitStack(T); InitStack(S1);

FindInDegree(G,indegree); for(i=0;i

for(i=0;i

while(!StackEmpty(S1)) { Pop(S1,j); Push(T,j); count++; for(p=G.vertices[j].firstarc;p;p=p->nextarc) { k=p->adjvex; if(--indegree[k]==0) Push(S1,k);

17 / 33

数据结构课程设计报告(完整版本)-

if(ve[j]+(p->info)>ve[k]) ve[k]=ve[j]+(p->info); } }

// for(i=0;i

//计算各顶点的最迟发生时间及进行输出 int CriticalPath(ALGraph &G) {

int vl[MAX_V_NUM]; int dut;

int i,j,k,ee,el; ArcNode *p; // char tag;

if(!ToPoOrder(G,T)) return 0;

cout<<\完成整项工程至少需要的时间是：\.vnum-1]<nextarc) { k=p->adjvex; dut=(p->info); if(vl[k]-dut

// for(i=0;i

cout<<\影响工程进度的关键活动是:\ for(j=0;jnextarc) { k=p->adjvex;

18 / 33

数据结构课程设计报告(完整版本)-

dut=(p->info); ee=ve[j]; el=vl[k]-dut;

//cout<<\endl; if(ee==el) //tag=(ee=el)?'*':''; cout<name<

int main() {

ALGraph G; int i,j,Hnum; ArcNode *p,*q;

// int indegree[MAX_V_NUM]; //ALGraph G;

cout<<\请输入图中的顶点数和弧数以及图的标志和弧的标志：\

cin>>G.vnum; cin>>G.arcnum; cin>>G.kind; cin>>G.kind1;

cout<<\请完成该邻接表的输入：\ for(i=0;i

{ cout<<\请输入该顶点的信息\ cin>>G.vertices[i].data; cout<<\请输入与\.vertices[i].data<<\号顶点相邻的弧的数目:\ cin>>Hnum; if(Hnum==0) { G.vertices[i].firstarc=0; } else {

19 / 33

数据结构课程设计报告(完整版本)-

cout<<\请依次次输入弧的信息（包括顶点的位置及权值和该边的名称）\ p=(ArcNode *)malloc(sizeof(ArcNode)); G.vertices[i].firstarc=p; p->nextarc=0; cin>>p->adjvex; cin>>p->info; cin>>p->name; for(j=0;j>q->adjvex; cin>>q->info; cin>>q->name; q->nextarc=p->nextarc; p->nextarc=q; } } }

//ToPoOrder(G,T); //CriticalPath(G); ////////test//////////

/* for(i=0;inextarc) { cout<adjvex].data<

// FindInDegree(G,indegree); //for(i=0;i

// cout<<\ CriticalPath(G);

////////////test end///////////

return 0; }

20 / 33