图：有向无环图（DAG）（应用：拓扑，逆拓扑排序）

1.有向无环图的定义

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

顶点中不可能出现重复的操作数。

2.算数表达式

用有向无环图描述算术表达式。

解题步骤：

1. 把各个操作数不重复地排成一排。
2. 标出各个运算符的生效顺序（先后顺序有点出入无所谓)
3. 按顺序加入运算符，注意“分层”（同级的运算为同一层）
4. Step 4:从底向上逐层检查同层的运算符是否可以合体：如果同一层的左右子树一致，则合并为一个子树。

使用有向无环图存储一个表达式，图的最终形态是不唯一的。

案例：

3.拓扑排序

1.AOV网的概念

作用是记录活动的先后顺序的图。

AOV网( Activity on Vertex Network，用顶点表示活动的网):
用DAG图(有向无环图）表示一个工程。
顶点表示活动，有向边<V1,V2>表示活动V1必须先于活动V2进行。

2.拓扑排序的实现

所谓的拓扑排序就是描述做事的先后顺序。

将AOV网的顶点遍历的过程就是拓扑排序的实现步骤：

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

值得注意的是，存在回路的图是不存在拓扑排序的。

3.代码实现

流程图：

#define MaxVertexNum 100//图中顶点数目的最大值

typedef struct ArcNode {//边表结点
    int adjvex;//该弧所指向的顶点的位置
    struct ArcNode *nextarc;//指向下一条弧的指针
    // / l 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);//初始化栈，存储入度为o的顶点
    for (int i = 0; i < G.vexnum; i++)
        if (indegree[i] == 0)
            push(S, i);//将所有入度为0的顶点进栈
    int count = 0;//计数，记录当前已经输出的顶点数
    while (!IsEmpty(S)) {//栈不空，则存在入度为o的顶点
        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;//拓扑排序成功

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

4.性能分析

• 时间复杂度：若采用邻接表存储图，为O(|V|+|E|)，若采用邻接矩阵，则需O(IV|²).

4.逆拓扑排序

1.实现步骤

对一个AOV网逆拓扑排序:

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

逆拓扑排序的代码实现是计算出度，和拓扑排序（计算入度）正好相反。

2.存储结构的选择

• 使用邻接表实现逆拓扑排序每一轮都需要遍历所有元素。
• 而使用邻接矩阵来实现逆拓扑排序，只需要遍历当前元素所在列即可找到出度，时间上要更高效一些。
• 或者使用逆邻接表存储元素，会更为方便的找到元素。

所谓逆邻接表：就把所有指向当前元素的元素连在一起，与邻接表记录出度刚好相反。

值得一提的是，拓扑排序、逆拓扑排序序列可能不唯一。

5.使用DFS算法（深度优先遍历）实现逆拓扑排序

代码实现：

void DFSTraverse(Graph G) {//对图G进行深度优先遍历
    for (v = 0; v < G.vexnum; ++v)
        visited[v] = FALSE;//初始化已访问标记数据
    for (v = 0; v < G.vexnum; ++v)//本代码中是从v=0开始遍历
        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); //输出顶点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16