14. 无向图
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];
}
}