5.4图的综合应用——DAG,AOV,AOE
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
5.3 DAG图的相关使用
DAG(Direct Acyclic Grpah)
应用有向无环图——>描述表达式——注意可以减少重复变量精简生成树
5.4 拓扑排序相关使用
AOV网Activity On Vertex NetWork顶点表示活动的网
DAG图有向无环图——>AOV网用顶点表示活动的网更真实的系统图表示更抽象的数学系统
时间复杂度O(V+E)遍历顶点集和边集用邻接表的结构存储图
排序方法
从AOV网选取一个没有前驱的顶点并输出
删除该顶点和它为起点的有向边
一直重复
1.拓扑排序结构体
弧针对于有向图
相关的细节理解不清楚
#define MaxVertexNum 100 //顶点数Vertex
typedef struct ArcNode{//边表节点
int adjvex;//弧指向顶点的位置应该是入度位置
struct ArcNode *nextarc;//指向下一条弧的指针
//InfoType info; //网的边权值
}ArcNode;
typedef struct VNode{//顶点表结点
VertexType data;//顶点信息
ArcNode *firsrarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjLisit[MaxVertexNum];
//图的信息表
typedef struct{
AdjList vertices;//省略邻接表的结构体定义
int vexnum,arcnum; //图的顶点数与弧数
}Graph;
2.拓扑排序方法体
//拓扑排序
bool TopologicalSort(Graph G)
{
InitStack(S); //初始化栈
for (int i = 0; i < G.vexnum; i++)
{
if (indegree[i] == 0) //记录顶点的入度
Push(S, i);
}
int count = 0;
while (!IsEmpty(S))
{
Pop(S, i);
print[count++] = i; //记录顶点的拓扑序列
for (p = G.vertices[i].firstarc; p; p = p->nextarc)
{
//将所有i指向的顶点入度减1并将入度减少为0的顶点压入栈S
v = p->adjvex;
if (!(--indegree[v]))
Push(S, v);
}
}
if (count < G.vexnum) //判断拓扑排序是否成功
return false;
else
return true;
}
3.DFS实现拓扑与逆拓扑排序
5.5AOE网在关键路径中的使用Activity On Edge NetWork
DAG——>AOV——>AOE
DAG图 描述表达式减少重复)
有向无环图
AOV网 顶点表示活动拓扑排序
顶点表示活动网
AOE网顶点表示事件边表示活动图关键路径
顶点表示事件边表示活动图边上权值表示开销用边表示活动的网络
特征
源点汇点关键路径关键活动
求解关键路径步骤
1.拓扑排序事件最早发生时间 ve()
2.逆拓扑排序事件最迟发生时间 vl()
3.e()活动最早发生时间 借助 ve()
4.l()活动最迟发生时间 借助el()
5.所有活动的时间余量 d()
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |