0%

14. 无向图

14.1 术语

图是由一组顶点和将点连接起来的组成的。

  1. 相邻:如果两个顶点被至少一条边连接,那么就称顶点相邻,并称边依附于顶点。

  2. 顶点的度:依附于它的边的条数

  3. 子图:一幅图的子集(包括边和顶点)组成的图

  4. 路径:由边顺序连接的一组顶点

    其中又分为简单路径
    简单路径:没有重复顶点的路径
    简单环:起点和终点必须相同的没有重复顶点和边的环

  1. 连通图:如果从任何一个顶点都存在一条路径到达另一个任意节点,那么称这幅图为连通图

    如果一副非联通图由若干个连通部分组成,那么这些部分都叫做极大连通子图

  2. 无环图:就是没有环的图

    树是一幅无环连通图

  3. 密度:已经连接的顶点对占所有可能被连接的顶点对的比例。

    这派生出了两个概念,稀疏图稠密图
    一般来说,如果一幅图中不同的边的数量在顶点总数VV的一个小常数倍内,那么这幅图就是稀疏的

  4. 二分图:一种能够将所有顶点分成两部分的图,其中每条边都连着两个不同的顶点

14.2 表示法

14.2.0 API

为了解决有关图的问题,下面定义一个图的基本 API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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×VV \times V布尔矩阵来表示图,当 vvww 相邻时,将 vw 列的元素标记为 true,否则为 false

这种方法需要 V2V^2 个布尔值的空间,实际上十分耗费存储空间,不实用。

而且当图具有平行边时,邻接矩阵无法准确表示这一结构。

14.2.2 边的数组

我们可以定义一个 Edge 类,其中使用两个 int 变量来表示所连接的两个顶点。

但是这一结构无法实现 adj(),实现它需要检查图中所有的边。

14.2.3 邻接表数组

我们可以使用一个以顶点为索引的列表数组,其中每个元素都是和该顶点相邻的顶点列表

即,每个数组元素既是一个顶点也是一个链表头,链表储存着与该顶点(链表头)相邻的所有顶点

Adjacent Array

它可以实现:

  1. 使用的空间和 V+EV + E 成正比
  2. 添加一条边所需的时间为常数
  3. 遍历顶点 v 的所有相邻顶点所需要的时间和 v 的度数成正比

对于这些操作来说,这样的特性已经是最优的了,所以我们选择邻接表来作为图的数据结构

下面是图的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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];
}
}