软件设计师 - 第3章数据结构

概述

按照存储结构来分，数据结构可以分成如下四种：

线性结构：数据元素间呈现线性关系，有单一的前驱和后继
表：可以看做是线性结构的推广，是多个线性结构的集合
树：不同于线性结构，其元素可以有多个直接后继
图：不同于线性结构和树，其元素可以有多个直接前驱和后继

线性结构

线性表

线性表是n个元素的有序序列，非空线性表有如下特点：

存在唯一的第一个元素
存在唯一的最后一个元素
除第一个元素外其余元素都有且只有一个前驱
除最后一个元素外其余元素都有且只有一个后继

线性表的存储方式有两种：顺序存储、链式存储。

顺序存储

采用顺序存储时，就是平常使用的一维数组，可通过数组的索引直接访问对应元素，但进行插入和删除操作时会麻烦些。

// 声明一个固定长度为8，采用顺序存储的线性表 —— 数组
int array[8];
for (int i = 0; i < 8; i++) {array[i] = i;
}

访问操作

对于采用顺序存储的线性表，若要访问位置n处的数据，只需使用下表即可，效率高。

// 访问位置5处的数据
int result = array[5];

插入操作

对于采用顺序存储的固定长度的线性表，若所有位置均被使用，此时若要在位置n处插入新的数据需要重新申请一块空间，将原空间中前n-1个元素复制到新空间，在n处填入新数据，将原空间中n处及其后的数据复制到n+1处及其后；若原空间有剩余位置未被使用，只需将n处及其后的数据“后移”，在n处填入新数据即可。

可见对于顺序存储的结构进行插入操作时需要进行大量的“移位”操作，效率低。

// 在位置5处插入数据6
int array2[9];
for (int i = 0; i < 5; i++) {array2[i] = array[i];
}
array2[5] = 6;
for (int i = 6; i < 9; i++) {array2[i] = array[i - 1];
}

删除操作

对于采用顺序存储的线性表，若要删除位置n处的数据，需要将n+1及其后的数据“前移”。

可见对于顺序存储的结构进行删除操作时需要进行大量的“移位”操作，效率低。

// 删除位置5处数据
for (int i = 5; i < 8 - 1; i++) {array[i] = array[i + 1];
}
array[7] = -1;

链式存储

采用链式存储是，除了需要存储数据数据外还需要存后继/前驱节点指针，当节点信息中只存一种（前驱或后继）指针时称为单向链表，两者都存时称为双向链表。单向链表中最后节点的后继指向第一个节点时形成的链表称为循环链表，同理，单向链表中第一个节点的前驱指向最后节点时形成的链表称为循环链表，双向链表中第一个节点的前驱指向最后节点、最后节点的后继指向第一个节点时形成的链表称为循环链表。还有一种特殊的链表，其利用顺序储存方式存储指向数据的指针，该结构称为静态链表。采用链式存储是访问特定位置元素需要从头开始遍历，效率低，但删除/删除操作效率比顺序存储高。

// 定义链式存储中节点结构
typedef struct node {int data;struct node *next;
} NODE, *LinkList;// 声明一个采用链式存储的线性表
LinkList head = NULL, tail = NULL;
for (int i = 0; i < 8; i++) {NODE* newNode = (NODE*)malloc(sizeof(NODE));if (newNode == NULL) {printf("Memory allocation failed\n");exit(1);}newNode->data = i;newNode->next = NULL;if (head == NULL) {head = newNode;} else {tail->next = newNode;}tail = newNode;    
}

访问操作

对于采用链式存储的线性表，若要访问位置n处的数据，需要从头开始遍历，直到遍历到位置n为止，效率低。

NODE* getNode(int index) {NODE *node = head;for (int i = 0; i < 5; i++) {if (node != NULL) {node = node->next;} else {return node;}}return node;
}// 访问位置5处的数据
NODE* node = getNode(5);
if (node == NULL) {printf("Linked List Index Out of Bounds\n");exit(1);
}
int result = node->data;

插入操作

对于采用链式存储的线性表，若要在位置n处插入新数据只需要修改n-1处的指针即可。

// 在位置5处插入数据6
NODE* node = getNode(5 - 1);
if (node == NULL) {printf("Linked List Index Out of Bounds\n");exit(1);
}
NODE* newNode = (NODE*)malloc(sizeof(NODE));
if (newNode == NULL) {printf("Memory allocation failed\n");exit(1);
}
newNode->data = 6;
newNode->next = node->next;
node->next = newNode;

删除操作

对于采用链式存储的线性表，若要删除位置n处数据只需要修改n-1处的指针即可。

// 删除位置5处数据
NODE* node = getNode(5 - 1);
if (node == NULL) {printf("Linked List Index Out of Bounds\n");exit(1);
}
if (node->next != null) {NODE* temp = node->next;node->next = temp->next;free(temp);
}

栈

栈是一种线性结构，只能访问一端，修改栈内数据时只能是后进先出（Last In First Out, LIFO），栈的一端称为栈顶，另一端称为栈底，没有数据时称为空栈。一般支持如下运算：

初始化：创建一个空栈
判空：判断栈是否为空栈
入栈：将数据放入栈顶，更新栈顶指针
出栈：将栈顶数据删除，更新栈顶指针
读栈顶数据：只读栈顶数据，不删除，不更新栈顶指针

栈的应用场景有很多，常见的如下：

表达式求值
括号匹配

队列

队列是一种线性结构，是一种先进先出（First In First Out, FIFO）的结构，只允许在一端插入数据，该端称为对尾，在另一端删除数据，该端称为对头。一般支持如下运算：

初始化：创建一个空队列
判空：判断队列是否为空栈
入队：将数据放入队尾，更新队尾指针
出对：将对头数据删除，更新对头指针
读对头数据：只读对头数据，不删除，不更新对头指针

队列的应用场景有很多，常见的如下：

任务队列
消息队列

当队列采用顺序存储时会有些问题，下面举例说明

// 使用数组模拟队里，此时队列为空
int array[8];
int *front = array;
int *rear = array;
// 连续队列5个数据
for (int i = 0; i < 5; i++) {*rear = i;rear = rear + 1;
}
// 连续出队4个数据
for (int i = 0; i < 4; i++) {*front = -1;front = front + 1;
}
// 此时队列中只有一个元素，但此时队尾只能添加3个元素

由于上述问题的存在，所有在使用顺序结构作为队列时使用了循环队列的概念，即队尾逻辑上下一个元素是队头，此时便可利用出队的空间。

#define SIZE 8int array[SIZE];
int *front = array;
int *rear = array;
// 记录队列中的元素数量
int count = 0;// 判断队列是否满，只有在限制队列长度时才需要判断，比如本例中队列长度为8
bool isFull() {return count == SIZE;
}// 判断队列是否为空，此时front与rear指向同一个位置
bool isEmpty() {return count == 0;
}// 入队
void enqueue(int value) {if (isFull()) {printf("Queue is full\n");return;}*rear = value;// 如此时rear已经是顺序结构的最后一个元素，则指向第一个元素rear = (rear == array + SIZE - 1) ? array : rear + 1;count++;
}// 出队
void dequeue() {if (isEmpty()) {printf("Queue is empty\n");return;}// 如此时front已经是顺序结构的最后一个元素，则指向第一个元素front = (front == array + SIZE - 1) ? array : front + 1;count--;
}

串

是一种特殊的线性表，数据元素是字符，有几个概念：空串，空格串，子串，串相等，串比较等，有如下几个基本操作：

赋值操作
连接操作
求长度操作
串比较操作
求子串操作

子串的定位操作通常称为串的模式匹配，子串也称模式串。

朴素的模式匹配算法

该算法也称布鲁特-福斯算法，基本思想是从主串的第一个字符开始匹配子串，若相同则匹配下一个字符，完全匹配成功则返回，否则从主串的第二个字符还是匹配，……。

主串长度n，匹配串长度m。最好情况匹配成功实践复杂度O(n+m)，最坏情况的时间复杂度O(n*m)。

改进的模式匹配算法

改进的模式匹配算法又称KMP算法。待补充

表

表可认为是线性表在维度上的扩展，也可认为表是线性表，只不过其元素也是线性表。

数组

数组要求其内元素的数据结构相同，数组可以是多维的，例如1维是“线”结构，2维是“面”结构，3维是“体”结构，……。数据可根据给定的下标直接操作对应的数据元素，完成对数据元素的取值或修改操作，数组结构的特点如下：

数据元素数据固定，如要新增或删除元素实际上需要新数组来完成操作
数据元素具有相同的类型
数据元素下表关系具有上下界的约束其有序

对于数组我们一般讨论2维，一般采用顺序存储方式，可采用以行为主序和以列为主序两种。以行为主序就是按照行的顺序存储数据，以列为主序就是按照列的顺序存储数据。以一个n*m的2维数组A为例，以行为主序的存储顺序是(a11, a12, a13, ..., a1m, a21, a22, a23, .., a2m, ..., an1, an2, an3, ..., anm(。以列为主序的存储顺序是(a11, a21, a31, ..., an1, a12, a22, a32, ..., an2, ..., a1m, a2m, a3m, ..., anm)。

矩阵

矩阵可以看做2维数组，但矩阵有其独特的概念，例如为了节省存储空间而提出的一些概念矩阵，如特殊矩阵，稀疏矩阵等。

特殊矩阵

若在矩阵中元素（或非0元素）的分布有一定的规律，常见的特殊矩阵有对称矩阵，三角矩阵，对角矩阵等。对于这些特殊矩阵，可将原本2维数组压缩成1维数组。

对称矩阵：可将原本n*n的矩阵数据存储到有着n*(n+1)/2个元素空间的1维度数组中。
三角矩阵：
对角矩阵：可将原本n*n的矩阵数据存储到有着 t*n - (t^2-1)/4个元素空间的1维度数组中，t表示对角线个数。

稀疏矩阵

矩阵中若非0元素个数远远少于0元素个数，且非0元素分布没有规律，则该矩阵称为稀疏矩阵。可使用一个三元组存储矩阵中没有元素信息，(i, j, aij)，i, j存储行列信息，aij存储元素值。存储稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，链式存储结构称为十字链表。

广义表

广义表是线性表的推广，是由0个或多个元素或子表组成的有限序列。线性表中元素都是结构上不可分割的元素，广义表中元素可以是单元素，也可以是有结构的表。其中元素称为原子，内部的表称为子表。广义表的长度指的数表中元素个数，广义表的深度指的是表内嵌套表的层数。下面介绍两个概念：

表头：非空广义表中第一个元素称为表头，可以是原子，可可以是子表
表尾：非空广义表中除表头之外元素构成的表

广义表的特点如下：

广义表可以是多层次结构，即广义表中子表中继续存放子表
广义表可以共享其他子表，即某个子表被多个广义表使用
广义表可以递归定义，即广义表中子表可以是其本身

广义表本身是一种带有层次的非线性结构，因此难以使用顺序存储结构，通常采用链式存储结构，结点分成表结点和元素节点，表结点中有3个信息：表示其是表结点的tag=1信息，指向表头的指针，指向表尾的指针，元素节点中有2个信息：表示其是元素结点的tag=0信息，元素值信息。

树

树结构是一种常见的数据结构，也是非常重要的数据结构，其数据元素可以后两个或两个以上的直接后继元素。树的定义是递归的，即树中存在唯一一个根节点，根节点的直接后继是另一棵树（子树）的根节点，也可以认为树是由根节点及其子树构成。树中的节点有如下一些概念：

“双亲”：说是双亲，其实指的是节点的直接前驱，是一个节点，树中除根外都有“双亲”
孩子：指的是节点的直接后继，是其所有子树的根
兄弟：指的是其“双亲”的直接后继节点除了本身
节点的度：指的是节点的子树个数
叶子节点：也称终端节点，度为0的节点
分支节点：也称非终端节点，指的是度不为0的节点
内部节点：除根节点外的分支节点
节点的层次：根为第1层，其子树的根为第2层，以此类推
树的高度：树的最大层数
有序/无序树：节点的左右子树是有次序的

二叉树

二叉树也是一种树，其满足树的定义，但在二叉树中节点最多有两个子树，这两个子树分别称为左、右子树，即使节点只有一个子树，该子树也需要注明其是左或右。二叉树有如下特性：

二叉树的第i层上最多有2^(i-1)个节点，i>0
高度为k的二叉树最多有2^k-1个节点，k>0
二叉树的终端节点（叶子节点）数量是度为2节点数量+1
具有n个节点的完全二叉树深度是log2n取下界+1

在二叉树中还有一些特殊的二叉树，如下：

满二叉树：深度为k的二叉树节点有2^k-1个，该树中除叶子节点外没有节点都有两个子节点，且所有叶子节点都在同一层
完全二叉树：相比于满二叉树，完全二叉树可能缺少最后若干个叶子节点，满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树
非完全二叉树：相比于满二叉树，非完全二叉树缺少的节点一定非最后若干个叶子节点

二叉树存储结构

树是非线性结构，推荐采用链式存储方法，但依然可以使用顺序存放方式，如完全二叉树就适合使用顺序存储。对于完全二叉树可以使用树的节点树来申请顺序空间，但对于其他二叉树需要申请2^k-1个空间才可以。

顺序存储：若树中有n个节点，对于节点i
- 若i=0，则其是根节点
- 若i>1，则其双亲是i/2取下界
- 若2i<=n，则其左孩子是2i，否则无左孩子
- 若2i+1<=n，则其左孩子是2i+1，否则无右孩子
链式存储：可使用三叉链表或二叉链表
- 节点包好数据域，左孩子指针域，右孩子指针域
- 左孩子指针域指向左子树的根
- 右孩子指针域指向右孩子的根
- 数据域存储数据信息，或者数据域也是指针域，指向数据节点

typedef struct Node {int data;struct Node *lchild;struct Node *rchild;
} Node, *Tree;

二叉树遍历

二叉树的遍历是指遍历二叉树的方法，按照先遍历左子树后遍历右子树的约定，可根据访问根节点位置的不同分为：先序遍历，中序遍历，后序遍历。

// 先序写法
void PreOrder(Tree root) {if (root != NULL) {printf("%d\n", root->data);PreOrder(root->lchild);PreOrder(root->rchild);}
}// 中序写法
void InOrder(Tree root) {if (root != NULL) {InOrder(root->lchild);printf("%d\n", root->data);InOrder(root->rchild);}
}// 后序写法
void PostOrder(Tree root) {if (root != NULL) {PostOrder(root->lchild);PostOrder(root->rchild);printf("%d\n", root->data);}
}

通过分析上面的三种遍历方法可知，除了打印语句位置不同，其余逻辑都是相同的，说明这三种遍历方式遍历的路线相同，处理叶子节点的逻辑也相同，只不过处理分支节点逻辑不同：

先序遍历：在读到分支节点后立即输出
中序遍历：在读到分支节点后先处理左子树，再输出，可认为是“第2次”遍历时输出
后续遍历：在读到分支节点后先处理左子树，再处理右子树，最后输出，可认为是“第3次”遍历时输出

无论是递归方式遍历树还是非递归方式遍历树，其本质都是使用了栈。递归方式通过函数调用的方式将函数入栈，同时函数访问的节点也入栈，非递归方式通过遍历节点主动将节点入栈出栈来实现。递归方式实现简单，但会有大量的函数入栈出栈操作，影响性能。非递归方式实现稍麻烦一些，但性能较好。下面介绍下非递归方式实现的中序遍历。

int InOrder(Trre root) {Tree p;Node *q;InitStack(St); // 初始化栈p = root;while (p != NULL || !IsEmpty(St)) {if (p != NULL) {Push(St, p); // 入栈p = p->lchild;} else {q = Pop(St); // 出栈printf("%d\n", q->data);p = q->rchild;}}
}

除了上面说的3种遍历方式外还有层次遍历，即一层一层遍历节点。

void LevelOrder(Tree root) {Tree p;InitQueue(Q); // 初始化队列EnQueue(Q, root); // 入队while (!IsEmpty(Q)) {DeQueue(Q, p); // 出队printf("%d\n", p->data);if (p->lchild) EnQueue(Q, p->lchild);if (p->rchild) EnQueue(Q, p->rchild);}
}

线索二叉树

无论使用哪种遍历方式遍历特定树都会得到与之对应的唯一的一个顺序，在该顺序中节点存在唯一直接前驱和直接后继，这些信息不存在于树中，只有在按照某种顺序遍历时才能得到。所以有没有某种办法直接在树中加入这些直接前驱与后续节点信息呢，于是线索二叉树应运而生。由于一棵n个节点的二叉树中必然会有n+1个空指针域，这些域原本是要指向节点的左/右子树的，但由于节点的限制，所以只能填空。可以利用这些空指针域，另外增加两个字段标识指针域的含义。

typedef struct Node {short ltag;short rtag;int data;struct Node *lchild;struct Node *rchild;
} Node, *Tree;

由上述节点构成的链表称为线索链表，采用该链表存储的二叉树称为线索二叉树，其中ltag/rtag的取值不同表示lchild/rchild指向不同：

ltag=0：lchild指向左孩子
ltag=1：lchild指向直接前驱
rtag=0：rchild指向右孩子
rtag=1：rchild指向直接后继

怎样建立这样的线索二叉树：

首先需要确定遍历方式
使用指针p指向正在访问的节点
使用指针pre指向前一个访问的节点
若p指向的节点有空指针域，则将ltag/rtag标记为1
若pre!=NULL，且pre指向的节点rtag=1，令pre->rchild=p
若p指向的节点ltag=1，令p->lchild=pre
使pre=p，p指向下一个节点

上述的方式建立的线索二叉树并不完整，还需要进一步运算来得到，下面举个例子说明。

当p->rtag=1时，p->rchild指向的节点就是其直接后续

当p-rtag=0时，p->rchild指向的节点是其右孩子节点，只有在中序遍历时右孩子节点才是其直接后继，此时还需要确认其右子树中第一个被访问的节点，该节点才是p的直接后继。

最优二叉树

最优二叉树又称哈夫曼树，是一个带权路径长度最短的树，即在给定n个带权的叶子节点后，经过排列使其所有节点的带权路径长度最短，该树就是最优二叉树。由于对同层节点的左右子树没有要求，所以得到的最优二叉树可能不唯一。每个节点的带权路径长度是其权值*其到根的长度。

$WPL = \sum_{k=1}^{n}w_{k}l_{k}$

其中w表示k节点的权值，l表示k节点到根节点的路径长度。

哈夫曼编码

在介绍哈夫曼编码前先介绍下等长编码，即所有待编码的字符都使用等长的码来编码，如26个字符，可使用5位二进制数实现等长编码。这样编码简单，但是由此来编码会导致码串过长问题，不利于提高通信效率。因此需要一个可以缩短码串长度的编码方式，但是其前提是每个待编码的字符权值不能相同，若是相同则不能保证解决上述问题。对于不等长编码要求任一字符的编码都不是另一个字符编码的前缀，否则会有译码问题。

构造哈夫曼编码树的过程如下：

从待编码集合中选择两个权值最小的节点作为底层叶子节点
得到上述两个节点“双亲”节点的权值，并将其放入待编码集合
重复步骤1,2，知道集合中仅剩一个节点，则该节点的权值就是WPL

树和森林

树的存储结构

前面介绍了二叉树的存储结构，可使用顺序存储，可使用链式存储，本次扩展到所有树，有如下几种存储结构：

树的双亲表示法：是一个具有n个节点的数组，数组中节点包含两个域，数据域和“双亲”索引域，数据域存的是节点信息，“双亲”索引域存的是“双亲”节点在本数组中的序号
树的孩子表示法：是一个具有n个节点的数组，数组中节点包含两个域，数据域和指针域，数据域存储的是节点信息，指针域指向孩子节点链表。孩子节点链表中的节点也包含两个域，数据域和指针域，数据域存储孩子节点信息，指针域指向兄弟节点。
树的双亲孩子表示法：综合上述两种表示法，是一个具有n个节点的数组，数组中节点包含三个域，数据域、“双亲”索引域和指针域。
孩子兄弟表示法：又称二叉链表表示法，链表节点中包含三个域，数据域、孩子节点域和兄弟节点域，孩子节点域存储的是第一个孩子的指针，兄弟节点域存储的是下一个兄弟的指针。该表示法可实现树、森林与二叉树之间的转换。

树和森林的遍历

由于树中节点的子节点不固定，不想二叉树那样可先序、中序、后续，普通的树遍历方式只有先根和后根。

这里在介绍下什么是森林，森林是由若干棵互不相交的树组成的集合。换句话说，森林是树的集合。将树的根节点移除，剩余的部分可能就是森林，深林也可通过一个超根节点变成一棵树。不同于树，深林的遍历方式有先序遍历和中序遍历。

树、森林与二叉树间的转化

任何一棵树或者森林都可表示为一颗二叉树，反之依然。

树转二叉树：使用树的兄弟表示法，该二叉树的根没有右子树
森林转二叉树：使用树的兄弟表示法
二叉树转树：根节点无右子树时转成树，有右子树时转成森林

图

图与线性结构，表，树的区别在于，其节点的直接前驱和直接后继没有限制，任意两个节点间都可能存在联系。

图使用符号G=(V, E)表示，其中V是图中定点的非空有限集合，E是图中的边有限集合。下面围绕图介绍几个概念：

有向图：E中的边是有方向的，使用<vi, vj>表示从vi到vj存在一条边（或称弧），vi是有向边的起点，称为弧尾，vj是有向边的终点，称为弧头，所有边都是有向的图称为有向图。
无向图：边是无向的<vi, vj>表示vi与vj间存在一条边。
完全图：对于有向图，任意两点作为起终点都存在有向边；对于无向图，任意两点间都存在无向边。
度、出度和入度：度指的是与该节点关联的边数量，记作D(v)。对于有向图，还有出度和入度的概念，入度是指以该节点作为终点的又向边的数量，记作ID(v)，出度是指以该节点作为起点的又向边的数量，记作OD(v)，度=入度+出度。
路径：沿着有向边的方向/无向边可从节点vp走到vq
子图：G1=(V1, E1)，如果V1<=V且E1<=E，则称G1是G的子图
连通图和连通分量：对于无向图中，若节点vi和vj间存在路径，则认为vi和vj是连通的，若图中任意两点都是连通的，则该图是连通图，无向图G的极大连通子图称为G的连通分量。
强连通图和强连通分量：对于有向图，任意两个节点间都存在两条有向边，则该图是强连通图，有向图G的极大连通子图称为G的强连通分量。
网：边带权值的图称为网
有向树：有向图中只有一个节点入度为0，其余节点入度为1

图的存储结构

图的存储结构有：

邻接矩阵：将具有n节点的图使用n*n的矩阵表示，若<vi, vj>存在弧，则(i, j)值为1，否则值为0

邻接链表：将具有n节点的图使用长度为n数组存储，数组中元素有三个域，分别存储节点序号，节点信息，指向与节点连接的那些节点形成的链表，链表中元素有两个域，分别存储节点序号，下一个节点指针。有从弧尾出发的邻接链表就会有从弧头出发的邻接链表，称为逆邻接表。

图的遍历

图的遍历是指从某个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且只访问一次的过程。图的遍历算法是求解图的连通性问题、拓扑排序及求关键路径等算法的基础。

深度优先搜索 Depth First Search DFS

设置搜索指针p，使p指向顶点v。
访问p所指顶点，并使p指向与其相邻接的且尚未被访问过的顶点。
若p所指顶点存在，则重复步骤2，否则执行步骤4。
沿着刚才访问的次序和方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使p指向这个未被访问的顶点,然后重复步骤2，直到所有的顶点均被访问为止。

广度优先搜索 Breadth First Search BFS

将v入队
出队后，遍历其邻接节点并入队
若队列不为空，执行步骤2，若为空则执行步骤4
将未被访问的节点入队，执行步骤2，3知道所有节点都被访问且队列为空

生成树及最小生成树

连通图的生成树是该图的极小连通子图，若在生成树中增加任意一条边则必然形成回路。生成树不是唯一的，从不同的顶点出发，不同的存储方式，不同的求解方法，都可以得到不同的生成树。非连通图可创建生成树森林。按照深度优先和广度优先得到的生成树分别称为深度优先生成树和广度优先生成树。

若图中的弧带有权值，不同的生成树就有不同的权，把权值最小的生成树称为最小生成树。

普利姆算法 Prim

待补充

克鲁苏卡尔算法 Kruskal

待补充

拓扑排序和关键路径

以顶点表示活动的网 Activity On Vertex network AOV

以顶点表示活动，有向边是活动依赖或者优先级，弧尾表示高优先级或者被依赖的活动。AOV网中不会出现循环依赖，即环。对于那些不存在回路的有向图称为有向无环图，DAG(Directed Acycline Graph)，可使用拓扑排序的方式对有向图进行检测，判定其是否是DAG。

拓扑排序

拓扑排序可认为当工程只有一个人完成时需要以怎样的活动次序来进行，显然被依赖的活动需要优先完成。

在AOV网中选择一个入度为0的顶点，并且输出
删除该顶点及与其有关的所有弧
重复1,2直到AOV网中不存在入度为0的顶点
若AOV网中依然存在顶点，则其不是DAG

用边表示活动的网 Activity On Edge network AOE

对于有向图中有向边带有权值的情况，可使用以边表示活动的网，权值表示活动的持续时间，AOE网中还可以看出活动的依赖关系，顶点表示以该顶点为弧头的所有边（活动）都已完成，同时也表示以该节点为弧尾的所有边（活动）可以动工。同时也可以将日常生活的的一些活动时间概念加入其中，如最早开始时间，最晚开始时间，最晚结束时间，计划完成时间等。

在AOE网中应该存在一个入度为0的顶点作为工程的开始顶点，称为源点。也应该存在一个出度为0的顶点作为工程的结束顶点，称为汇点。与AOV不同，AOE的关心问题如下：