数据结构 |
您所在的位置：网站首页 › aov和aoe网分别是什么 › 数据结构 |
数据结构
|
1.基本概念：
AOV网：用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网络（Activity On Vertex Network）,简称AOV-网。 AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网（Activity On Edge Network） {路径长度：路径上各个活动所持续的时间之和 关键路径：从源点到汇点具有最大长度的路径 关键活动：在关键路径上的活动} 拓扑排序：对一个有向图构造拓扑序列的过程。 关键路径：由于在AOE网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径叫做关键路径。 2.算法实现思路 拓扑排序从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入读为0的顶点为止。 （拓扑排序的过程中，需要删除顶点，显然用邻接表会更加方便。考虑到算法过程中始终要查找入度为0的顶点，因此我们设置一个indegree数组，用来存放各顶点的入度数目。） 拓扑排序主要是为解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最短时间问题。我们如果要对一个流程图获得最短时间，就必须要分析它们的拓扑关系，并且找到当中最关键的流程。这个流程的时间就是最短时间。 一个活动的最早开始时间= 最晚开始时间，则该活动是关键活动，活动间的路径是关键路径。 拓扑排序 #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define TRUE 1 #define FALSE 0 #define STACK_INIT_SIZE 10 #define STACKINCREMENT 2 #define MAX_VERTEX_SIZE 20 #define INFINITY INT_MAX typedef int Status; typedef int InfoType; typedef int VertexType; typedef int VRType; typedef enum {DG,DN,UDG,UDN} GraphKind; typedef int SElemType; typedef struct { SElemType *base,*top; int stacksize; }SqStack; typedef struct ArcNode { VRType adjvex; int weight; struct ArcNode *next; }ArcNode; typedef struct VNode { VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_SIZE]; typedef struct { int vexnum,arcnum; AdjList vertices; GraphKind kind; }ALGraph; Status InitStack(SqStack *S); Status DestroyStack(SqStack *S); Status Push(SqStack *S, SElemType e); Status Pop(SqStack *S, SElemType *e); Status StackEmpty(SqStack S); Status CreateGraph(ALGraph *G){ ArcNode *p,*q; VNode v1,v2; int i,j,sign1,sign2; (*G).kind = DG; printf("有向图\n"); printf("请输入顶点数，弧的数\n"); scanf("%d%d",&(*G).vexnum,&(*G).arcnum); printf("请初始化顶点\n"); for(i = 0; i < (*G).vexnum; ++i){ scanf("%d",&(*G).vertices[i].data); (*G).vertices[i].firstarc = NULL; } printf("请初始化弧\n"); |
【本文地址】
今日新闻 |
推荐新闻 |