0%

图的数据结构及基础算法

图(Graph)这个数据结构在平时开发中遇到的比较少,但我认为它是十分重要的,因为从真实的世界中来看,很多东西都可以抽象为图的表示,比如人际关系,地理位置,天马行空的东西都可以抽象为图,所以它比链表等基础数据结构高级一点点,也比较复杂,属于非线性结构。数学中有一个图论的分支也是与其有关。了解图在程序世界的存储方式,我们可以更加细致地刻画图的结构,让其为我所用,岂不妙哉?

定义和分类

那么图的定义是什么呢?我们直接看维基百科:

一张图 $G$ 是一个二元组$(V,E)$,其中$V$称为顶点集,$E$称为边集。它们亦可写成$V(G)$和$E(G)$。 $E$的元素是一个二元组数对,用$(x,y)$表示,其中${x,y} \in V$。

下面一个图的示例:

image

图中的元素被称为顶点(Vertex),顶点与顶点之间连线被称为(Edge),每个顶点有多少连线被称称为(Degree),比如a图的2节点,度为2。

图(a)顶点与顶点之间的边没有方向,这种图被称为无向图(Undirected graph),在现实中,一个顶点与另一个顶点之间也可以是有向的,比如我们熟悉的铁路网等,从一个地方到一个地方,必然是有指向的,这种叫有向图(Directed graph),如图(b)所示。当然一个更常见的场景,比如北京到上海的距离肯定比上海到苏州的距离长,如何描述边与边的权重呢?这种图被称为带权图(Weighted graph),1顶点到2顶点边的权重为1。这里的权重只是抽象出的概念,在现实中可根据不同场景代表不同的含义,比如距离,车票价格等。

有向图中,指向这个顶点的边和从其出发的边是不一样的,所以用出度(Out-degree)和入度(In-degree)来具体描述顶点的度。出度指的是有多少边是从当前顶点出发指向其他顶点;入度指的是有多少边指向当前顶点。对于图(b)而言,1节点的出度和人度都是1。

当然图是有很多的概念,上面是最基本的,了解了这些,我们才可以探讨图在代码中如何表示(以无向图示例)。

存储表示

根据维基百科的介绍,图有如下存储表示:

  • 邻接矩阵(Adjacency matrix)
  • 邻接表(Adjacency list)
  • 前向星
  • 有向图的十字链表
  • 无向图的邻接多重表

本文以邻接矩阵和邻接表为例,后面几种再单独探讨。

邻接矩阵

大学学过线性代数的同学对矩阵可能还有点印象,矩阵(Matrix)是一个按照长方阵列排列的复数或实数集合,映射到编程语言是二维数组。

对于上图(a)而言,该图是一个无向不加权图,在矩阵中,其中的元素初始值都是0,我们规定从一个顶点i到另一个顶点j如果有边,这两个顶点对应的矩阵位置G(i, j) 和 G(j, i) 的值记为1,由于是无向图,可能会映射到两个元素,下面是图(a)的邻接矩阵表示:

对于图(b),这是个有向不加权图,我们规定,,其中的元素初始值都是0,从一个顶点i指向另一个顶点j,这两个顶点对应的矩阵位置G(i, j)的值记为1,图(b)的邻接矩阵表示为:

对于图(c),这是个无向加权图,我们规定,元素初始值都是0,从一个顶点i到另一个顶点j如果有边,这两个顶点对应的矩阵位置G(i, j) 和 G(j, i) 的值记为该边的权重值,所以图(c)的邻接矩阵表示为:

从上面的几个邻接矩阵来看,用邻接矩阵来表示图还是很方便的,虽然简单,但却有很大问题,假设现在图G有n个顶点,需要开辟$n^2$个空间,并且很多空间都没有存储值,白白被浪费掉了。所以用邻接矩阵来表示图还是需要考虑考虑的。

用邻接矩阵来表示图代码也很简单,我们需要声明一个二维数组:

1
2
// 邻接矩阵
private int[][] adjacencyMatrix;

接下来要做的一个操作是添加边,首先要知道起始顶点的位置和目标顶点的位置,无向图两个位置都要赋值为1,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 添加边
*
* @param start 起始节点位置
* @param end 结束节点位置
*/
public void addEdge(int start, int end) {
checkPosition(start);
checkPosition(end);

this.adjacencyMatrix[start][end] = 1;
this.adjacencyMatrix[end][start] = 1;
this.edgeSize++;
}

下面是完整代码:

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
* 无向图 - 基于邻接矩阵(adjacency matrix)
*
* @author hanjuntao
*/
public class AMUndiGraph implements Graph {

/**
* 邻接矩阵长或宽最大长度
*/
private static final int maxSideLength = 4;
// 邻接矩阵长或宽长度
private int sideLength;
// 邻接矩阵
private int[][] adjacencyMatrix;
// 节点数目
private int nodeSize;
// 边数量
private int edgeSize;

public AMUndiGraph() {
this(maxSideLength);
}

public AMUndiGraph(int sideLength) {
if (sideLength <= 0) {
throw new IllegalArgumentException("The sideLength [" + sideLength + "] is not valid number");
}

this.sideLength = sideLength;
adjacencyMatrix = new int[sideLength][sideLength];
}

/**
* 添加边
*
* @param start 起始节点位置
* @param end 结束节点位置
*/
public void addEdge(int start, int end) {
checkPosition(start);
checkPosition(end);

if (this.adjacencyMatrix[start][end] == 0 && this.adjacencyMatrix[end][start] == 0) {
this.adjacencyMatrix[start][end] = 1;
this.adjacencyMatrix[end][start] = 1;
this.edgeSize++;
}
}

/**
* 获取节点数量
*
* @return 节点数量
*/
@Override
public int getNodeSize() {
int currNodeSize = 0;

for (int i = 0; i < sideLength; i++) {
for (int j = 0; j < i + 1; j++) {
if (adjacencyMatrix[i][j] == 1) {
currNodeSize++;
}
}
}

return currNodeSize;
}

/**
* 获取边的数量
*
* @return 边的数量
*/
@Override
public int getEdgeSize() {
return this.edgeSize;
}

private void checkPosition(int index) {
if (index < 0 || index >= adjacencyMatrix.length) {
throw new IllegalArgumentException("The index [" + index + "] is not valid number");
}
}

@Override
public String toString() {
return "AMUndiGraph{" +
"sideLength=" + sideLength +
", adjacencyMatrix=" + Arrays.deepToString(adjacencyMatrix) +
", nodeSize=" + nodeSize +
", edgeSize=" + edgeSize +
'}';
}
}

邻接表

用邻接矩阵表示图代码很简单,计算也很方便,如果边比较密集,还是可以考虑的。可以不可以不要二维数组只要一维数组表示图呢?知道散列表的拉链法的同学比较清楚当一个key出现哈希冲突时,会存到链表里面,邻接表与这个类似,我们需要一个一维数组来保存所有的顶点,每一个顶点对应一个链表,存储所以与该顶点存在边的顶点。当我们需要判断一个顶点与另一个顶点是否存在边时,我们可以定位到这个顶点,然后遍历其链表看看有没有另一个顶点即可。如下图所示:

image

首先我们声明邻接表:

1
2
// 邻接表
private LinkedList<Integer>[] adj;

接着需要添加边,对于无向图,我们只需要将目标顶点放入到顶点对应的链表中就行了,代码如下:

1
2
3
4
5
6
7
public void addEdge(int start, int end) {
checkPosition(start);
checkPosition(end);
adj[start].add(end);
adj[end].add(start);
this.edgeSize++;
}

完整代码如下:

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* 无向图 - 基于邻接表(adjacency list)
*
* @author hanjuntao
*/
public class AJUndiGraph implements Graph {
// 邻接表
private LinkedList<Integer>[] adj;
// 边数量
private int edgeSize;

public AJUndiGraph(int arrSize) {
if (arrSize <= 0) {
throw new IllegalArgumentException("The arrSize [" + arrSize + "] is not valid number");
}

adj = new LinkedList[arrSize];
for (int i = 0; i < arrSize; i++) {
adj[i] = new LinkedList<>();
}
}

public void addEdge(int start, int end) {
checkPosition(start);
checkPosition(end);

adj[start].add(end);
adj[end].add(start);
this.edgeSize++;
}

private void checkPosition(int index) {
if (index < 0 || index >= adj.length) {
throw new IllegalArgumentException("The index [" + index + "] is not valid number");
}
}

@Override
public int getNodeSize() {
return adj.length;
}

@Override
public int getEdgeSize() {
return this.edgeSize;
}

@Override
public String toString() {
return "AJUndiGraph{" +
"adj=" + Arrays.deepToString(adj) +
", nodeSize=" + getNodeSize() +
", edgeSize=" + edgeSize +
'}';
}
}

References: