【数据结构】有向无环图描述表达式、拓扑排序

1. 有向无环图描述表达式

1. 有向无环图

若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）。

2. DAG描述表达式

方法步骤：

Step1：把每个操作数不重复地排成一排。

Step2：标出各个运算符的生效顺序（先后顺序可能不一样无所谓）。

Step3：按顺序加入运算符，注意“分层”。

Step4：从底向上逐层检查同层的运算符是否可以合体。

2. 拓扑排序

AOV网（Activity On Vertex NetWork，用顶点表示活动的网）；用DAG图（有向无环图）表示一个工程。顶点表示活动，有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行。

1. 拓扑排序的定义

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序：

1. 每个顶点出现且只出现一次。
2. 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序。

2. 拓扑排序的实现

1. 从AOV网中选择一个没有前驱（入度为0）的顶点并输出。
2. 从网中删除该顶点和所有以它为起点的有向边。
3. 重复1和2知道当前的AOV网为空或当前网中不存在无前驱的顶点为止。

注意：当前网中不存在无前驱的顶点，说明没有顶点的入度为0，说明有回路。

3. 代码实现

#define MaxVertexNum 100  // 图中顶点数目的最大值
typedef struct ArcNode{  // 边表结点
    int adjvex;  // 该弧所指向的顶点的位置
    struct ArcNode *nextarc;  // 指向下一条弧的指针
    // InfoType info;  // 网的边权值
}ArcNode;

typedef struct VNode{  // 顶点表结点
    VertexType data;  // 顶点信息
    ArcNode *firstarc;  // 指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];

typedef struct{
    AdjList vertices;  // 邻接表
    int vexnum,arcnum;  // 图的顶点树和弧数
}Graph;  // Graph是以邻接表存储的图类型

bool TopologicalSort(Graph G){
    InitStack(S);  // 初始化栈，存储入度为0的顶点
    for(int i=0;i<G.vexnum;i++){
        if(indegree[i]==0){
            Push(S,i);  // 将所有入度为0的顶点进栈
        }
    }
    int count=0;  // 计数，记录当前已经输出的顶点数
    while(!IsEmpty(S)){
        Pop(S,i);  // 栈顶元素出栈
        print[count++]=i;  // 输出顶点i
        for(p=G.vertices[i].firstarc;p;p=p->nextarc){
            // 将所有i指向的顶点的入度减1，并且将入度为0的顶点压入栈S
            v=p->adjvex;
            if(!(--indegree[v])){
                Push(S,v);  // 入度为0，则入栈
            }
        }
    }
    if(count<G.vexnum){
        return false;  // 排序失败，有向图中有回路
    }else{
        return true;  // 排序成功
    }
}

4. 复杂度分析

从代码可以看出，每个顶点都需要处理一次，每条边都需要处理一次，则时间复杂度为：O(|V|+|E|)。

若采用邻接矩阵，则需O(|V|^2)。

5. 逆拓扑排序

对一个AOV网，如果采用以下步骤进行排序，则称之为逆拓扑排序：

1. 从AOV网中选择一个没有后继（出度为0）的顶点并输出。
2. 从网中删除该顶点和所有以它为终点的有向边。
3. 重复1和2的步骤直到当前的AOV网为空。

6. 逆拓扑排序的实现（DFS算法）

void DFSTraverse(Graph G){
    for(v=0;v<G.vexnum;++v){
        visited[v]=false;
    }
    for(v=0;v<G.vexnum;++v){
        if(!visited[v]){
            DFS(G,v);
        }
    }
}
void DFS(Graph G,int v){  // 从顶点v出发，深度优先遍历图G
    visited[v]=true;  // 设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w)){
        if(!visited[w]){  // w为u的尚未
            DFS(G,w);
        }
    } 
    print(v);  // 输出顶点  DFS实现逆拓扑排序，在顶点退栈前输出
}

说明：DFS实现逆拓扑排序，在顶点退栈前输出。

3. 小结