Ha$p^3$lanet

搜索是互联网时代非常重要的一个技术。作者举了搜索引擎的例子，正是通过搜索引擎，使得人们能够更好的利用存储在互联网上的海量的数据。为了更好的抽象搜索的概念，我们引入以下几个定义：

上节中，我们介绍了图的基本概念以及他的基本操作：存储、遍历方法。这一节，我们更加深入的探讨一些图的相关的实际应用，包括：最小生成树，最短路径 和 有向无环图 的拓扑排序和关键路径问题。每一个应用下，都介绍了几种算法，在这一过程中，我们可以更加深入的了解图的结构及它的相关操作。

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为 $G(V,E)$, 其中，$G$ 表示一个图，$V$ 是图 $G$ 中顶点的集合，$E$ 是图 $G$ 中边的集合。

I 线索二叉树

线索二叉树的构想主要来源于两个问题，1- 二叉链表存储结构让每个结点都有左右指针，但部分结点无左子树/右子树/both。2- 二叉链表不存储结点的前驱、后继结点的信息（（Note：这里的前驱、后继是针对某种遍历方法而言的，前驱指遍历时该结点前一个结点，后继类似。）。

I 定义

树是n个结点的有限集合，在任意一棵非空的树中，1- 有且仅有一个特定的 “根” （root）结点；2- 当 $n>1$ 时，其余结点可分为 $m(m>0)$ 个互不相交的有限集合，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。

串（string）又称为字符串，字符串的查找匹配等操作在计算机中非常重要，因此将其单独列出来讲解。

队列在我们生活中也很常见，例如客服人员接听电话，会将打电话的人按顺序进行排队，时间上最先打入的最早接听。抽象一下，我们定义数据结构：

队列（queue） 是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

栈（stack）是一种后进先出的数据结构，实际上，这种结构运用非常普遍，例如浏览网页时，我们使用”后退”按键，word，PS 等软件的撤销操作，都是栈的应用。

除了使用线性存储结构外，还可以使用链式结构存储线性表。链表的思想就是不再固定元素的位置，而是让每个元素知道它的上一个元素和下一个元素分别在哪里，也就是每个元素不仅存储数据信息，还存储地址信息。我们把存储数据元素信息的域称为 数据域，存储指针元素的域称为 指针域，指针域中存储的信息称为 指针 或者 链，数据域与指针域结合，称为 结点（Node）。

线性表是一种元素的有限序列。它的数据对象集合为 $a_1,a_2,\dots ,a_n$, 每个元素的类型都相同。其中，除第一个元素$a_1$ 外，每个元素都有且只有一个直接前驱元素，除了最后一个元素 $a_n$ 外，每个元素都有且只有一个直接后继元素。