数据结构

数据结构基本术语

• 一、数据的子集

  • 数据：是被计算机程序识别的符号集合；
  • 数据元素：数据的基本单位，通常被作为一个整体(struct)
  • 数据项：若干个数据项组成数据元素，是构成数据元素不可分割的最小单位，struct中的属性；
  • 数据对象：具有相同数据性质的“数据元素的集合”，是数据的子集

• 二、数据结构

  • 数据结构三要素：逻辑结构、存储结构、数据运算
  • 定义：相互之间存在一种或多种特定关系的数据元素的集合；
  • 逻辑上分为：线性结构和非线性结构。用4种结构表示就是，线性、树形、图形、集合；

• 三、抽象数据类型

  • 抽象数据类型 = 数据对象+数据关系+基本操作集

• 四、存储结构：

  • 顺序、链式、索引存储、散列(Hash)存储。四种存储结构有各自的优缺点：
  • 顺序存储：逻辑相邻的结点在物理位置上也相邻，会产生较多外部碎片；
  • 链式存储：不会出现内存碎片，只能顺序存取，也增加了额外的存储空间；
  • 索引结构：检索速度快，不过增加了索引表，增、删、改数据时要修改索引表会花费时间；
  • 散列Hash：增、删、查都快，会存在hash冲突的情况；
  • 四大存储结构：顺序存储、链式存储、索引存储(用一张表记录key的位置)、散列存储(hash函数算出key在内存中的位置)

• 五、存取结构：

  • 随机存取、顺序存取(又称非随机存取)

• 六、逻辑结构

  • 两个就是：线性结构、非线性结构
  • 四个就是：线性结构、树形结构、图形结构、集合；

• 数据结构和数据对象的区别是：后者是数据元素之间有相同性质，前者是数据元素之间有某种关系；

• 七、算法的基本术语

  • 5个特性：有穷性、正确性、可行性、0个或多个输入、1个或多个输出；

  • 4个评价方面：正确性、可读性、健壮性、高效率与低存储

  • 算法的定义：算法是对特定问题求解步骤的一种描述，它是指令的有限序列；

  • 影响时间复杂度的因素：问题规模n、输入数据的性质（输入数据的初始状态）

  • 空间复杂度：算法所消耗的存储空间；

线性表

• 定义：具有相同数据类型的n个数据元素的有限序列；
• 两种存储逻辑结构：

  • 一、顺序存储结构：顺序表(数组)表示，顺序访问+随机访问，占用连续的存储空间，插入、删除需要移动元素，存储密度高(不需要存储额外指示信息)；

  • 二、链式存储结构：

    • 链表表示，顺序访问+不可随机访问，插入、删除只需要修改指针，不需要移动元素，引入了额外的指针域；
    • 五种链表类型：

      • 1、单链表：

        • 头结点(在单链表的第一个元素结点之前增加的一个结点，指向第一个元素结点)、头指针(始终指向链表的第一个结点，有头结点指向头结点，无头结点指向第一个元素)
        • 引入头结点可以空表和非空表处理统一，使得对链表第一个位置上的操作和其它位置的操作一致；
        • 单链表的头插法可以实现链表的逆序：1<-2<-3<-4<-5；
        • 单链表的尾插法是正序：1->2->3->4->5；

      • 2、双链表

        • 双链表可以通过某结点访问它的直接前驱、直接后继，有两个指针next和prior；
        • 插入元素需要进行4步操作：新节点的(next、prior)，前驱结点的next、后继结点的prior；
        • 删除2步操作：前驱结点的next、后继结点的prior；

      • 3、循环单链表

        • 与单链表差不多，不同是在单链表表尾结点指针指向了头结点，形成了一个环；
        • 尾指针，在插入、删除结点之后，一定要保证尾指针指向最后一个结点；

      • 4、循环双链表

        • 与双链表差不多，不同的是头结点的prior指向表尾结点，表尾结点的next指向头结点；

      • 5、静态链表

        • 数组表示的链表，用数组下标表示next；-1表示next=null。插入删除不需要移动元素；

  • 顺序表与链表的对比

    • 数据存储规模难以估计时选链表；
    • 数据插入、删除多的选链表；
    • 链表插入、删除指定结点的时间复杂度为O(n)，因为要遍历到指定结点的前驱才能完成，删除p的后继结点为O(1)；
    • 顺序表在表尾插入、删除时间复杂度为O(1)，在指定位置插入、删除是O(n)

  • 线性表的基本操作方法：

    • InitList(L)，构造一个空的线性表
    • Length(L)
    • LocateElem(L, e)，按值查找
    • GetElem(L, i)，按位查找
    • ListInsert(&L, i, e)，在表中的i个位置插入元素e
    • ListDelete(&L, i, e)，删除表中的i个位置元素值，并返回e
    • PrintList(L)
    • Empty(L)
    • DestoryList(&L)，销毁线性表，释放所占用的内存

栈和队列

• 一、队列：

  • 操作受限的线性表，只允许在一端插入，在另一端删除，先进后出。有顺序存储和链式存储；

  • 1、队列的顺序存储：

    • 两个指针，front指向队头元素，rear指向队尾元素的下一个。初始时front和rear都指向0这个位置；
    • 入队：队未满时，存到rear的位置，rear++；
    • 出队：队未空时，取front指向的元素，front++；

  • 2、循环队列：是一种存储结构，有两个指针front和rear，出队更新front指向，入队更新rear指向；

    • 出队时front=(front+1)%MaxSize，例如n=10，front=0，1%10=1；
    • 入队时rear=(rear+1)%MaxSize，例如n=10，rear=8，9%10=9；
    • 队列长度：[MaxSize-(front-rear)]%MaxSize，例如n=10，front=3，rear=8，(10-1-5)%10=4；
    • 判断队满、队空：
      • (1)、在类型中新增一个字段表示队满、队空；
      • (2)、或者牺牲一个存储单元来区分队满、队空，用front=rear来判断；

  • 3、队列的链式存储

    • 链队是一个带有两个指针front和rear的单链表，头指针指向队头结点，尾指针指向队尾结点，

    • 队空：front和rear指向同一个结点；

    • 入队：在队尾插入结点，更新rear为新插入的这个结点，再把rear指向新加入的结点。例如Q.rear->next=NewElement，Q.rear = NewElement；

    • 出队：先判断是否为空队，从链表中摘下结点，Q.front->next改指向；

    • 注意，默认有头结点的情况，头结点不存实际数据，只指向队列中的第一个元素，也方便代码操作；

    • 4、输入或输入受限的双端队列：只能一边输入或输入，另一端可以插入和删除。双端队列是允许两端都可以进行入队和出队；

• 二、栈：

  • 受限的线性表，只允许在表尾插入或删除操作，后进先出。有顺序栈(顺序表表示)和链栈(链表表示)；

  • 1、顺序栈：入栈、出栈，栈顶指针top会++或--；

  • 2、共享栈：用顺序表存储时有用，可以有效的利用存储空间，头尾各一个栈，栈满两个栈顶指针相遇，top2==top1+1；

  • 3、链栈：不存在上溢的情况，插入、删除结点方便。默认没有头结点；

    • 入栈（头插法）：p->next=NewElement；p=NewElement；入队序列123，头插法结果：321。尾插法找到尾部元素把next指向新结点就行，尾插法结果123；
    • 出栈：摘下一个结点，S = S->next,free(p)；
    • 输入或输入受限的栈：只能一边输入或输入；

  • 4、例题：给定序列的n个元素，将其依次入栈，入栈过程中可以出栈，可以形成多少种出栈序列，用卡特兰函数(2n^n/n+1)表示结果数量（分子和分母各自表示阶乘）;

  • 注意入栈和出栈有规律：比如12345依次入栈出栈，先入栈123，那2就不可能在1的后面，2就不可能在3的前面；

• 三、栈和队列的应用

  • 栈：

    • (1)、括号匹配；
    • (2)、中缀表达式转前缀表达式或后缀表达式；
    • (3)、后缀表达式求值，操作数依次存入新栈，碰到求值符号计算成一个新值在存入新栈，如此重复，最后一个就是值了；
    • (4)、进制转换(数制转换)？

  • 队列：

    • 树的层序遍历、图的广度优先遍历、解决CPU与外部设备速度不匹配的问题、解决多进程资源争夺的问题、页面替换算法、
    • 杨辉三角？

  • 四、广义表(list)不考

    • 广义表是线性表的推广，但广义表不是线性结构，是层次结构
    • 广义表的深度：一层括号就是一层深度，(b,(c,d))，深度是2；
    • 广义表的长度：((d,e),(b,(c,d)))，长度是2，深度是3；
    • 操作：取表头GetGead(LS)、取表尾GetTail(LS)，除第一个元素外，其余元素组成的表就是表尾；

  • 栈的操作方法，做题时如题干未做出限制，则可直接使用这6个基本的操作函数：

    • InitStach(&S)
    • StachEmpty(S)：判断为空返回true，否则返回false；
    • Push(&S, x)：进栈
    • Pop(&S, &x)：出栈，非空就弹出栈顶元素，并用x返回；
    • GetTop(S, &x)：读出栈顶元素，如上；
    • DestoryStach(&S)

  • 队列的操作方法，考试中可以直接用这5个基本方法：

    • InitQueuq(&Q)
    • QueuqEmpty(Q)：判断为空返回true，否则返回false；
    • EnQueue(&Q, x)
    • DeQueue(&Q, &x)：出队，非空就删除对头元素，并用x返回；
    • GetHead(Q, &x)：读对头元素，如上；

树

• 6种树

  • 树、二叉树、线索二叉树、二叉排序树、平衡二叉树、哈夫曼二叉树
  • 转换与还原：树、二叉树、森林相互转换与还原
  • 操作：遍历、并查集

• 一、6种树

  • 树是一种逻辑结构；

  • 结点数、边数、结点的度数、树的层级(h)

  • 1、树、空树、m叉树、树的边数为n-1

    • 树的表示：双亲表示法（数组下标+结构体:parent指针）、孩子链表表示法（需要n个链表）、孩子、兄弟存储结构(链表指定左孩子、右兄弟，多个兄弟之前链起来)

  • 2、二叉树：度为2的树最少有3个结点，满二叉树(叶子结点的父结点的度都为2)、完全二叉树(左右子树高度之差不超过1，缺的结点一定在右子树)

  • 3、线索二叉树：利用叶子结点的左右指针存储直接前驱和直接后继，结构体中加左右两个tag，标记左右指针是指向子节点还是指向前驱或后继；方便遍历之后找前驱和后继；

  • 4、二叉排序树：左子树小于根结点，右子树大于根结点，每颗子树都是这样；

  • 5、平衡二叉树：左右子树高度之差小于等于1，需要维护平衡，判断是ll rr lr rl的哪种不平衡，然后调整最小不平衡子树；

  • 6、哈夫曼二叉树：

    • 也叫最小路径二叉树，带权路径长度(wpl)，把一个序列构造成最小路径树，序列值就是结点的权重，序列值最终都在叶子结点，
    • 构造是从两个最小权重开始，两两合并之后的值放回序列，再从序列中选两个个最小的，最后相加算出wpl值；
    • 路径长度：a-b-c的路径是3 (ab)+((ab)+(bc))；
    • 哈夫曼树的应用哈夫曼编码，哈夫曼二叉树的边标记0和1，组成前缀不同的二进制串；

• 二、森林+转换

  • 树和二叉树的转换

    • 树转成二叉树根结点是没有右子树的，规则是左子树，右兄弟，如此循环；
    • 二叉树转树，左子树的左边是根结点的左子树及孙子树，左子树右边的右子树都是左子树的兄弟结点及兄弟结点的子节点，如此循环即可；

  • 森林转树，不用转，森林就是多棵树

  • 森林转二叉树，把每棵树先分别转成二叉树，然后把右边的树依次连到旁边左子树根结点的右子树上；

  • 二叉树转森林，把二叉树的根结点的右子树断开，依次断开右子树就是森林了；

  • 并查集：union把两颗树合并成一棵树，find找到两颗树是否同属一个根结点，当找到根结点为负数时就不属于同一集合，用树的双亲表示法，用在图上判断图的连通性;

• 三、遍历+还原

  • 1、遍历二叉树：

    • 深度优先：先序遍历、中序遍历、后序遍历。广度优先：层序遍历

    • 树和森林的遍历：只有先序遍历和后续遍历，后序遍历就是二叉树中序，为啥没有后续遍历是因为 lpr，m个子结点p放在哪了对吧；

    • 深度优先：通过描边法遍历，左1、下2、右3，前序按从左到右标记1的路线走，中序按标记2的路线走，后续按标记3的路线走；

    • 广度优先：借助一个队列，根结点先入队，出队时把结点的子节点从左往右依次放入队列，如此循环。标记最长宽度时记录一下每层的宽度值，大于最长宽度就替换现有值；

  • 2、还原遍历序列成二叉树

    • 通过中序+（前、后、层序）可以唯一还原一颗二叉树；
    • 前序遍历序列中第一个结点是根结点、后续最后一个是根结点，在中序序列中找到根结点，然后确定左右子树集合，如此循环即可恢复成二叉树；
    • 前序、后续作用是明确根结点，中序作用是区分左右子树集合；
    • 问题：第二次划分如何确定子树的根结点？一样，根据两个序列中划分的左右子树结合，前序第一个依然是根结点，中序依然可以在找到子树根结点区分左右子树；

图

• 一、概念：

  • 有向图、无向图、无向(有向)完全图、连通图、极大连通子图(连通分量)(针对无向图)、极小连通子图(最小生成树)(针对无向图)、强连通分量(有向图)、强连通图、极大强连通子图；
  • 无向图的度(2e)、有向图的度(出度、入度)、边的权值、回路或环、路径长度(路径上边的数目)

• 二、图的存储

  • 1、邻接矩阵：
    • 用二维数组表示，通过行和列确定出度和入度，适合存储稠密图，通过邻接矩阵可以判断图的类型。
    • 随机访问，很容确定两个顶点是否有边相连，要确定图的总边数时要按行和列检测每个元素，有向图O(n^2)，无向图只需选择上或下三角即可确定边数；
  • 2、邻接表：顶点表、边表，每个顶点建立一个边表，对于有向图就是出边表，适合存储稀疏图。容易找顶点的所有邻边，不方便确定两个顶点是否存在边O(n)；
  • 图的邻接矩阵表示是唯一的，邻接表表示不唯一，链接次序是任意的；

• 三、遍历：

  • 1、深度优先(二叉树前序)
    • 找一个相邻访问，再找相邻边的相邻边访问，重复这个过程，到底之后依次退回到最近被访问的顶点，检查是否有边未被访问，通过visited判断没有访问的顶点；
  • 2、广度优先(层序遍历)：
    • 和二叉树广度优先有两个区别，1多了一个visited区分已经访问过的边，2图有不相邻的子图，需要记录所有子图visited。Tranverse和DFS；
    • BFS算法可以求解单源最短路径，一层就是路径加1；
  • 3、BFS和DFS的遍历结果：邻接矩阵和邻接表遍历结果唯一，图形化的图(随意指向)遍历结果不唯一；
    • 遍历与图的连通性：有向图1次DFS不能证明强连通分量。1次dfs只能遍历到该连通分量是否连通，无向图从任意结点出发只需一次就可以判断图是否连通？

• 四、应用

  • 1、最小生成树(朴树撸鞭)

    • prim普罗姆：

      • 扩展树，构造过程从图中任意取出一个顶点，然后从与这个顶点相邻的边中选一个权值最小且不成环的顶点，以此类推。O(n2)，适用于稠密图；
      • 构造过程从序列中选择最小的两个顶点合并的值插入序列，然后再选出两个最小的顶点，如此重复，最后所有的顶点都会在叶子结点；
      • 有两种方式可以算最小带权路径值，所有的分支结点权值相加或者所有叶子结点乘以各自对应的层级边数相加；

    • kruskal克鲁斯卡尔：

      • 从小到大排序之后，挑选树，每次从图中挑选一条权值最小的边(不要求相邻，选出不相邻就放在一边)，可能有最后一刻在连成一棵树的情况，适合稀疏图；
      • 判断是否产生回路需要用到并查集，如果两个顶点同属一个集合，则加到树里来就是有环的；

    • 生成树唯一的情况：

      • 唯一：1当各边的权值都不相等的时，图的最小生成树是唯一的。2当图本身就是一棵树时，图的最小生成树就是自己本身，这个时候生成树也是唯一；
      • 不唯一：某个时刻有多个边的权值一样，选哪个都行，不唯一，但是权值都是最小的，和哈夫曼树一样WPL最小，树的形态不唯一；

  • 2、最短路径

    • 带权图的最短路径，两个顶点之间最短的那条路径；
    • Dij迪杰斯特拉：
      • 单源最短路径，求某1个顶点到其它顶点的最短路径，每个顶点都要和其它顶点走一趟，选择每趟路径最小的加入集合，
      • 下一趟用上一趟求得的最短路径去找新的最短路径，O(V^2)。不适用负权值的边；
    • froyd弗洛伊德：多源最短路径，不考跳过，也可以用迪杰斯特拉对遍历n次实现；

  • 3、有向无环图描述表达式：

    • 有向无环图DAG，
    • 先画出二叉树，二叉树描述中缀表达式，以乘号为根后划分左右子树，如此循环，再合并相同子树实现重复项共享，从上到下合并；

  • 4、拓扑排序：

    • AOV网，以顶点表示活动，以边表示活动的先后顺序的有向图。
    • 从DAG图中选择前驱为0的顶点输出，然后删除这个顶点相关的边，重复这个过程。拓扑排序和数字排序不同，拓扑排序只是表示事件的先后顺序；
    • 邻接表O(V+E)和邻接矩阵O(V^2)

  • 5、关键路径：

    • AOE网，活动中的最大路径就是关键路径，求解过程ve(k)、vl(k)、e(ak)、l(ak)，max、min，可能有多个路径。
    • 关键路径也可以缩短，但是路径长度不能小于其它可达路径；
    • 只求某个顶点的关键路径可以用描述法，求解活动的最早开始时间、活动的最晚开始时间还是得画求解过程；

查找

• 一、顺序查找

  • 从头开始遍历，一个一个比较关键字，顺序表和链表都支持；
  • 无序和有序序列查找不成功的平均查找长度不一样，有序查找不用到表尾，只要关键词处在两个元素中间就是查找失败；
  • 静态查找表：只有查询操作；动态查询表：需要动态的插入或删除的操作；

• 二、折半查找(考代码)

  • 小high大low（小孩大喽），mid = (low+high)/2，向下取整；
  • 只适用于有序的顺序表。适合静态表，对于需要频繁执行插入和删除的操作的数据集不适用，因为维护有序性工作量比较大；
  • 折半查找判定树：叶子结点为null时会存储祖先结点中的值，左子树：小到第一次位于祖先结点的右侧，大到父结点。右子树：小到父结点，大到第一次位于祖先结点的左侧
  • 折半查找与完全二叉树的关系：折半查找判定树与对应结点完全二叉树树高一样高。折半查找可以看作是在完全二叉树上进行的操作。使用完全二叉树进行折半查找可以提高算法的效率。

• 三、分块查找(索引顺序查找)

  • 吸收了顺序查找和折半查找各自的优点，既有动态结构，又适合快速查找；
  • 加了一层索引表，索引表按关键字有序排列。索引表中的每个元素有各块的最大值和各块的第一个元素地址；
  • 查找过程：先在索引表中用折半查找确定关键字所在的块，再在块内顺序查找；
  • 平均查找长度：[log2(b+1)] + s+1/2，b是块数，s是每块的记录数；

• 四、散列表

  • 1、hash函数：取余法，余数通常为表长m中的最大质数p(只能被自己和1整除的数)

  • 2、hash冲突的解决办法：

    • 开放地址法：取决于如何设置di的值，1、依次加1找地址，2、依次往后取平方公式算(有正负数)，3、再hash法
    • 拉链法：数组加链表

  • 3、装填因子是针对开放地址法来说的，是表的装满程度，表中的记录数n/表的长度m=装填因子，等于1的时候就装满了；查找方法就是构造方法，冲突之后主要看比较次数是多少；

  • 4、开放地址法和拉链法的查找成功和查找失败时的平均查找长度：比较次数相加 除以 元素个数 = ASL；

• 其它查找看树；

排序(9种排序算法分成4大类)

• pre：注意交换和比较次数

• 一、插入

  • 1、直接插入排序：待排序序列某个时刻状态(有序序列、待排序Li、无限序列)，从左往右一个个比对找到Li的插入位置k，找到后将k之后所有元素后移一位，Li复制到k的位置，如此重复；
  • 2、折半插入排序：和直接插入排序唯一的区别是，比较过程是小high大low，交换过程是一样的；
  • 3、分块插入排序(希尔排序)：将一个表每次按第i趟递减拆分成多个子表，分别进行插入排序，最后一次d=1，是全表直接插入排序，用上插入排序表现好的两个优势：数量量少、基本有序；

• 二、交换

  • 1、冒泡排序：正序，从左往右一个一个比对，153287，5和3比交换位置、5和2比交换位置、5和8比交换位置，8和7比交换位置，8一趟之后就到最终位置了；
  • 2、快速排序：额外空间是递归栈，每次把mid调整到最终位置，小high大low，每次递归左边传low-(mid-1)，右边传mid-high，如此递归；

• 三、选择

  • 1、简单选择排序：一趟选择一个最小的，与前排位置交换，每一趟确定一个最终位置，如此重复即可
  • 2、堆排序：
    • 1把初始序列按照双亲结点编号floor(i/2)，用层序遍历构造成平衡二叉树。
    • 2然后把二叉树按逆层序遍历(从右往左)建立初始堆，
    • 3每次把堆顶元素和数组末尾元素交换，再将堆顶元素向下调整维持堆的特性，规模减1，如此重复即可；

• 四、other

  • 1、归并排序：
    • 二路归并排序，
      • 将序列每趟分成多个子表，第一轮2^1=2两两比较，两个子表排序时按表头左对齐，比较表头选择更小的输出，输出一个后当前表中后面的元素往前移动，再进行两表头比较，
      • 如此重复直到一个表空第一轮就结束，第二轮2^2=4，按四个元素分成一个表，按左对齐比较，
      • 如此重复，直到整个表成为一个整体排序结束。小high大low，基于分治的思想，
    • k路归并排序(排序趟数m=logk^n)；
  • 2、基数排序：
    • 需要n个队列辅助(几进制就几个队列，10进制10个队列，二进制2个，31天是1月，就是31进制)，每趟按数字个、十、百位放在对应编号的队列中，
    • 第一趟按个位放分配好之后按队列序号正序收集队列，然后再按照十位分配到对应队列中，如此重复就排序好了；

• 五、9类按相同特性分类：

  • 1、稳定的：直接插入排序、折半插入排序、冒泡排序、归并排序、基数排序；

  • 2、需要额外空间的排序：快速排序(log2n)、归并排序(空间O(n))、基数排序(O(r))

  • 3、时间为O(nlog2^n)的排序(快归队)：快速排序、归并排序、堆排序。其它时间为O(n)、O(n^2)、基数排序是O(d(n+r))，d是趟数、n是分配次数、r是收集次数(队列)；

  • 4、初始关键字序列先关的

    • 初始关键字有(无)序时性能更好的排序算法：基本有序时插入排序和冒泡排序O(n)，关键字有序时快排花的时间最多O(n^2)、关键词无序时快排性能最好；
    • 关键字数量选择合适的排序：关键字少（直接插入排序、简单选择排序），关键词多（快速排序、归并排序、堆排序）
    • 移动次数与初始序列无关：归并排序、基数排序
    • 比较次数与初始序列无关：简单选择排序、折半插入排序、基数排序
    • 排序趟数和初始序列有关：冒泡排序(有序可提前结束)、快速排序(乱序性能最好)

  • 5、一趟最终位置和几趟局部有序

    • 一趟排序后关键字会去到最终位置的：冒泡排序、简单选择排序、快速排序、堆排序，快排的mid在中间位置，另外3种在数组最前或最后；

    • 几趟排序后局部有序的：直接插入排序、折半插入排序、冒泡排序、简单选择排序、归并排序、堆排序

    • 6、是否可以使用链表存储(只需要前驱、后继关系)：直接插入排序、简单选择排序、冒泡排序、归并排序、基数排序

做题汇总

• 特兰函数的4种用法

  • 1、n个元素入栈，可以形成的出栈元素序列个数；

  • 2、n个结点能够构成的不同形态的二叉树数目；

  • 3、n个结点形成的前序、中序、后序、层序序列，问有多少棵二叉树遍历的结果如此；

  • 4、n个结点能够构成的不同形态的有序树数目为多少Catalan(n-1)，n-1的原因是树转二叉树后 根结点无右子树。注意上面三个都是n？

• aov网和aoe网的区别？都是有向图表示；

  • AOV网：用顶点表示活动，用弧表示“活动间的优先关系”的有向图，称为顶点表示活动的网（Activity On Vertex Network)，拓扑排序；
  • AOE网： 是一个带权的有向无环图，其中，顶点表示事件（Event)，边表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。（Activity On Edge) 即边表示活动的网。

• AOV网的应用：

  • 在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动(Activity)，
  • 在有向图里若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。
  • AOV网就是一种可以形象地反映出整个工程中各个活动之间的先后关系的有向图。

• AOE网的应用：

  • 在工程实施过程中，有些活动开始是以它的所有前序活动的结束为先决条件的，必须在其他有关活动完成之后才能开始，有些活动没有先决条件，可以安排在任何时间开始。

• 问题

• 图的深度优先有点不太会；