14.1 术语
图是由一组顶点和将点连接起来的边组成的。
-
相邻：如果两个顶点被至少一条边连接，那么就称顶点相邻，并称边依附于顶点。
-
顶点的度：依附于它的边的条数
-
子图：一幅图的子集（包括边和顶点）组成的图
-
路径：由边顺序连接的一组顶点
其中又分为简单路径和环：
简单路径：没有重复顶点的路径
简单环：起点和终点必须相同的没有重复顶点和边的环
-
连通图：如果从任何一个顶点都存在一条路径到达另一个任意节点，那么称这幅图为连通图
如果一副非联通图由若干个连通部分组成，那么这些部分都叫做极大连通子图
-
无环图：就是没有环的图
树是一幅无环连通图
-
密度：已经连接的顶点对占所有可能被连接的顶点对的比例。
这派生出了两个概念，稀疏图和稠密图。
一般来说，如果一幅图中不同的边的数量在顶点总数的一个小常数倍内，那么这幅图就是稀疏的 -
二分图：一种能够将所有顶点分成两部分的图，其中每条边都连着两个不同的顶点
14.2 表示法
14.2.0 API
为了解决有关图的问题，下面定义一个图的基本 API
public class Graph {
public Graph(int V) // Create graph using the Vertex number
public Graph(In in) // Create graph from input stream
public int V(); // The number of Vertex
public int E(); // The number of Edge
// Add edge v-w into graph
public void addEdge(int v, int w);
// The vertexes adjacent to v
public Iterable<Integer> adj(int v);
public String toString(); // The string explanation of graph
}14.2.1 邻接矩阵
使用一个 的布尔矩阵来表示图，当 和 相邻时，将 v 行 w 列的元素标记为 true，否则为 false
这种方法需要 个布尔值的空间，实际上十分耗费存储空间，不实用。
而且当图具有平行边时，邻接矩阵无法准确表示这一结构。
14.2.2 边的数组
我们可以定义一个 Edge 类，其中使用两个 int 变量来表示所连接的两个顶点。
但是这一结构无法实现 adj()，实现它需要检查图中所有的边。
14.2.3 邻接表数组
我们可以使用一个以顶点为索引的列表数组，其中每个元素都是和该顶点相邻的顶点列表。
即，每个数组元素既是一个顶点也是一个链表头，链表储存着与该顶点（链表头）相邻的所有顶点。
它可以实现：
- 使用的空间和 成正比
- 添加一条边所需的时间为常数
- 遍历顶点 v 的所有相邻顶点所需要的时间和 v 的度数成正比
对于这些操作来说，这样的特性已经是最优的了，所以我们选择邻接表来作为图的数据结构
下面是图的代码实现：
public class Graph {
private final int V; // Vertex number
private int E; // Edge number
private Bar<Integer>[] adj; // adjacent array
public Graph(int V) {
this.V = V;
this.E = 0;
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<Integer>();
}
}
public Graph(In in) {
this(in.readInt());
int E = in.readInt();
for (int i = 0; i < E; i++) {
// Add Edge
int v = in.readInt();
int w = in.readInt();
addEdge(v, w);
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
}