?
Ⅰ. 图的抽象数据类型 - THE GRAPH ABSTRACT DATA TYPE
0x00 引入：七桥问题
概念：最早可追溯到1736年，欧拉用图论解决了经典的七桥问题。
欧拉证明，如果要从图中的一个节点除法，经图中所有边一次且仅一次，最后回到出发的节点，那么当且仅当图中所有节点的度都是偶数。为了纪念欧拉的发现，我们称之为欧拉回路。
图是使用最广泛的数学结构，可应用于电路分析、寻找最短路径、项目规划、化合物鉴定、网络流程设计、基因/蛋白质相互作用等……
0x01?图的定义
一个图由两个集合构成：?
? ：有限的、非空的顶点集合，?
：有限的、可能是空的边缘集合。
我们可以将其写作 ??.
An undirected graph：each edge is represented as an unordered pair of vertices.
无向图的节点二元组是无序二元组? ?eg.???和?
? 表示同一条边。
A directed graph -- each edge is represented as a directed pair of vertices.
有向图的边是有序的节点二元组，用??表示，
?是边尾，
?是边头。 eg.?
?与?
?是两条不同的边。
这些图的集合表示为：
? ? ? ? ? ? ? ? ? ? ???
? ? ? ?? ??
? ? ? ? ? ? ? ? ? ? ? ?? ?
注意，有向图在边头标出箭头。?是树，我们可以将树定义为图的一种特例 （
?不是树）
① No self loops：
图中不允许存在由节点??发出而只想自己的边，即不允许存在?
?的情况。
也就是说??不是图的合法边，这样的边我们称之为 环边?。
② No multiple edges：
图中一般不重复出现同一条边，如果允许重复出现，那么这样的图称为 重复边图（multigraph）
Complete graph：
对于无向图，一个有??个顶点的完整图有?
?条不同的边。
对于有向图，一个有??个顶点的完整图有?
?条不同的边。?
一个有向图是强连通的（strongly connected），如果??中的每一对不同的顶点，都有一条从?
?到?
?和?
?到?
??的有向路径。
A strongly connected component is a maximal subgraph which is strongly connected.
强连通分量是有向图中的最大强连通子图。
一个顶点的度是与该顶点相关的边的数量。
对于一个有向图，我们将一个顶点 ?的内度（in-degree）定义为以
?为首的边的数量，而一个顶点
?的外度（out-degree）定义为以
?为尾的边的数量。
如果??是一个有?
?个顶点和?
?条边的图?
?中顶点?
?的度数，那么边的数量为：
0x02 图的ADT
Ⅱ. 图的表示
0x00 邻接矩阵 - Adjacency Matrix
令??为一个具有?
?个顶点的图，
?
?的邻接矩阵为一个
?的二维数组，比如 adj_mat，定义为：
adj_mat[i][j] = 1 if the edge ( , ) is in E(G)
0 if there is no such edge.这样的定义也可以用于有向图，只是??是有向的。
无向图的邻接矩阵是对称的，因为边??在?
?中，则边?
?也在?
?中。
对于无定向图，我们可以通过只存储矩阵的上三角或下三角来节省空间。
参考资料
Fundamentals of Data Structures in C
