# 图 Graph

作者:小傅哥
博客:https://bugstack.cn (opens new window)

沉淀、分享、成长,让自己和他人都能有所收获!😄

# 一、前言

图的历史

Leonhard Euler 于1736 年发表的关于柯尼斯堡七桥 (opens new window)的论文被认为是图论史上的第一篇论文。这篇论文,以及范德蒙德写的关于骑士问题的论文,都是在莱布尼茨发起的分析位置上进行的。欧拉公式涉及凸多面体的边数、顶点数和面数,由 Cauchy 和L'Huilier 研究和推广,它代表了称为拓扑的数学分支的开始。

1860 年和 1930 年拓扑学的自主发展通过 Jordan、Kuratowski 和 Whitney 的著作使图论得以发展。图论和拓扑学 (opens new window)共同发展的另一个重要因素来自现代代数技术的使用。这种用途的第一个例子来自物理学家古斯塔夫·基尔霍夫的工作,他在 1845 年发表了他的基尔霍夫电路定律,用于计算电路中的电压和电流。

# 二、图的数据结构

图(Graph)结构是一种比树结构复杂的非线性的数据结构,图在实际生活中的例子非常多,比如;地铁线路网、微信好友关系链、计算机中的状态执行等,都可以抽象成图的结构。

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E) = 【G表示图、V表示顶点个数、E表示边的个数】。图的数据结构是多对多关系,就像你的微信好友可能也是我的微信好友,且相互交叉对应。与之对应的是树,树是1对多关系,所以树也是一种特殊的没有闭环的图。

按照图是否有方向是否有权重可以分为一下4类组合;

U/U U/W D/U D/W
无向图&无权重 无向图&有权重 有向图&无权重 有向图&有权重
  • 顶点:图中的任意节点都算作顶点,图中任意两个顶点间都可能存在连接,如果没有顶点间没有连线则称为空图。
  • 无向图:图中任意两个顶点间都没有指向,则称这样的图为无向图。
  • 有向图:图中任意两个顶点间都有指向边,则称这样的图为有向图。
  • 无权重:图中任意两个顶点间的连线,没有权重值,则无权重。
  • 有权重:图中任意两个顶点间的连线,包含权重值,则有权重。

# 三、图的结构实现

图的结构实现可以基于数组、链表和红黑树实现,也因此将使用数组实现的图称为邻接矩阵,链表和红黑树实现的图称为邻接表。

// 图的顶点数
protected int v;
// 图的边个数
protected int e;

// 图的矩阵【数组】
protected int[][] table;
// 图的矩阵【链表】
protected LinkedList<Integer[]>[] table;
// 图的矩阵【红黑树】
private TreeSet<Integer>[] table;
1
2
3
4
5
6
7
8
9
10
11

图的数据存放可以使用 int 数组、LinkedList 链表、TreeSet 红黑树等方式存储。

# 1. 邻接矩阵【数组】

# 1.1 无向图&无权重

// 图的顶点数
protected int v;
// 图的边个数
protected int e;
// 图的矩阵
protected int[][] table;

// 对称插入,无方向,无权重
public void insert(int x, int y) {
    table[x][y] = 1;
    table[y][x] = 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
  • 邻接矩阵通过数组存放元素,会有一些浪费空间,所有的空间都会填满。
  • 在插入元素的时候,对称插入节点。例如:0→1、1→0,两个方向都插入元素。

# 1.2 有向图&有权重

// 图的顶点数
protected int v;
// 图的边个数
protected int e;
// 图的矩阵
protected int[][] table;

// 对称插入,无方向,无权重
public void insert(int x, int y, int weight) {
    table[x][y] = weight;
}
1
2
3
4
5
6
7
8
9
10
11
  • 邻接矩阵通过数组存放元素,会有一些浪费空间,所有的空间都会填满。
  • 在插入元素的时候,插入单向节点,节点值为权重值。例如:0→2,权重值是4。

# 2. 邻接表【链表】

# 1.1 无向图&无权重

// 图的顶点数
protected int v;
// 图的边个数
protected int e;
// 图的矩阵
protected LinkedList<Integer[]>[] table;

// 对称插入,无方向,无权重
public void insert(int x, int y) {
    table[x].add(new Integer[]{y});
    table[y].add(new Integer[]{x});
}
1
2
3
4
5
6
7
8
9
10
11
12
  • 通过数组+链表的实现方式可以减少非必要的元素存储,更加节省空间。
  • 其实插入元素的过程和数组类似,无向无权重直接对称插入元素即可。

# 1.2 有向图&有权重

// 图的顶点数
protected int v;
// 图的边个数
protected int e;
// 图的矩阵
protected LinkedList<Integer[]>[] table;

// 对称插入,有方向,有权重
public void insert(int x, int y, int weight) {
    table[x].add(new Integer[]{y, weight});
}
1
2
3
4
5
6
7
8
9
10
11
  • 通过数组+链表的实现方式可以减少非必要的元素存储,更加节省空间。
  • 其实插入元素的过程和数组类似,有方向有权重则只插入单个指向,并需要通过数组或者对象的方式记录权重值。

# 3. 遍历

图的最终实现是通过 TreeSet 红黑树的方式,这样即节省空间,又能提高元素的索引和遍历效率。

// 图的顶点数
private int v;
// 图的边个数
private int e;
// 图的矩阵
private TreeSet<Integer>[] table;
1
2
3
4
5
6

# 3.1 无向图&有向图

无向图 有向图
对称插入:table[x].add(y); table[y].add(x); 单向插入:table[x].add(y);

# 3.2 广度遍历&深度遍历

U/U U/U D/U D/U
深度遍历 广度遍历 深度遍历 广度遍历

通过四个图的的对比,可以看到;

  1. 深度遍历,不断地向下探测。广度遍历横行探测。
  2. 当有权重时候,则深度和广度会按照权重进行选择优先遍历的顺序。
public void bfs(int s) {
    Queue<Integer> queue = new LinkedList<>();
    visited[s] = true;
    queue.add(s);
    while (!queue.isEmpty()) {
        int v = queue.remove();
        order.add(v);
        for (int w : G.adj(v)) {
            if (!visited[w]) {
                queue.add(w);
                visited[w] = true;
            }
        }
    }
}

private void dfs(int v) {
    visited[v] = true;
    // 深度优先,前序遍历
    pre.add(v);
    for (int w : graph.adj(v)) {
        if (!visited[w]) {
            dfs(w);
        }
    }
    // 深度优先,后序遍历
    post.add(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

# 四、图实现测试

# 1. 邻接矩阵

@Test
public void test_U_U() {
    AdjacencyMatrixArray.U_U matrix = new AdjacencyMatrixArray.U_U(6, 9);
    matrix.insert(0, 1);
    matrix.insert(0, 3);
    matrix.insert(0, 2);
    matrix.insert(0, 4);
    matrix.insert(1, 4);
    matrix.insert(2, 4);
    matrix.insert(2, 5);
    matrix.insert(3, 5);
    System.out.println(matrix);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
  • 在单元测试中共提供了UU、UW、DU、DW四种情况,读者可自行验证。
图配置:V = 6, E = 9
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 | 
⏛⏛⏛⏛⏛⏛⏛⏛⏛⏛⏛⏛⏛⏛⏛⏛
0 | 0 | 1 | 1 | 1 | 1 | 0 | 
---------------------------
1 | 1 | 0 | 0 | 0 | 1 | 0 | 
---------------------------
2 | 1 | 0 | 0 | 0 | 1 | 1 | 
---------------------------
3 | 1 | 0 | 0 | 0 | 0 | 1 | 
---------------------------
4 | 1 | 1 | 1 | 0 | 0 | 0 | 
---------------------------
5 | 0 | 0 | 1 | 1 | 0 | 0 | 
---------------------------
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  • 通过测试结果可以看到一个邻接矩阵无向图且无权重的存放结果。

# 2. 邻接链表

@Test
public void test_D_W() {
    AdjacencyMatrixList.D_W matrix = new AdjacencyMatrixList.D_W(6, 9);
    matrix.insert(0, 1, 1);
    matrix.insert(0, 3, 2);
    matrix.insert(0, 2, 3);
    matrix.insert(0, 4, 5);
    matrix.insert(1, 4, 1);
    matrix.insert(2, 4, 3);
    matrix.insert(2, 5, 7);
    matrix.insert(3, 5, 4);
    System.out.println(matrix);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
  • 在单元测试中共提供了UU、UW、DU、DW四种情况,读者可自行验证。

测试结果

图配置:V = 6, E = 9
---------------------------
0 |[1,1][3,2][2,3][4,5]
---------------------------
1 |[4,1]
---------------------------
2 |[4,3][5,7]
---------------------------
3 |[5,4]
---------------------------
4 |
---------------------------
5 |
---------------------------
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  • 通过测试结果可以看到邻接链表在对图元素的存储上,非常节省空间,并记录了权重值。

# 五、常见面试题

  • 图的使用场景是什么?
  • 图有的分类?
  • 图怎么存放权重值?
  • 图的广度遍历
  • 图的深度遍历