关键路径
数据结构中 求关键路径，以前写的代码，传给大家看看！
/* 名称：关键路径 语言：数据结构C语言版 编译环境：VC++ 6.0 日期：2014-3-25 */ #include <stdio.h> #include <limits.h> #include <malloc.h> #include<cstdlib> #include <string.h> // 求关键路径。实现算法7.13、7.14的程序 // 图的邻接表存储表示 #define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_VERTEX_NUM 20 typedef int InfoType; // 存放网的权值 typedef char VertexType[MAX_NAME]; // 字符串类型 typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网} typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info; // 网的权值指针） }ArcNode; // 表结点 typedef struct VNode { VertexType data; // 顶点信息 ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM];// 头结点 typedef struct { AdjList vertices; int vexnum,arcnum; // 图的当前顶点数和弧数 int kind; // 图的种类标志 }ALGraph; int ve[MAX_VERTEX_NUM]; // 全局变量(用于算法7.13和算法7.14) // 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 int LocateVex(ALGraph G,VertexType u) { int i; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vertices[i].data)==0) return i; return -1; } // 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。 int CreateGraph(ALGraph *G) { int i,j,k; int w; // 权值 VertexType va,vb; ArcNode *p; printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): "); scanf("%d",&(*G).kind); printf("请输入图的顶点数和边数:（空格）\n"); scanf("%d%d",&(*G).vexnum,&(*G).arcnum); printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME); for(i = 0; i < (*G).vexnum; ++i) // 构造顶点向量 { scanf("%s",(*G).vertices[i].data); (*G).vertices[i].firstarc = NULL; } if((*G).kind == 1 || (*G).kind == 3) // 网 printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n"); else // 图 printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n"); for(k = 0;k < (*G).arcnum; ++k) // 构造表结点链表 { if((*G).kind==1||(*G).kind==3) // 网 scanf("%d%s%s",&w,va,vb); else // 图 scanf("%s%s",vb); i = LocateVex(*G,va); // 弧尾 j = LocateVex(*G,vb); // 弧头 p = (ArcNode*)malloc(sizeof(ArcNode)); p->adjvex = j; if((*G).kind == 1 || (*G).kind == 3) // 网 { p->info = (int *)malloc(sizeof(int)); *(p->info) = w; } else p->info = NULL; // 图 p->nextarc = (*G).vertices[i].firstarc; // 插在表头 (*G).vertices[i].firstarc = p; if((*G).kind >= 2) // 无向图或网,产生第二个表结点 { p = (ArcNode*)malloc(sizeof(ArcNode)); p->adjvex = i; if((*G).kind == 3) // 无向网 { p->info = (int*)malloc(sizeof(int)); *(p->info) = w; } else p->info = NULL; // 无向图 p->nextarc = (*G).vertices[j].firstarc; // 插在表头 (*G).vertices[j].firstarc = p; } } return 1; } // 输出图的邻接表G。 void Display(ALGraph G) { int i; ArcNode *p; switch(G.kind) { case DG: printf("有向图\n"); break; case DN: printf("有向网\n"); break; case AG: printf("无向图\n"); break; case AN: printf("无向网\n"); } printf("%d个顶点：\n",G.vexnum); for(i = 0; i < G.vexnum; ++i) printf("%s ",G.vertices[i].data); printf("\n%d条弧(边):\n",G.arcnum); for(i = 0; i < G.vexnum; i++) { p = G.vertices[i].firstarc; while(p) { if(G.kind <= 1) // 有向 { printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data); if(G.kind == DN) // 网 printf(":%d ",*(p->info)); } else // 无向(避免输出两次) { if(i < p->adjvex) { printf("%s－%s ",G.vertices[p->adjvex].data); if(G.kind == AN) // 网 printf(":%d ",*(p->info)); } } p=p->nextarc; } printf("\n"); } } // 求顶点的入度，算法7.12、7.13调用 void FindInDegree(ALGraph G,int indegree[]) { int i; ArcNode *p; for(i=0;i<G.vexnum;i++) indegree[i]=0; // 赋初值 for(i=0;i<G.vexnum;i++) { p=G.vertices[i].firstarc; while(p) { indegree[p->adjvex]++; p=p->nextarc; } } } typedef int SElemType; // 栈类型 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 // 栈的顺序存储表示 P46 typedef struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }SqStack; // 顺序栈 // 构造一个空栈S。 int InitStack(SqStack *S) { // 为栈底分配一个指定大小的存储空间 (*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if( !(*S).base ) exit(0); // 存储分配失败 (*S).top = (*S).base; // 栈底与栈顶相同表示一个空栈 (*S).stacksize = STACK_INIT_SIZE; return 1; } // 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。 int StackEmpty(SqStack S) { if(S.top == S.base) return 1; else return 0; } // 插入元素e为新的栈顶元素。 int Push(SqStack *S,SElemType e) { if((*S).top - (*S).base >= (*S).stacksize) // 栈满，追加存储空间 { (*S).base = (SElemType *)realloc((*S).base,((*S).stacksize + STACKINCREMENT) * sizeof(SElemType)); if( !(*S).base ) exit(0); // 存储分配失败 (*S).top = (*S).base+(*S).stacksize; (*S).stacksize += STACKINCREMENT; } *((*S).top)++=e; // 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向左 return 1; } // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。 int Pop(SqStack *S,SElemType *e) { if((*S).top == (*S).base) return 0; *e = *--(*S).top; // 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向左 return 1; } // 算法7.13 P185 // 有向网G采用邻接表存储结构,求各顶点事件的最早发生时间ve (全局变量)。 // T为拓扑序列顶点栈,S为零入度顶点栈。若G无回路,则用栈T返回G的一个拓 // 扑序列,且函数值为1,否则为0 int TopologicalOrder(ALGraph G,SqStack *T) { int j,k,count,indegree[MAX_VERTEX_NUM]; SqStack S; ArcNode *p; FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1] InitStack(&S); // 初始化栈 for(j=0;j<G.vexnum;++j) // 建零入度顶点栈S if(!indegree[j]) Push(&S,j); // 入度为0者进栈 InitStack(T); // 初始化拓扑序列顶点栈 count=0; // 对输出顶点计数 for(j=0;j<G.vexnum;++j) // 初始化ve[]=0 (最小值) ve[j]=0; while(!StackEmpty(S)) { // 栈不空 Pop(&S,&j); Push(T,j); // j号顶点入T栈并计数 ++count; for(p=G.vertices[j].firstarc;p;p=p->nextarc) { // 对j号顶点的每个邻接点的入度减1 k=p->adjvex; if(--indegree[k]==0) // 若入度减为0,则入栈 Push(&S,k); if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info); } } if(count<G.vexnum) { printf("此有向网有回路\n"); return 0; } else return 1; } // 算法7.14 P185 // G为有向网,输出G的各项关键活动 int CriticalPath(ALGraph G) { int vl[MAX_VERTEX_NUM]; SqStack T; int i,ee,el; ArcNode *p; char dut,tag; if(!TopologicalOrder(G,&T)) // 产生有向环 return 0; j=ve[0]; for(i=1;i<G.vexnum;i++) // j=Max(ve[]) 完成点的值 if(ve[i]>j) j=ve[i]; for(i=0;i<G.vexnum;i++) // 初始化顶点事件的最迟发生时间(最大值) vl[i]=j; // 完成点的最早发生时间 while(!StackEmpty(T)) // 按拓扑逆序求各顶点的vl值 for(Pop(&T,&j),p=G.vertices[j].firstarc;p;p=p->nextarc) { k=p->adjvex; dut=*(p->info); // dut<j,k> if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut; } printf(" j k dut ee el tag\n"); for(j=0;j<G.vexnum;++j) // 求ee,el和关键活动 for(p=G.vertices[j].firstarc;p;p=p->nextarc) { k=p->adjvex; dut=*(p->info); ee=ve[j]; el=vl[k]-dut; tag=(ee==el)?'*':' '; // 输出关键活动 printf("%2d %2d %3d %3d %3d %c\n",dut,el,tag); } printf("关键活动为:\n"); for(j=0;j<G.vexnum;++j) // 同上 for(p=G.vertices[j].firstarc;p;p=p->nextarc) { k=p->adjvex; dut=*(p->info); if(ve[j]==vl[k]-dut) // 输出关键活动 printf("%s→%s\n",G.vertices[j].data,G.vertices[k].data); } return 1; } int main() { ALGraph h; printf("请选择有向网\n"); CreateGraph(&h); Display(h); CriticalPath(h); system("pause"); return 0; } /* 输出效果： 请选择有向网 请输入图的类型(有向图:0,无向网:3): 1 请输入图的顶点数和边数:（空格） 6 8 请输入6个顶点的值(<3个字符): v1 v2 v3 v4 v5 v6 请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔): 3 v1 v2 2 v1 v3 2 v2 v4 3 v2 v5 4 v3 v4 3 v3 v6 2 v4 v6 1 v5 v6 有向网 6个顶点： v1 v2 v3 v4 v5 v6 8条弧(边): v1→v3 :2 v1→v2 :3 v2→v5 :3 v2→v4 :2 v3→v6 :3 v3→v4 :4 v4→v6 :2 v5→v6 :1 j k dut ee el tag 0 2 2 0 0 * 0 1 3 0 1 1 4 3 3 4 1 3 2 3 4 2 5 3 2 5 2 3 4 2 2 * 3 5 2 6 6 * 4 5 1 6 7 关键活动为: v1→v3 v3→v4 v4→v6 请按任意键继续. . . */
