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;
}