最好的素材网站,展示类网站模板,网站页面设计的网址,微信商城怎么开商城一#xff1a;拓扑排序
前面讲过拓扑排序只是简单的描述#xff0c;下面具体的实现。
用顶点表示活动#xff0c;用弧表示活动间的优先关系的有向图为AOV网。
AOV网中没有环#xff0c;检测的办法是进行拓扑排序。
步骤#xff1a; (1)在有向图中选一个没有前驱的顶点…一拓扑排序
前面讲过拓扑排序只是简单的描述下面具体的实现。
用顶点表示活动用弧表示活动间的优先关系的有向图为AOV网。
AOV网中没有环检测的办法是进行拓扑排序。
步骤 (1)在有向图中选一个没有前驱的顶点且输出之。
(2)从图中删除该顶点和所有以它为尾的弧。
重复上述两步直至全部顶点均已输出或者当前图中不存在无前驱的顶点为止。另一种情况则说明有向图中存在环。
以有向图为例图中,V1和V6没有前驱则可任选一个。假设先输出V6在删除V6及弧V6,V4V6,V5之后只有顶点V1没有
前驱则输出V1且删去V1及弧V1,V2,V1,V3,V1,V4之后V3和V4都没有前驱。依次类推,可从中任选一个继续进行。整个拓扑
排序的过程如图7.28所示。最后得到该有向图的拓扑有序序列为: V6-V1-V4-V3-V2-V5 具体代码用C语言实现如下 #includestring.h#includectype.h#includemalloc.h /* malloc()等 */#includelimits.h /* INT_MAX等 */#includestdio.h /* EOF(^Z或F6),NULL */#includestdlib.h /* atoi() */#includeio.h /* eof() */#includemath.h /* floor(),ceil(),abs() */#includeprocess.h /* exit() *//* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status; /* Status是函数的类型,其值是函数结果状态代码如OK等 */typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */#define MAX_NAME 5 /* 顶点字符串的最大长度 */typedef int InfoType;typedef char VertexType[MAX_NAME]; /* 字符串类型 *//* 图的邻接表存储表示 */#define MAX_VERTEX_NUM 20typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */typedef struct ArcNode{int adjvex; /* 该弧所指向的顶点的位置 */struct ArcNode *nextarc; /* 指向下一条弧的指针 */InfoType *info; /* 网的权值指针 */}ArcNode; /* 表结点 */typedef struct{VertexType data; /* 顶点信息 */ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */typedef struct{AdjList vertices;int vexnum,arcnum; /* 图的当前顶点数和弧数 */int kind; /* 图的种类标志 */}ALGraph;/* 图的邻接表存储的基本操作(15个) */int LocateVex(ALGraph G,VertexType u){ /* 初始条件: 图G存在,u和G中顶点有相同特征 *//* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */int i;for(i0;iG.vexnum;i)if(strcmp(u,G.vertices[i].data)0) //比较顶点是否相等return i;return -1;}Status CreateGraph(ALGraph *G){ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */int i,j,k;int w; /* 权值 */VertexType va,vb;ArcNode *p;printf(请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): );scanf(%d,(*G).kind);printf(请输入图的顶点数,边数: );scanf(%d,%d,(*G).vexnum,(*G).arcnum);printf(请输入%d个顶点的值(%d个字符):\n,(*G).vexnum,MAX_NAME);for(i0;i(*G).vexnum;i) /* 构造顶点向量 */{scanf(%s,(*G).vertices[i].data);(*G).vertices[i].firstarcNULL;}if((*G).kind1||(*G).kind3) /* 网 */printf(请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n);else /* 图 */printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n);for(k0;k(*G).arcnum;k) /* 构造表结点链表 */{if((*G).kind1||(*G).kind3) /* 网 */scanf(%d%s%s,w,va,vb);else /* 图 */scanf(%s%s,va,vb);iLocateVex(*G,va); /* 弧尾 */jLocateVex(*G,vb); /* 弧头 */p(ArcNode*)malloc(sizeof(ArcNode));p-adjvexj;if((*G).kind1||(*G).kind3) /* 网 */{p-info(int *)malloc(sizeof(int));*(p-info)w; //网的权值指针}elsep-infoNULL; /* 图 */p-nextarc(*G).vertices[i].firstarc; /* 插在表头 */(*G).vertices[i].firstarcp;if((*G).kind2) /* 无向图或网,产生第二个表结点 */{p(ArcNode*)malloc(sizeof(ArcNode));p-adjvexi;if((*G).kind3) /* 无向网 */{p-info(int*)malloc(sizeof(int));*(p-info)w;}elsep-infoNULL; /* 无向图 */p-nextarc(*G).vertices[j].firstarc; /* 插在表头 */(*G).vertices[j].firstarcp;}}return OK;}void DestroyGraph(ALGraph *G){ /* 初始条件: 图G存在。操作结果: 销毁图G */int i;ArcNode *p,*q;(*G).vexnum0;(*G).arcnum0;for(i0;i(*G).vexnum;i){p(*G).vertices[i].firstarc; //第一个表结点的地址头结点while(p){qp-nextarc;if((*G).kind%2) /* 网 */free(p-info);free(p);pq;}}}VertexType* GetVex(ALGraph G,int v){ /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */if(vG.vexnum||v0)exit(ERROR);return G.vertices[v].data;}Status PutVex(ALGraph *G,VertexType v,VertexType value){ /* 初始条件: 图G存在,v是G中某个顶点 *//* 操作结果: 对v赋新值value */int i;iLocateVex(*G,v); //先找到该顶点if(i-1) /* v是G的顶点 */{strcpy((*G).vertices[i].data,value);return OK;}return ERROR;}int FirstAdjVex(ALGraph G,VertexType v){ /* 初始条件: 图G存在,v是G中某个顶点 *//* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */ArcNode *p;int v1;v1LocateVex(G,v); /* v1为顶点v在图G中的序号 */pG.vertices[v1].firstarc;if(p)return p-adjvex;elsereturn -1;}int NextAdjVex(ALGraph G,VertexType v,VertexType w){ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 *//* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 *//* 若w是v的最后一个邻接点,则返回-1 */ArcNode *p;int v1,w1;v1LocateVex(G,v); /* v1为顶点v在图G中的序号 */w1LocateVex(G,w); /* w1为顶点w在图G中的序号 */pG.vertices[v1].firstarc;while(pp-adjvex!w1) /* 指针p不空且所指表结点不是w */pp-nextarc;if(!p||!p-nextarc) /* 没找到w或w是最后一个邻接点 */return -1;else /* p-adjvexw */return p-nextarc-adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */}void InsertVex(ALGraph *G,VertexType v){ /* 初始条件: 图G存在,v和图中顶点有相同特征 *//* 操作结果: 在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做) */strcpy((*G).vertices[(*G).vexnum].data,v); /* 构造新顶点向量 */(*G).vertices[(*G).vexnum].firstarcNULL;(*G).vexnum; /* 图G的顶点数加1 */}Status DeleteVex(ALGraph *G,VertexType v){ /* 初始条件: 图G存在,v是G中某个顶点 *//* 操作结果: 删除G中顶点v及其相关的弧 */int i,j;ArcNode *p,*q;jLocateVex(*G,v); /* j是顶点v的序号 */if(j0) /* v不是图G的顶点 */return ERROR;p(*G).vertices[j].firstarc; /* 删除以v为出度的弧或边 */while(p){qp;pp-nextarc;if((*G).kind%2) /* 网 */free(q-info);free(q);(*G).arcnum--; /* 弧或边数减1 */}(*G).vexnum--; /* 顶点数减1 */for(ij;i(*G).vexnum;i) /* 顶点v后面的顶点前移 */(*G).vertices[i](*G).vertices[i1];for(i0;i(*G).vexnum;i) /* 删除以v为入度的弧或边且必要时修改表结点的顶点位置值 */{p(*G).vertices[i].firstarc; /* 指向第1条弧或边 */while(p) /* 有弧 */{if(p-adjvexj){if(p(*G).vertices[i].firstarc) /* 待删结点是第1个结点 */{(*G).vertices[i].firstarcp-nextarc;if((*G).kind%2) /* 网 */free(p-info);free(p);p(*G).vertices[i].firstarc;if((*G).kind2) /* 有向 */(*G).arcnum--; /* 弧或边数减1 */}else{q-nextarcp-nextarc;if((*G).kind%2) /* 网 */free(p-info);free(p);pq-nextarc;if((*G).kind2) /* 有向 */(*G).arcnum--; /* 弧或边数减1 */}}else{if(p-adjvexj)p-adjvex--; /* 修改表结点的顶点位置值(序号) */qp;pp-nextarc;}}}return OK;}Status InsertArc(ALGraph *G,VertexType v,VertexType w){ /* 初始条件: 图G存在,v和w是G中两个顶点 *//* 操作结果: 在G中增添弧v,w,若G是无向的,则还增添对称弧w,v */ArcNode *p;int w1,i,j;iLocateVex(*G,v); /* 弧尾或边的序号 */jLocateVex(*G,w); /* 弧头或边的序号 */if(i0||j0)return ERROR;(*G).arcnum; /* 图G的弧或边的数目加1 */if((*G).kind%2) /* 网 */{printf(请输入弧(边)%s→%s的权值: ,v,w);scanf(%d,w1);}p(ArcNode*)malloc(sizeof(ArcNode));p-adjvexj;if((*G).kind%2) /* 网 */{p-info(int*)malloc(sizeof(int));*(p-info)w1;}elsep-infoNULL;p-nextarc(*G).vertices[i].firstarc; /* 插在表头 */(*G).vertices[i].firstarcp;if((*G).kind2) /* 无向,生成另一个表结点 */{p(ArcNode*)malloc(sizeof(ArcNode));p-adjvexi;if((*G).kind3) /* 无向网 */{p-info(int*)malloc(sizeof(int));*(p-info)w1;}elsep-infoNULL;p-nextarc(*G).vertices[j].firstarc; /* 插在表头 */(*G).vertices[j].firstarcp;}return OK;}Status DeleteArc(ALGraph *G,VertexType v,VertexType w){ /* 初始条件: 图G存在,v和w是G中两个顶点 *//* 操作结果: 在G中删除弧v,w,若G是无向的,则还删除对称弧w,v */ArcNode *p,*q;int i,j;iLocateVex(*G,v); /* i是顶点v(弧尾)的序号 */jLocateVex(*G,w); /* j是顶点w(弧头)的序号 */if(i0||j0||ij)return ERROR;p(*G).vertices[i].firstarc; /* p指向顶点v的第一条出弧 */while(pp-adjvex!j) /* p不空且所指之弧不是待删除弧v,w */{ /* p指向下一条弧 */qp;pp-nextarc;}if(pp-adjvexj) /* 找到弧v,w */{if(p(*G).vertices[i].firstarc) /* p所指是第1条弧 */(*G).vertices[i].firstarcp-nextarc; /* 指向下一条弧 */elseq-nextarcp-nextarc; /* 指向下一条弧 */if((*G).kind%2) /* 网 */free(p-info);free(p); /* 释放此结点 */(*G).arcnum--; /* 弧或边数减1 */}if((*G).kind2) /* 无向,删除对称弧w,v */{p(*G).vertices[j].firstarc; /* p指隙サ鉾的第一条出弧 */while(pp-adjvex!i) /* p不空且所指之弧不是待删除弧w,v */{ /* p指向下一条弧 */qp;pp-nextarc;}if(pp-adjvexi) /* 找到弧w,v */{if(p(*G).vertices[j].firstarc) /* p所指是第1条弧 */(*G).vertices[j].firstarcp-nextarc; /* 指向下一条弧 */elseq-nextarcp-nextarc; /* 指向下一条弧 */if((*G).kind3) /* 无向网 */free(p-info);free(p); /* 释放此结点 */}}return OK;}Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */void(*VisitFunc)(char* v); /* 函数变量(全局量) */void DFS(ALGraph G,int v){ /* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */int w;VertexType v1,w1;strcpy(v1,*GetVex(G,v));visited[v]TRUE; /* 设置访问标志为TRUE(已访问) */VisitFunc(G.vertices[v].data); /* 访问第v个顶点 */for(wFirstAdjVex(G,v1);w0;wNextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))if(!visited[w])DFS(G,w); /* 对v的尚未访问的邻接点w递归调用DFS */}void DFSTraverse(ALGraph G,void(*Visit)(char*)){ /* 对图G作深度优先遍历。算法7.4 */int v;VisitFuncVisit; /* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */for(v0;vG.vexnum;v)visited[v]FALSE; /* 访问标志数组初始化 */for(v0;vG.vexnum;v)if(!visited[v])DFS(G,v); /* 对尚未访问的顶点调用DFS */printf(\n);}typedef int QElemType; /* 队列类型 *//* c3-2.h 单链队列队列的链式存储结构 */typedef struct QNode{QElemType data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front,rear; /* 队头、队尾指针 */}LinkQueue;
/* bo3-2.c 链队列(存储结构由c3-2.h定义)的基本操作(9个) */Status InitQueue(LinkQueue *Q){ /* 构造一个空队列Q */(*Q).front(*Q).rear(QueuePtr)malloc(sizeof(QNode));if(!(*Q).front)exit(OVERFLOW);(*Q).front-nextNULL;return OK;}Status DestroyQueue(LinkQueue *Q){ /* 销毁队列Q(无论空否均可) */while((*Q).front){(*Q).rear(*Q).front-next;free((*Q).front);(*Q).front(*Q).rear;}return OK;}Status ClearQueue(LinkQueue *Q){ /* 将Q清为空队列 */QueuePtr p,q;(*Q).rear(*Q).front;p(*Q).front-next;(*Q).front-nextNULL;while(p){qp;pp-next;free(q);}return OK;}Status QueueEmpty(LinkQueue Q){ /* 若Q为空队列,则返回TRUE,否则返回FALSE */if(Q.frontQ.rear)return TRUE;elsereturn FALSE;}int QueueLength(LinkQueue Q){ /* 求队列的长度 */int i0;QueuePtr p;pQ.front;while(Q.rear!p){i;pp-next;}return i;}Status GetHead_Q(LinkQueue Q,QElemType *e) /* 避免与bo2-6.c重名 */{ /* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */QueuePtr p;if(Q.frontQ.rear)return ERROR;pQ.front-next;*ep-data;return OK;}Status EnQueue(LinkQueue *Q,QElemType e){ /* 插入元素e为Q的新的队尾元素 */QueuePtr p(QueuePtr)malloc(sizeof(QNode));if(!p) /* 存储分配失败 */exit(OVERFLOW);p-datae;p-nextNULL;(*Q).rear-nextp;(*Q).rearp;return OK;}Status DeQueue(LinkQueue *Q,QElemType *e){ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */QueuePtr p;if((*Q).front(*Q).rear)return ERROR;p(*Q).front-next;*ep-data;(*Q).front-nextp-next;if((*Q).rearp)(*Q).rear(*Q).front;free(p);return OK;}Status QueueTraverse(LinkQueue Q,void(*vi)(QElemType)){ /* 从队头到队尾依次对队列Q中每个元素调用函数vi()。一旦vi失败,则操作失败 */QueuePtr p;pQ.front-next;while(p){vi(p-data);pp-next;}printf(\n);return OK;}void BFSTraverse(ALGraph G,void(*Visit)(char*)){/*按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。算法7.6 */int v,u,w;VertexType u1,w1;LinkQueue Q;for(v0;vG.vexnum;v)visited[v]FALSE; /* 置初值 */InitQueue(Q); /* 置空的辅助队列Q */for(v0;vG.vexnum;v) /* 如果是连通图,只v0就遍历全图 */if(!visited[v]) /* v尚未访问 */{visited[v]TRUE;Visit(G.vertices[v].data);EnQueue(Q,v); /* v入队列 */while(!QueueEmpty(Q)) /* 队列不空 */{DeQueue(Q,u); /* 队头元素出队并置为u */strcpy(u1,*GetVex(G,u));for(wFirstAdjVex(G,u1);w0;wNextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))if(!visited[w]) /* w为u的尚未访问的邻接顶点 */{visited[w]TRUE;Visit(G.vertices[w].data);EnQueue(Q,w); /* w入队 */}}}printf(\n);}void Display(ALGraph G){ /* 输出图的邻接矩阵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(i0;iG.vexnum;i)printf(%s ,G.vertices[i].data);printf(\n%d条弧(边):\n,G.arcnum);for(i0;iG.vexnum;i){pG.vertices[i].firstarc;while(p){if(G.kind1) /* 有向 */{printf(%s→%s ,G.vertices[i].data,G.vertices[p-adjvex].data);if(G.kindDN) /* 网 */printf(:%d ,*(p-info));}else /* 无向(避免输出两次) */{if(ip-adjvex){printf(%s%s ,G.vertices[i].data,G.vertices[p-adjvex].data);if(G.kindAN) /* 网 */printf(:%d ,*(p-info));}}pp-nextarc;}printf(\n);}}void FindInDegree(ALGraph G,int indegree[]){ /* 求顶点的入度算法7.12、7.13调用 */int i;ArcNode *p;for(i0;iG.vexnum;i)indegree[i]0; /* 赋初值 */for(i0;iG.vexnum;i){pG.vertices[i].firstarc;while(p){indegree[p-adjvex];pp-nextarc;}}}typedef int SElemType; /* 栈类型 */#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */#define STACKINCREMENT 2 /* 存储空间分配增量 */typedef struct SqStack{SElemType *base; /* 在栈构造之前和销毁之后base的值为NULL */SElemType *top; /* 栈顶指针 */int stacksize; /* 当前已分配的存储空间以元素为单位 */}SqStack; /* 顺序栈 *//* 顺序栈的基本操作9个 */Status InitStack(SqStack *S){ /* 构造一个空栈S */(*S).base(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW); /* 存储分配失败 */(*S).top(*S).base;(*S).stacksizeSTACK_INIT_SIZE;return OK;}Status DestroyStack(SqStack *S){ /* 销毁栈SS不再存在 */free((*S).base);(*S).baseNULL;(*S).topNULL;(*S).stacksize0;return OK;}Status ClearStack(SqStack *S){ /* 把S置为空栈 */(*S).top(*S).base;return OK;}Status StackEmpty(SqStack S){ /* 若栈S为空栈则返回TRUE否则返回FALSE */if(S.topS.base)return TRUE;elsereturn FALSE;}int StackLength(SqStack S){ /* 返回S的元素个数即栈的长度 */return S.top-S.base;}Status GetTop(SqStack S,SElemType *e){ /* 若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR */if(S.topS.base){*e*(S.top-1);return OK;}elsereturn ERROR;}Status Push(SqStack *S,SElemType e){ /* 插入元素e为新的栈顶元素 */if((*S).top-(*S).base(*S).stacksize) /* 栈满追加存储空间 */{(*S).base(SElemType *)realloc((*S).base,((*S).stacksizeSTACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW); /* 存储分配失败 */(*S).top(*S).base(*S).stacksize;(*S).stacksizeSTACKINCREMENT;}*((*S).top)e;return OK;}Status Pop(SqStack *S,SElemType *e){ /* 若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR */if((*S).top(*S).base)return ERROR;*e*--(*S).top;return OK;}Status StackTraverse(SqStack S,Status(*visit)(SElemType)){ /* 从栈底到栈顶依次对栈中每个元素调用函数visit()。 *//* 一旦visit()失败则操作失败 */while(S.topS.base)visit(*S.base);printf(\n);return OK;}Status TopologicalSort(ALGraph G){ /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, *//* 否则返回ERROR。算法7.12 */int i,k,count,indegree[MAX_VERTEX_NUM];SqStack S;ArcNode *p;FindInDegree(G,indegree); /* 对各顶点求入度indegree[0..vernum-1] */InitStack(S); /* 初始化栈 */for(i0;iG.vexnum;i) /* 建零入度顶点栈S */if(!indegree[i])Push(S,i); /* 入度为0者进栈 */count0; /* 对输出顶点计数 */while(!StackEmpty(S)){ /* 栈不空 */Pop(S,i);printf(%s ,G.vertices[i].data); /* 输出i号顶点并计数 */count;for(pG.vertices[i].firstarc;p;pp-nextarc){ /* 对i号顶点的每个邻接点的入度减1 */kp-adjvex;if(!(--indegree[k])) /* 若入度减为0,则入栈 */Push(S,k);}}if(countG.vexnum){printf(此有向图有回路\n);return ERROR;}else{printf(为一个拓扑序列。\n);return OK;}}void main(){ALGraph f;printf(请选择有向图\n);CreateGraph(f);Display(f);TopologicalSort(f);}二关键路径 与AOV网对应的是AOE网即用边表示活动的网AOE网是一个带权的有向无环图顶点表示事件弧表示活动权表示活动持续的时间。通常用AOE网估计工程的完成时间。
由于在AOE网中有些活动可以并行的进行所以完成工程的最短时间是从开始点到完成点的最长路径的长度。路径最长的叫关键路径我们用e(i)表示活动最早开始时间l(i)表示最迟开始时间。两者之差l(i)一e(i)意味着完成活动a的时间余量。我们把l(i)e(i)的活动叫做关键活动。显然;关键路径上的所有活动都是关键活动因此提前完成非关键活动并不能加快工程的进度。 用代码C语言实现如下
#includestring.h#includectype.h#includemalloc.h /* malloc()等 */#includelimits.h /* INT_MAX等 */#includestdio.h /* EOF(^Z或F6),NULL */#includestdlib.h /* atoi() */#includeio.h /* eof() */#includemath.h /* floor(),ceil(),abs() */#includeprocess.h /* exit() *//* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status; /* Status是函数的类型,其值是函数结果状态代码如OK等 */typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */#define MAX_NAME 5 /* 顶点字符串的最大长度 */typedef int InfoType;typedef char VertexType[MAX_NAME]; /* 字符串类型 *//* c7-2.h 图的邻接表存储表示 */#define MAX_VERTEX_NUM 20typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */typedef struct ArcNode{int adjvex; /* 该弧所指向的顶点的位置 */struct ArcNode *nextarc; /* 指向下一条弧的指针 */InfoType *info; /* 网的权值指针 */}ArcNode; /* 表结点 */typedef struct{VertexType data; /* 顶点信息 */ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */typedef struct{AdjList vertices;int vexnum,arcnum; /* 图的当前顶点数和弧数 */int kind; /* 图的种类标志 */}ALGraph;/* bo7-2.c 图的邻接表存储(存储结构由c7-2.h定义)的基本操作(15个) */int LocateVex(ALGraph G,VertexType u){ /* 初始条件: 图G存在,u和G中顶点有相同特征 *//* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */int i;for(i0;iG.vexnum;i)if(strcmp(u,G.vertices[i].data)0)return i;return -1;}Status CreateGraph(ALGraph *G){ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */int i,j,k;int w; /* 权值 */VertexType va,vb;ArcNode *p;printf(请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): );scanf(%d,(*G).kind);printf(请输入图的顶点数,边数: );scanf(%d,%d,(*G).vexnum,(*G).arcnum);printf(请输入%d个顶点的值(%d个字符):\n,(*G).vexnum,MAX_NAME);for(i0;i(*G).vexnum;i) /* 构造顶点向量 */{scanf(%s,(*G).vertices[i].data);(*G).vertices[i].firstarcNULL;}if((*G).kind1||(*G).kind3) /* 网 */printf(请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n);else /* 图 */printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n);for(k0;k(*G).arcnum;k) /* 构造表结点链表 */{if((*G).kind1||(*G).kind3) /* 网 */scanf(%d%s%s,w,va,vb);else /* 图 */scanf(%s%s,va,vb);iLocateVex(*G,va); /* 弧尾 */jLocateVex(*G,vb); /* 弧头 */p(ArcNode*)malloc(sizeof(ArcNode));p-adjvexj;if((*G).kind1||(*G).kind3) /* 网 */{p-info(int *)malloc(sizeof(int));*(p-info)w;}elsep-infoNULL; /* 图 */p-nextarc(*G).vertices[i].firstarc; /* 插在表头 */(*G).vertices[i].firstarcp;if((*G).kind2) /* 无向图或网,产生第二个表结点 */{p(ArcNode*)malloc(sizeof(ArcNode));p-adjvexi;if((*G).kind3) /* 无向网 */{p-info(int*)malloc(sizeof(int));*(p-info)w;}elsep-infoNULL; /* 无向图 */p-nextarc(*G).vertices[j].firstarc; /* 插在表头 */(*G).vertices[j].firstarcp;}}return OK;}void DestroyGraph(ALGraph *G){ /* 初始条件: 图G存在。操作结果: 销毁图G */int i;ArcNode *p,*q;(*G).vexnum0;(*G).arcnum0;for(i0;i(*G).vexnum;i){p(*G).vertices[i].firstarc;while(p){qp-nextarc;if((*G).kind%2) /* 网 */free(p-info);free(p);pq;}}}VertexType* GetVex(ALGraph G,int v){ /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */if(vG.vexnum||v0)exit(ERROR);return G.vertices[v].data;}Status PutVex(ALGraph *G,VertexType v,VertexType value){ /* 初始条件: 图G存在,v是G中某个顶点 *//* 操作结果: 对v赋新值value */int i;iLocateVex(*G,v);if(i-1) /* v是G的顶点 */{strcpy((*G).vertices[i].data,value);return OK;}return ERROR;}int FirstAdjVex(ALGraph G,VertexType v){ /* 初始条件: 图G存在,v是G中某个顶点 *//* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */ArcNode *p;int v1;v1LocateVex(G,v); /* v1为顶点v在图G中的序号 */pG.vertices[v1].firstarc;if(p)return p-adjvex;elsereturn -1;}int NextAdjVex(ALGraph G,VertexType v,VertexType w){ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 *//* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 *//* 若w是v的最后一个邻接点,则返回-1 */ArcNode *p;int v1,w1;v1LocateVex(G,v); /* v1为顶点v在图G中的序号 */w1LocateVex(G,w); /* w1为顶点w在图G中的序号 */pG.vertices[v1].firstarc;while(pp-adjvex!w1) /* 指针p不空且所指表结点不是w */pp-nextarc;if(!p||!p-nextarc) /* 没找到w或w是最后一个邻接点 */return -1;else /* p-adjvexw */return p-nextarc-adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */}void InsertVex(ALGraph *G,VertexType v){ /* 初始条件: 图G存在,v和图中顶点有相同特征 *//* 操作结果: 在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做) */strcpy((*G).vertices[(*G).vexnum].data,v); /* 构造新顶点向量 */(*G).vertices[(*G).vexnum].firstarcNULL;(*G).vexnum; /* 图G的顶点数加1 */}Status DeleteVex(ALGraph *G,VertexType v){ /* 初始条件: 图G存在,v是G中某个顶点 *//* 操作结果: 删除G中顶点v及其相关的弧 */int i,j;ArcNode *p,*q;jLocateVex(*G,v); /* j是顶点v的序号 */if(j0) /* v不是图G的顶点 */return ERROR;p(*G).vertices[j].firstarc; /* 删除以v为出度的弧或边 */while(p){qp;pp-nextarc;if((*G).kind%2) /* 网 */free(q-info);free(q);(*G).arcnum--; /* 弧或边数减1 */}(*G).vexnum--; /* 顶点数减1 */for(ij;i(*G).vexnum;i) /* 顶点v后面的顶点前移 */(*G).vertices[i](*G).vertices[i1];for(i0;i(*G).vexnum;i) /* 删除以v为入度的弧或边且必要时修改表结点的顶点位置值 */{p(*G).vertices[i].firstarc; /* 指向第1条弧或边 */while(p) /* 有弧 */{if(p-adjvexj){if(p(*G).vertices[i].firstarc) /* 待删结点是第1个结点 */{(*G).vertices[i].firstarcp-nextarc;if((*G).kind%2) /* 网 */free(p-info);free(p);p(*G).vertices[i].firstarc;if((*G).kind2) /* 有向 */(*G).arcnum--; /* 弧或边数减1 */}else{q-nextarcp-nextarc;if((*G).kind%2) /* 网 */free(p-info);free(p);pq-nextarc;if((*G).kind2) /* 有向 */(*G).arcnum--; /* 弧或边数减1 */}}else{if(p-adjvexj)p-adjvex--; /* 修改表结点的顶点位置值(序号) */qp;pp-nextarc;}}}return OK;}Status InsertArc(ALGraph *G,VertexType v,VertexType w){ /* 初始条件: 图G存在,v和w是G中两个顶点 *//* 操作结果: 在G中增添弧v,w,若G是无向的,则还增添对称弧w,v */ArcNode *p;int w1,i,j;iLocateVex(*G,v); /* 弧尾或边的序号 */jLocateVex(*G,w); /* 弧头或边的序号 */if(i0||j0)return ERROR;(*G).arcnum; /* 图G的弧或边的数目加1 */if((*G).kind%2) /* 网 */{printf(请输入弧(边)%s→%s的权值: ,v,w);scanf(%d,w1);}p(ArcNode*)malloc(sizeof(ArcNode));p-adjvexj;if((*G).kind%2) /* 网 */{p-info(int*)malloc(sizeof(int));*(p-info)w1;}elsep-infoNULL;p-nextarc(*G).vertices[i].firstarc; /* 插在表头 */(*G).vertices[i].firstarcp;if((*G).kind2) /* 无向,生成另一个表结点 */{p(ArcNode*)malloc(sizeof(ArcNode));p-adjvexi;if((*G).kind3) /* 无向网 */{p-info(int*)malloc(sizeof(int));*(p-info)w1;}elsep-infoNULL;p-nextarc(*G).vertices[j].firstarc; /* 插在表头 */(*G).vertices[j].firstarcp;}return OK;}Status DeleteArc(ALGraph *G,VertexType v,VertexType w){ /* 初始条件: 图G存在,v和w是G中两个顶点 *//* 操作结果: 在G中删除弧v,w,若G是无向的,则还删除对称弧w,v */ArcNode *p,*q;int i,j;iLocateVex(*G,v); /* i是顶点v(弧尾)的序号 */jLocateVex(*G,w); /* j是顶点w(弧头)的序号 */if(i0||j0||ij)return ERROR;p(*G).vertices[i].firstarc; /* p指向顶点v的第一条出弧 */while(pp-adjvex!j) /* p不空且所指之弧不是待删除弧v,w */{ /* p指向下一条弧 */qp;pp-nextarc;}if(pp-adjvexj) /* 找到弧v,w */{if(p(*G).vertices[i].firstarc) /* p所指是第1条弧 */(*G).vertices[i].firstarcp-nextarc; /* 指向下一条弧 */elseq-nextarcp-nextarc; /* 指向下一条弧 */if((*G).kind%2) /* 网 */free(p-info);free(p); /* 释放此结点 */(*G).arcnum--; /* 弧或边数减1 */}if((*G).kind2) /* 无向,删除对称弧w,v */{p(*G).vertices[j].firstarc; /* p指隙サ鉾的第一条出弧 */while(pp-adjvex!i) /* p不空且所指之弧不是待删除弧w,v */{ /* p指向下一条弧 */qp;pp-nextarc;}if(pp-adjvexi) /* 找到弧w,v */{if(p(*G).vertices[j].firstarc) /* p所指是第1条弧 */(*G).vertices[j].firstarcp-nextarc; /* 指向下一条弧 */elseq-nextarcp-nextarc; /* 指向下一条弧 */if((*G).kind3) /* 无向网 */free(p-info);free(p); /* 释放此结点 */}}return OK;}Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */void(*VisitFunc)(char* v); /* 函数变量(全局量) */void DFS(ALGraph G,int v){ /* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */int w;VertexType v1,w1;strcpy(v1,*GetVex(G,v));visited[v]TRUE; /* 设置访问标志为TRUE(已访问) */VisitFunc(G.vertices[v].data); /* 访问第v个顶点 */for(wFirstAdjVex(G,v1);w0;wNextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))if(!visited[w])DFS(G,w); /* 对v的尚未访问的邻接点w递归调用DFS */}void DFSTraverse(ALGraph G,void(*Visit)(char*)){ /* 对图G作深度优先遍历。算法7.4 */int v;VisitFuncVisit; /* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */for(v0;vG.vexnum;v)visited[v]FALSE; /* 访问标志数组初始化 */for(v0;vG.vexnum;v)if(!visited[v])DFS(G,v); /* 对尚未访问的顶点调用DFS */printf(\n);}typedef int QElemType; /* 队列类型 */
/* c3-2.h 单链队列队列的链式存储结构 */typedef struct QNode{QElemType data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front,rear; /* 队头、队尾指针 */}LinkQueue;
/* bo3-2.c 链队列(存储结构由c3-2.h定义)的基本操作(9个) */Status InitQueue(LinkQueue *Q){ /* 构造一个空队列Q */(*Q).front(*Q).rear(QueuePtr)malloc(sizeof(QNode));if(!(*Q).front)exit(OVERFLOW);(*Q).front-nextNULL;return OK;}Status DestroyQueue(LinkQueue *Q){ /* 销毁队列Q(无论空否均可) */while((*Q).front){(*Q).rear(*Q).front-next;free((*Q).front);(*Q).front(*Q).rear;}return OK;}Status ClearQueue(LinkQueue *Q){ /* 将Q清为空队列 */QueuePtr p,q;(*Q).rear(*Q).front;p(*Q).front-next;(*Q).front-nextNULL;while(p){qp;pp-next;free(q);}return OK;}Status QueueEmpty(LinkQueue Q){ /* 若Q为空队列,则返回TRUE,否则返回FALSE */if(Q.frontQ.rear)return TRUE;elsereturn FALSE;}int QueueLength(LinkQueue Q){ /* 求队列的长度 */int i0;QueuePtr p;pQ.front;while(Q.rear!p){i;pp-next;}return i;}Status GetHead_Q(LinkQueue Q,QElemType *e) /* 避免与bo2-6.c重名 */{ /* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */QueuePtr p;if(Q.frontQ.rear)return ERROR;pQ.front-next;*ep-data;return OK;}Status EnQueue(LinkQueue *Q,QElemType e){ /* 插入元素e为Q的新的队尾元素 */QueuePtr p(QueuePtr)malloc(sizeof(QNode));if(!p) /* 存储分配失败 */exit(OVERFLOW);p-datae;p-nextNULL;(*Q).rear-nextp;(*Q).rearp;return OK;}Status DeQueue(LinkQueue *Q,QElemType *e){ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */QueuePtr p;if((*Q).front(*Q).rear)return ERROR;p(*Q).front-next;*ep-data;(*Q).front-nextp-next;if((*Q).rearp)(*Q).rear(*Q).front;free(p);return OK;}Status QueueTraverse(LinkQueue Q,void(*vi)(QElemType)){ /* 从队头到队尾依次对队列Q中每个元素调用函数vi()。一旦vi失败,则操作失败 */QueuePtr p;pQ.front-next;while(p){vi(p-data);pp-next;}printf(\n);return OK;}void BFSTraverse(ALGraph G,void(*Visit)(char*)){/*按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。算法7.6 */int v,u,w;VertexType u1,w1;LinkQueue Q;for(v0;vG.vexnum;v)visited[v]FALSE; /* 置初值 */InitQueue(Q); /* 置空的辅助队列Q */for(v0;vG.vexnum;v) /* 如果是连通图,只v0就遍历全图 */if(!visited[v]) /* v尚未访问 */{visited[v]TRUE;Visit(G.vertices[v].data);EnQueue(Q,v); /* v入队列 */while(!QueueEmpty(Q)) /* 队列不空 */{DeQueue(Q,u); /* 队头元素出队并置为u */strcpy(u1,*GetVex(G,u));for(wFirstAdjVex(G,u1);w0;wNextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))if(!visited[w]) /* w为u的尚未访问的邻接顶点 */{visited[w]TRUE;Visit(G.vertices[w].data);EnQueue(Q,w); /* w入队 */}}}printf(\n);}void Display(ALGraph G){ /* 输出图的邻接矩阵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(i0;iG.vexnum;i)printf(%s ,G.vertices[i].data);printf(\n%d条弧(边):\n,G.arcnum);for(i0;iG.vexnum;i){pG.vertices[i].firstarc;while(p){if(G.kind1) /* 有向 */{printf(%s→%s ,G.vertices[i].data,G.vertices[p-adjvex].data);if(G.kindDN) /* 网 */printf(:%d ,*(p-info));}else /* 无向(避免输出两次) */{if(ip-adjvex){printf(%s%s ,G.vertices[i].data,G.vertices[p-adjvex].data);if(G.kindAN) /* 网 */printf(:%d ,*(p-info));}}pp-nextarc;}printf(\n);}}int ve[MAX_VERTEX_NUM]; /* 全局变量(用于算法7.13和算法7.14) */void FindInDegree(ALGraph G,int indegree[]){ /* 求顶点的入度算法7.12、7.13调用 */int i;ArcNode *p;for(i0;iG.vexnum;i)indegree[i]0; /* 赋初值 */for(i0;iG.vexnum;i){pG.vertices[i].firstarc;while(p){indegree[p-adjvex];pp-nextarc;}}}typedef int SElemType; /* 栈类型 */#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */#define STACKINCREMENT 2 /* 存储空间分配增量 */typedef struct SqStack{SElemType *base; /* 在栈构造之前和销毁之后base的值为NULL */SElemType *top; /* 栈顶指针 */int stacksize; /* 当前已分配的存储空间以元素为单位 */}SqStack; /* 顺序栈 *//* 顺序栈的基本操作9个 */Status InitStack(SqStack *S){ /* 构造一个空栈S */(*S).base(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW); /* 存储分配失败 */(*S).top(*S).base;(*S).stacksizeSTACK_INIT_SIZE;return OK;}Status DestroyStack(SqStack *S){ /* 销毁栈SS不再存在 */free((*S).base);(*S).baseNULL;(*S).topNULL;(*S).stacksize0;return OK;}Status ClearStack(SqStack *S){ /* 把S置为空栈 */(*S).top(*S).base;return OK;}Status StackEmpty(SqStack S){ /* 若栈S为空栈则返回TRUE否则返回FALSE */if(S.topS.base)return TRUE;elsereturn FALSE;}int StackLength(SqStack S){ /* 返回S的元素个数即栈的长度 */return S.top-S.base;}Status GetTop(SqStack S,SElemType *e){ /* 若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR */if(S.topS.base){*e*(S.top-1);return OK;}elsereturn ERROR;}Status Push(SqStack *S,SElemType e){ /* 插入元素e为新的栈顶元素 */if((*S).top-(*S).base(*S).stacksize) /* 栈满追加存储空间 */{(*S).base(SElemType *)realloc((*S).base,((*S).stacksizeSTACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW); /* 存储分配失败 */(*S).top(*S).base(*S).stacksize;(*S).stacksizeSTACKINCREMENT;}*((*S).top)e;return OK;}Status Pop(SqStack *S,SElemType *e){ /* 若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR */if((*S).top(*S).base)return ERROR;*e*--(*S).top;return OK;}Status StackTraverse(SqStack S,Status(*visit)(SElemType)){ /* 从栈底到栈顶依次对栈中每个元素调用函数visit()。 *//* 一旦visit()失败则操作失败 */while(S.topS.base)visit(*S.base);printf(\n);return OK;}Status TopologicalOrder(ALGraph G,SqStack *T){ /* 算法7.13 有向网G采用邻接表存储结构,求各顶点事件的最早发生时间ve *//* (全局变量)。T为拓扑序列顶点栈,S为零入度顶点栈。若G无回路,则用栈T *//* 返回G的一个拓扑序列,且函数值为OK,否则为ERROR */int j,k,count,indegree[MAX_VERTEX_NUM];SqStack S;ArcNode *p;FindInDegree(G,indegree);/*对各顶点求入度indegree[0..vernum-1] */InitStack(S); /* 初始化栈 */for(j0;jG.vexnum;j) /* 建零入度顶点栈S */if(!indegree[j])Push(S,j); /* 入度为0者进栈 */InitStack(T); /* 初始化拓扑序列顶点栈 */count0; /* 对输出顶点计数 */for(j0;jG.vexnum;j) /* 初始化ve[]0 (最小值) */ve[j]0;while(!StackEmpty(S)){ /* 栈不空 */Pop(S,j);Push(T,j); /* j号顶点入T栈并计数 */count;for(pG.vertices[j].firstarc;p;pp-nextarc){ /* 对j号顶点的每个邻接点的入度减1 */kp-adjvex;if(--indegree[k]0) /* 若入度减为0,则入栈 */Push(S,k);if(ve[j]*(p-info)ve[k])ve[k]ve[j]*(p-info);}}if(countG.vexnum){printf(此有向网有回路\n);return ERROR;}elsereturn OK;}Status CriticalPath(ALGraph G){ /* 算法7.14 G为有向网,输出G的各项关键活动 */int vl[MAX_VERTEX_NUM];SqStack T;int i,j,k,ee,el;ArcNode *p;char dut,tag;if(!TopologicalOrder(G,T)) /* 产生有向环 */return ERROR;jve[0];for(i1;iG.vexnum;i) /* jMax(ve[]) 完成点的值 */if(ve[i]j)jve[i];for(i0;iG.vexnum;i) /* 初始化顶点事件的最迟发生时间(最大值) */vl[i]j; /* 完成点的最早发生时间 */while(!StackEmpty(T)) /* 按拓扑逆序求各顶点的vl值 */for(Pop(T,j),pG.vertices[j].firstarc;p;pp-nextarc){kp-adjvex;dut*(p-info); /* dutj,k */if(vl[k]-dutvl[j])vl[j]vl[k]-dut;}printf( j k dut ee el tag\n);for(j0;jG.vexnum;j) /* 求ee,el和关键活动 */for(pG.vertices[j].firstarc;p;pp-nextarc){kp-adjvex;dut*(p-info);eeve[j];elvl[k]-dut;tag(eeel)?*: ;printf(%2d %2d %3d %3d %3d %c\n,j,k,dut,ee,el,tag); /* 输出关键活动 */}printf(关键活动为:\n);for(j0;jG.vexnum;j) /* 同上 */for(pG.vertices[j].firstarc;p;pp-nextarc){kp-adjvex;dut*(p-info);if(ve[j]vl[k]-dut)printf(%s→%s\n,G.vertices[j].data,G.vertices[k].data); /* 输出关键活动 */}return OK;}void main(){ALGraph h;printf(请选择有向网\n);CreateGraph(h);Display(h);CriticalPath(h);}算法时间复杂度O(ne);
