1.2　搜索算法基础

搜索算法需要通过数据结构来描述搜索过程。所以，本节将先介绍几个搜索中重要的数据结构，包括图、树以及队列。

图（graph）是一种基础的数据结构。一个图（G）由节点的集合（V）和边的集合（E）组成，记作G=（V，E）。图1.4中展示了一个有向图和一个无向图。在无向图中，节点之间由无向边连接，即链接为双向；而在有向图中，节点之间由有向边连接，即链接为单向。对于无向图来说，一个节点的度等于与它相关联的边的数量。如图1.4左图中无向图的节点E，它的度为2。在有向图中，一个节点的度分为入度和出度，分别为到达节点的有向边数与从节点出发的有向边数。如图1.4右图中的有向图，节点D的入度为1，出度为2。

图1.4　无向图和有向图

以下是一些图中重要的概念：

路径：一个节点通向另一节点所经过的边的序列。

路径长度：一个节点到另一节点经过的边的个数或权重之和。

连通图：如果一个无向图中任意两个节点之间都存在路径，则为连通图。

强连通图：如果一个有向图中任意两个有序节点之间都存在路径，则为强连通图。

树（tree）是一种基础的数据结构，由节点和边构成。树可视为一种特殊的无向图，它有以下一些重要的性质：①每个节点只有一个父节点；②只存在一个没有父节点的节点，称为根节点。在树结构中，根节点为第一层，根节点的子节点为第二层，依此类推，如图1.5所示。

树的高度或深度是由树中节点的最大层次决定的。路径表示从根节点到节点的一条由边构成的通路。路径的长度是由其经过的边的数量求和得到的，例如从根节点A到子节点K的路径长度为4。

在搜索过程中，有时需要存储未搜索过的节点。队列是一种常用的存储数据结构。队列是一种线性数据结构，通常有三种形式：第一种是先入先出队列或first-in-first-out队列（FIFO queue），即最先被放入队列的数据最优先被取出，最后被放入的数据最后被取出，如图1.6（a）所示；第二种是优先级队列（priority queue），队列中的元素按照某种函数计算的优先级排列，高优先级的元素先出队；第三种是后入先出队列或last-in-first-out队列（LIFO queue，也称堆栈（stack）），即最后被放入队列的数据最先被取出，如图1.6（b）所示。

在了解了必要的数据结构知识后，下面开始介绍搜索算法。

图1.5　树结构

图1.6　先入先出队列（a）和后入先出队列（b）