数据结构/图

数据结构
引言 - 渐进符号 - 数组 - 列表结构 & 迭代器
栈 & 队列 - 树 - 最小 & 最大堆 - 图
哈希表 - 集合 - 权衡

图

图是一种结构，由一组顶点 $\{v_{1},v_{2},\dots ,v_{n}\}$ 和一组边 $\{e_{1},e_{2},\dots ,e_{m}\}$ 组成。边是一对顶点 $\{v_{i},v_{j}\}\ i,j\in \{1..n\}$。这两个顶点被称为边的端点。图在计算机科学中无处不在。它们被用来模拟现实世界的系统，例如互联网（每个节点代表一个路由器，每条边代表路由器之间的连接）；航空公司连接（每个节点是一个机场，每条边是一次航班）；或城市道路网络（每个节点代表一个交叉路口，每条边代表一个街区）。计算机图形中的线框图是图的另一个例子。

图可以是无向的或有向的。直观地，无向边模拟了其端点之间的“双向”或“双工”连接，而有向边是一条单向连接，通常被绘制成箭头。有向边通常被称为弧。从数学角度来看，无向边是顶点的无序对，而弧是有序对。例如，道路网络可以被模拟成一个有向图，其中单行道用箭头表示端点之间适当的方向，而双行道用一对平行有向边表示端点之间两个方向。你可能会问，为什么不用一个无向边来表示双行道呢？从理论上讲，这没有问题，但在实际的编程中，一般来说，坚持使用所有有向边或所有无向边会更简单，更不容易出错。

一个无向图最多可以有 $\left({\begin{array}{c}n+1\\2\end{array}}\right)$ 条边（每对无序对一条），而一个有向图最多可以有 $n^{2}$ 条边（每对有序对一条）。如果一个图的边远少于这个数量（通常是 $O(n)$ 条边），则称该图是稀疏的，而如果一个图的边接近于 $\Omega (n^{2})$ 条边，则称该图是稠密的。多重图在同一对顶点之间可以有多条边。例如，如果有人模拟航班，在两个城市之间可能有多趟航班，发生在一天中的不同时间。

图中的路径是指一系列顶点$\{v_{i_{1}},v_{i_{2}},\dots ,v_{i_{k}}\}$，其中相邻顶点之间存在边或弧。当$v_{i_{1}}\equiv v_{i_{k}}$时，该路径被称为环。无向无环图等同于无向树。有向无环图被称为DAG，它不一定是一棵树。

节点和边通常具有关联信息，例如标签或权重。例如，在一个航空航班图中，一个节点可能用相应机场的名称进行标记，一条边可能具有等于飞行时间的权重。流行的游戏"六度空间"可以用一个带标签的无向图来建模。每个演员成为一个节点，用演员的姓名标记。当两个演员在同一电影中出现时，节点之间通过一条边连接。我们可以用电影的名称来标记这条边。判断一个演员是否与凯文·贝肯之间存在六个或更少的步骤，等同于在图中寻找一条长度不超过六的路径，这条路径连接着贝肯的顶点和另一个演员的顶点。（这可以用在配套的算法书中找到的广度优先搜索算法来完成。弗吉尼亚大学的贝肯神谕已经实现了这个算法，它可以通过几个点击就能告诉你任何演员到凯文·贝肯的路径[1]。）

有向图

一个有向图。

以给定顶点为端点的边的数量被称为该顶点的度。在有向图中，指向给定顶点的边的数量被称为其入度，而从其指向的边的数量被称为其出度。通常，我们可能希望能够区分不同的节点和边。我们可以将标签与两者关联。我们称这样的图标记图。

有向图操作

make-graph(): 图

创建一个新的图，最初没有节点或边。

make-vertex(图 G, 元素 value): 顶点

创建一个新的顶点，并赋予给定的值。

make-edge(顶点 u, 顶点 v): 边

在u和v之间创建一条边。在有向图中，边将从u流向v。

get-edges(顶点 v): 边集

返回从v流出的边的集合

get-neighbors(顶点 v): 顶点集

返回与v相连的顶点集

无向图

一个无向图。

在有向图中，边从一个顶点指向另一个顶点，而在无向图中，边只是连接两个顶点。我们可以向前或向后移动。这是一个双向图。

加权图

我们可能还想将一些成本或权重与边的遍历相关联。当我们添加此信息时，图被称为加权图。一个加权图的例子是国家首都之间的距离。

有向图和无向图都可以是加权图。加权图上的操作与在创建边时添加权重参数相同

加权图操作（无向/有向图操作的扩展）

make-edge(顶点 u, 顶点 v, 权重 w): 边

在u和v之间创建一条权重为w的边。在有向图中，边将从u流向v。

图表示

邻接矩阵表示

邻接矩阵是表示图的两种常见方式之一。邻接矩阵显示哪些节点是相邻的。如果两个节点之间有一条边连接，则它们相邻。在有向图的情况下，如果节点$j$ 与节点 $i$ 相邻，则从 $i$ 到 $j$ 存在一条边。换句话说，如果$j$ 与 $i$ 相邻，则可以通过遍历一条边从 $i$ 到达 $j$。对于一个具有 $n$ 个节点的图，邻接矩阵将具有 $n\times n$ 的维度。对于无权图，邻接矩阵将用布尔值填充。

对于任何给定的节点 $i$，可以通过查看邻接矩阵的第 $\left(i,\left[1..n\right]\right)$ 行来确定其相邻节点。在 $\left(i,j\right)$ 处的值为真表示从节点 $i$ 到节点 $j$ 存在一条边，而假表示没有边。在无向图中，$\left(i,j\right)$ 和 $\left(j,i\right)$ 的值将相等。在加权图中，布尔值将被连接两个节点的边的权重替换，并使用一个特殊值来指示边不存在。

邻接矩阵的内存使用量为 $O(n^{2})$。

邻接表表示

邻接表是图的另一种常见表示。有很多方法可以实现这种邻接表示。一种方法是让图维护一个列表的列表，其中第一个列表是对应于图中每个节点的索引列表。每个索引都指向另一个列表，该列表存储每个相邻节点的索引。在该列表中，将每个链接的权重与相邻节点相关联可能也很有用。

示例：一个无向图包含四个节点 1、2、3 和 4。1 与 2 和 3 相连。2 与 3 相连。3 与 4 相连。

1 - [2, 3]

2 - [1, 3]

3 - [1, 2, 4]

4 - [3]

将图中所有节点的列表存储在哈希表中可能很有用。然后，键将对应于每个节点的索引，而值将是对相邻节点索引列表的引用。

另一种实现可能需要每个节点都保留一个其相邻节点的列表。

图遍历

在理想情况下，我们应该完全了解图的内容，以便为顶点和边优化索引，从而实现高效查找。然而，在计算机科学中，存在许多开放式问题，索引在这些问题中是不切实际甚至不可能的。图遍历让我们能够解决这些问题。遍历让我们能够高效地搜索大型空间，其中对象通过它们与其他对象的关联关系而不是对象本身的属性来定义。

深度优先搜索

从顶点 a 开始，访问其邻居 b，然后访问 b 的邻居 c，并持续进行，直到到达“死胡同”。然后回溯，访问从倒数第二个访问的顶点可达的节点，并继续应用相同的原则。

// Search in the subgraph for a node matching 'criteria'. Do not re-examine 
// nodes listed in 'visited' which have already been tested.
GraphNode depth_first_search(GraphNode node, Predicate criteria, VisitedSet visited) {
// Check that we haven't already visited this part of the graph
if (visited.contains(node)) {
 return null;
}
visited.insert(node);
// Test to see if this node satisfies the criteria
if (criteria.apply(node.value)) {
 return node;
}
// Search adjacent nodes for a match
for (adjacent in node.adjacentnodes()) {
 GraphNode ret = depth_first_search(adjacent, criteria, visited);
 if (ret != null) {
  return ret;
 }
}
// Give up - not in this part of the graph
return null;
}

广度优先搜索

广度优先搜索访问节点的邻居，然后访问邻居的未访问邻居，依此类推。如果它从顶点 a 开始，它将访问所有从 a 有边的顶点。如果某些点不可达，则需要从一个新的顶点开始另一个广度优先搜索。

---

数据结构
引言 - 渐进符号 - 数组 - 列表结构 & 迭代器
栈 & 队列 - 树 - 最小 & 最大堆 - 图
哈希表 - 集合 - 权衡