# Introduction

图是一种与树有些相像的数据结构，实际上，从数学意义上说，树是图的一种。然而，在计算机程序设计中，图的应用方式与树不同。图(Graph)是一种非线性数据结构，形式化描述为:$ Graph=(V,E) $。其中，$V={Vi | Vi ∈datatype, i=0,1,……,n-1}$ 是图中元素$Vi$(称为顶点 Vertex )的集合，$n=0$时，$V$为空集，记为$φ$。$E$是顶点之间的关系集，$E(Vi,Vj)$为顶点$Vi$与$Vj$之间是否存在路径的判定条件，即若$Vi$与$Vj$之间的路径存在，则关系$P< Vi,Vj >∈E$。

$$ E = {<V_i,V_j> | (V_i,V_j) \in V 且 P(V_i,V_j), 0 \leq i,j \leq n - 1} $$

在一张图中，树的边数为顶点数减一，而度数为边数的两倍。

Terminology

一个典型的图如下所示：

(1)邻接 如果两个顶点被同一条边连接，就称这两个定点是邻接的，譬如上图中顶点 I 和 G 是邻接的，但是 I 和 F 就不是邻接的。和某个指定顶点邻接的顶点有时叫做它的邻居，譬如 G 的邻居是 I、H 和 F。 (2)路径 路径是边的序列，上图显示了一条从顶点 B 到顶点 J 的路径，这条路径通过了顶点 A 和顶点 E。这条路径称作 BAEJ。这两个顶点之间还有其他路径，从 B 到 J 的另一条路径是 BCDJ。 (3)连通图 如果至少有一条路径可以连接起所有的顶点，那么这个图被称作连通的，否则就是非连通图。

(4)有向图与无向图

无向图中的边是没有方向的，可以从任意一边到另一边，所以，可以从顶点 A 到顶点 B，也可以从顶点 B 到顶点 A，两者是等价的。然而，有时候图还可以用来模拟另一种情况，即只能沿着边朝一个方向移动——只能从 A 到 B，而不能从 B 到 A，就像单行道一样，这样的图被称作是有向。允许移动的方向在图中通常用边一端箭头表示。 在某些图中，边被赋予一个权值，权值是一个数字，它能代表两个顶点间的物理距离，或者从一个顶点到另一个顶点的时间，或者是两点间的花费(譬如飞机航线)。

图的表示

顶点与边

在抽象的图中，只是简单地把顶点编号，从$0$到$N-1$($N$是顶点数)，不需要任何变量类型存储顶点，因为它们的用处来自于它们之间的相互关系。然而在大多数情况下，顶点表示某个真实世界的对象，这个对象必须用数据项描述。譬如，如果在一个飞机航线模拟的图中，顶点代表城市，那么它需要存储城市名字、海拔高度、地理位置和其他信息，基本的如下所示：

邻接矩阵

邻接表

搜索

广度优先搜索：广度优先搜索是按照树的层次进行的搜索，如果此层没有搜索完成的情况下不会进行下一层的搜索。

深度优先搜索：深度优先搜索是按照树的深度进行搜索的，所以又叫纵向搜索，在每一层只扩展一个节点，直到为树的规定深度或叶子节点为止。这个便称为深度优先搜索。

最小生成树