keypath.cpp

数据结构中关键路径算法的实现与应用。介绍求关键路经的算法

// KeyPath.cpp : Defines the entry point for the console application.
//

#include "StdAfx.h"
#include<stdio.h>
#include<stdlib.h>
#include<iomanip.h>
#include <process.h>

//#define PROJECTNUMBER 9//10
//#define PLANNUMBER 11//13

// 活动
typedef struct node
{
    int adjvex;			// 终点
    int dut;			// 花费的时间
    struct node *next;	// 边的终点节点
}edgenode;

// 节点
typedef struct 
{
    int projectname;	// 节点名称
    int id;				// 作为终点的数量
    edgenode *link;		// 作为起点的边
}vexnode;

//vexnode Graphicmap[PROJECTNUMBER];
// 创建图。参数：节点数组，节点数，活动数
void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)
{
    int begin,end,duttem;
    edgenode *p;
    for(int i=0;i<projectnumber;i++)
    {
		Graphicmap[i].projectname=i;
		Graphicmap[i].id =0;
		Graphicmap[i].link =NULL;
    }   

    printf("某项目的开始到结束在图中的节点输入<vi,vj,dut>\n");
    printf("如：3,4,9 回车表示第三节点到第四节点之间的活动用了9个单位时间\n");

    for(int k=0;k<activenumber;k++)
    {
       scanf("%d,%d,%d",&begin,&end,&duttem);
       p=(edgenode*)malloc(sizeof(edgenode));
       p->adjvex =end-1;
       p->dut =duttem;
       Graphicmap[end-1].id ++;
       p->next =Graphicmap[begin-1].link ;
       Graphicmap[begin-1].link =p;
    }
}

int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime)
{
    int i,j,k,m=0;
    int front=-1,rear=-1;
    int* topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列
    int* vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间
    int* ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间
    int* l =(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间
    int* e =(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间
    edgenode *p;
    totaltime=0;
    for(i=0;i<projectnumber;i++) 
		ve[i]=0;
    for(i=0;i<projectnumber;i++)
    {
       if(Graphicmap[i].id==0)
       {
         topologystack[++rear]=i;
         m++;
       }
    }

    while(front!=rear)
    {
       front++;
       j=topologystack[front];
       m++;
       p=Graphicmap[j].link ;
       while(p)
       {
           k=p->adjvex ;
           Graphicmap[k].id --;
           if(ve[j]+p->dut >ve[k])
              ve[k]=ve[j]+p->dut ;

           if(Graphicmap[k].id ==0)
              topologystack[++rear]=k;
           p=p->next ;
       }
    }

    if(m<projectnumber)
    {
       printf("\n本程序所建立的图有回路不可计算出关键路径\n");
       printf("将退出本程序\n");
       return 0;
    }

    totaltime=ve[projectnumber-1];

    for(i=0;i<projectnumber;i++)
       vl[i]=totaltime;

    for(i=projectnumber-2;i>=0;i--)
    {
       j=topologystack[i];
       p=Graphicmap[j].link ;
       while(p)
       {
           k=p->adjvex ;
           if((vl[k]-p->dut )<vl[j])
              vl[j]=vl[k]-p->dut ;
           p=p->next ;
       }
    }

    i=0;

    printf("| 起点 | 终点 |  最早开始时间  |  最迟完成时间  | 差值 |  备注  |\n");

    for(j=0;j<projectnumber;j++)
    {
       p=Graphicmap[j].link;

       while(p)
       {
           k=p->adjvex ;
           e[++i]=ve[j];
           l[i]=vl[k]-p->dut;
           printf("| %4d | %4d |    %4d    |    %4d    | %4d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]);
           if(l[i]==e[i])
              printf(" 关键活动 |");

           printf("\n");
           p=p->next ;
       }
    }

    return 1;
}

// 开始搜索关键路径
void seekkeyroot()
{
    int projectnumber,activenumber,totaltime=0;
    system("cls");

    printf("请输入这个工程的化成图形的节点数:");
    scanf("%d",&projectnumber);

	printf("请输入这个工程的活动个数:");
	scanf("%d",&activenumber);

	vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));

	CreateGraphic(Graphicmap,projectnumber,activenumber);
	SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);

	printf("整个工程所用的最短时间为：%d个单位时间\n",totaltime);
	system("pause");
}

int main()
{
    char ch;
    for(;;)
    {
       do 
       {
           system("cls");
           printf("|             欢迎进入求关键路径算法程序              |\n");
           for(int i=0;i<80;i++)printf("*");
           printf("%s","\n(S)tart开始输入工程的节点数据并求出关键路径\n");
           printf("%s","(E)xit退出\n");
           printf("%s","请输入选择:");
           scanf("%c",&ch);
           ch=toupper(ch);
       }while(ch!='S'&&ch!='E');

     switch(ch)
     {
		case'S':
			seekkeyroot();
			break;
		case'E': 
			return 1;
     }
    }
}