数据结构——图论基础

数据结构
字数统计: 4.8k   |   阅读时长≈ 20 分钟

什么是图

  • 图形结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层的结点 只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图形结构中，任意两个结点之间都可能相关，即结点之间的领接关系可以是任意的。

  • 图可以分为两种：有向图和无向图

    有向图
    无向图

图的相关术语

  1. 顶点： 途中的任何一个结点，都可以称作顶点，在图中不允许没有顶点，线性表可以是空表，树可以是空树，但是图不可以是空图，图可以没有边，但至少要有一个顶点
  2. 边： 连接到顶点的线就是边，即顶点到顶点之间的连线
  3. 顶点的度： 连接该顶点的边的条数
  4. 出度： 箭头从这个顶点指出去的就是出度
  5. 入度： 箭头方向指向这个顶点的就是入度
  6. 有向图： 顶点与顶点之间的关系是有方向的
  7. 无向图： 顶点与顶点之间的关系没有方向的

图的存储

使用邻接矩阵(二维数组)来存储图形结构

1、如果有N个节点，那么我们就需要使用N*N的矩阵来存储

有向图

在上面的有向图中共有7个顶点，那么我们就需要使用一个7*7的二维数组来进行存储，我们将A-G转为0-6对应的数组下标，二维数组的横坐标代表当前的节点，纵坐标代表其他节点，如果当前的值为1，表示两个点之间存在关联，否则没有关联。如下：

(1) A[0][1] = 1 : 第0个元素和第1个元素是有关联的（即A和B有联系）

(2) A[1][0] = 0 : 第1个元素和第0个元素没有关联（即B和A之间没有联系，因为是有向图）

(3) A[1][2] = 1 : 第1个元素和第二个元素有关联（即B和C之间有联系）

……依次进行映射，得到如下的图

邻接矩阵

这里会有一个稀疏矩阵的概念：矩阵中各个顶点之间的关联很少（即存在大量0，只有很少的值为1），这样就会有一个问题——保存图形结构的二维数组中大量空间被浪费掉的情况，为了减少这种不必要的浪费，可以使用邻接表来存储图形

使用领接表(链表)来存储图形结构

使用邻接表(链表)的方式来存储图形和Map中存储entity元素有点类似。

有向图

接下来我们利用链表将上述有向图存储起来

使用邻接表(链表)保存图形结构

两种存储方式对比

  • 领接矩阵(数组)： 浪费空间，但是操作都是在内存中进行，速度快。合适处理数据量不大的场景
  • 邻接表(链表)： 节省空间，速度比较慢，适合大数据量场景

图形的遍历

图形的遍历算法有两种：深度优先算法(DFS)和广度优先算法(BFS)

核心关键：

  • 队列(queue)：每次需要pop()取队列头元素，并且将头元素有关的节点全部加入队列。
  • 标记数组mark：每次将遍历过的结点打标记，下次遍历将不会再遍历有标记的结点。深度优先算法中，由于使用递归，存在回溯操作，所以在递归完后需要将结点标记取消
  • 以上两步操作参考下面代码部分

广度优先算法(BFS)

广度优先遍历就是类似于树的层次遍历，利用一个队列，先找到一个点，然后我们把这个点加入到队列中，从队列中取出一个值，依次找出这个点的关联结点加入到队列中，循环这个操作，知道队列为空，此时我们就已经完成了整个图的遍历。

注意： 这里同样我们需要对遍历过的点进行标记，如果这个点在队列中加入过，则不能再继续添加到队列中。比如：A→B，B→A，此时如果不做标记，A走到B，尝试B的时候，因为B到A又要尝试A一遍，会陷入死循环（有点类似Spring中的循环依赖）。

例如：将下面有向图做广度遍历

有向图

广度优先遍历
1、取一个点出来，这里我们从A开始，将A点放入队列中
2、从对头取出一个元素
3、将与A有关的所有结点放入队列中
4、标记A为遍历过的点，被标记过的结点不会再走

队列 入队结点 标记结点 出队结点
[A] A A A
[B] B A,B B
[C,F] C,F A,B,C,F C
[F,E] E A,B,C,F,E F
[E,G] G A,B,C,F,E,G E
[G,D] D(B结点已经被标记，不会再入队) A,B,C,F,E,G,D G
[D] 没有，G结点下没有关联结点 A,B,C,F,E,G,D D
[] 没有，队列为空，结束遍历 A,B,C,F,E,G,D

最终上面有向图的广度遍历结果为：ABCFEGD

深度优先算法(DFS)

深度优先算法可以想象成是走迷宫，我们会选择一个方向一路走到底，直到不能走了然后再返回上一步继续尝试其他方向，在代码中就是递归+回溯，这就是深度优先遍历。同样，我们需要标记已经走过的点，原因和广度优先遍历一样，防止陷入死循环。

在深度优先算法中有一个重要的优化手段就是剪枝 。

举例说明：

有向图

找到一个节点，先按照一个方向一致走下去(反映到代码中就是递归)，并且将走过的点进行标记，下次不再走标记过的点，如果没有与当前点有关联的点了，就一步一步往会返(代码中就是回溯操作)。

路径 标记点
A A
A->B A,B
A->B->E A,B,E
A->B->E->D A,B,E,D
A->B->E->D->C A,B,E,D,C
A->B->E->D(回溯，因为跟C有关的点都被标记了) A,B,E,D,C
A->B->E(回溯，跟D有关的点都被标记) A,B,E,D,C
A->B(回溯，跟E有关的点都被标记) A,B,E,D,C
A->B->F(C被标记，不用走) A,B,E,D,C,F
A->B->F->G A,B,E,D,C,F,G

上面我们是对节点的遍历，如果我们需要的是所有的路径，则在回退节点的时候，还应该将已经遍历过的标记的点也进行回退，这样我们就可以实现全部路径的遍历，可以参考后面的算法示例

案例

解救美女1 (使用BFS广度优先算法解决)

有一天，小美和你去玩迷宫。但是方向感不好的小美很快就迷路了，你得知后便去解救无助的小美，你已经弄清楚了迷宫的地图，现在你要知道从你当前位置出发你是否能够达到小美的位置？

使用BFS广度优先算法解决

  • 1表示地图上的障碍物，0表示有路可以走

  • 邻接矩阵（二维数组）：

    0(你) 0 1 0

    0 0 0 0

    0 0 1 0

    0 1 0(小美) 0

    0 0 0 1

代码

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
package com.lhb.test;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * - 有一天，小美和你去玩迷宫，但是方向感不好的小美很快就迷路了，你得知之后便去营救，你已经弄清楚了迷宫的地图，现在你要知道你从当前位置出发是否能够到达小美的位置
 *
 * - 1表示地图上的障碍物，0表示有路可以走
 * - 邻接矩阵（二维数组）：
 *
 * 0（你） 0 1 0
 * 0         0 0 0
 * 0 0 1 0
 * 0 1 0（小美） 0
 * 0 0 0 1
 *
 */
public class BFS {
    /**
     * 用来表示地图总共有几行
     */
    private int n;
    /**
     * 用来表示地图总共有几列
     */
    private int m;
    /**
     * 目标的横坐标
     */
    private int dx;
    /**
     * 目标的纵坐标
     */
    private int dy;
    /**
     * 用来存储邻接矩阵
     * 就是地图
     */
    private int data[][];
    /**
     * 用来标记数据，走过的点，不能再重复入BFS的队列，避免死循环
     */
    private boolean mark[][];


    /**
     * 构造函数
     */
    public BFS(int row, int col, int dx, int dy, int data[][], boolean mark[][]) {
        n = row;
        m = col;
        this.dx = dx;
        this.dy = dy;
        this.data = data;
        this.mark = mark;
    }

    /**
     * 找寻过程函数
     * 思路就是我们将当前点的相邻的节点全部入队列，依次从队列中取值，然后循环这个操作，直至队列为空，这就是BFS（广度优先）遍历全部图的节点
     * @param x X表示自己当前位置的横坐标
     * @param y y表示自己当前位置的纵坐标
     */
    public void bfs(int x, int y) {
        // 判断是否当前位置越界
        if (x < 1 || x > n || y < 1 || y > m) {
            // 表示当前已经下标越界
            return;
        }
        // 判断是否当前自己的位置就是目标的位置
        if (x == dx && y == dy) {
            System.out.println("当前位置就是目标位置: X: " + x + ", Y: " + y);
            return;
        }
        // 将当前自己的节点进行标记，下次不会再进行处理
        mark[x][y] = true;
        // 声明一个广度遍历的队列（BFS就是借助队列实现的）,队列的大小是邻接矩阵的长乘宽
        Queue<Point> queue = new ArrayBlockingQueue<>(n * m);
        // 将自己当前的位置封装成Point对象
        Point start = new Point();
        start.x = x;
        start.y = y;
        // 将自己现在这个节点添加到BFS的队列中
        queue.add(start);
        // 这个是个经典，以后都可以考虑，因为我们是用二维数组对其进行存储，且我们只能上下左右走，无法斜着走，所以我们应该四个方向进行判断
        // 这里定义了一个二维数组，这四个元素和我们当前的位置的横纵坐标相加，就会得到我们上下左右的点
        int next[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        // 开始遍历队列，若当前队列中不为空继续循环
        while (!queue.isEmpty()){
            // 取出队列中的第一个元素
            Point point = queue.poll();
            // 开始对当前节点的上下左右节点的处理，将其入队列，利用BFS遍历
            for (int i = 0; i < 4; i++) {
                // 新的横坐标
                int nextx = point.x + next[i][0];
                // 新的纵坐标
                int nexty = point.y + next[i][1];
                // 判断新的位置的横纵坐标是否越界
                if (nextx < 1 || nextx > n || nexty < 1 || nexty > m){
                    continue;
                }
                // data中的值若是1 表示障碍物，不能走
                // 还要判断是否该点已经被标记，如果标记也不用走，避免重复入队，死循环
                if (data[nextx][nexty] == 0 && !mark[nextx][nexty]) {
                    // 此时是表示可以继续走
                    // 判断是否已经到达目标点
                    if (nextx == dx && nexty == dy) {
                        System.out.println("已经找到目标位置: X: " + nextx + ", Y: " + nexty);
                        return;
                    }
                    // 赋值新的Point
                    Point newPoint = new Point();
                    newPoint.x = nextx;
                    newPoint.y = nexty;
                    // 将当前节点进行标记，避免下次重复入队列
                    mark[nextx][nexty] = true;
                    // 入队
                    queue.add(newPoint);
                }
            }
        }

        System.out.println("无法找到目标点");
        return;
    }
	/**
	 * 我的思路， 
	 */
	public void bfs(Pointer pointer) {
		ArrayBlockingQueue<Pointer> queue = new ArrayBlockingQueue<Pointer>(n * m);
		queue.add(pointer);
		mark[pointer.x][pointer.y] = true;
		while (!queue.isEmpty()) {
			Pointer point = queue.poll();
			// 向下走
			if (point.x + 1 < m && point.y < n && data[point.x + 1][point.y] == 0 && !mark[point.x + 1][point.y]) {
				mark[point.x + 1][point.y] = true;
				if (point.x + 1 == dy && point.y == dx) {
					System.out.println("向下走： " + new Pointer(point.x+1,point.y));
					return;
				}
				queue.add(new Pointer(point.x + 1, point.y));
			}
			// 向上走
			if (point.x - 1 > 0 && point.y < n && data[point.x - 1][point.y] == 0 && !mark[point.x - 1][point.y]) {
				mark[point.x - 1][point.y] = true;
				if (point.x - 1 == dy && point.y == dx) {
					System.out.println("向上走： " + new Pointer(point.x-1,point.y));
					System.out.println(Arrays.asList(mark));
					return;
				}
				queue.add(new Pointer(point.x - 1, point.y));
			}
			// 向右走
			if (point.y + 1 < n && point.x < m && data[point.x][point.y + 1] == 0 && !mark[point.x][point.y + 1]) {
				mark[point.x][point.y + 1] = true;
				if (point.x == dy && point.y + 1 == dx) {
					System.out.println("向右走： " + new Pointer(point.x,point.y + 1));
					return;
				}
				queue.add(new Pointer(point.x, point.y + 1));
			}
			// 向左走
			if (point.y - 1 > 0 && point.x < m && data[point.x][point.y - 1] == 0 && !mark[point.x][point.y - 1]) {
				mark[point.x][point.y - 1] = true;
				if (point.x == dy && point.y - 1 == dx) {
					System.out.println("向左走： " + new Pointer(point.x,point.y - 1));
					return;
				}
				queue.add(new Pointer(point.x, point.y - 1));
			}
		}
	}


    /**
     * 主函数，用来测试
     * @param args
     */
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = 5;
        int m = 4;

        // 新建BFS的队列
        // 加1是因为我们不用0有关的格子，我们相当于横纵坐标从1开始
        int data[][] = new int[n+1][m+1];
        // 初始化标记数组
        boolean mark[][] = new boolean[n+1][m+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                data[i][j] = cin.nextInt();
            }
        }

        // 输入目标点
        int dx = cin.nextInt();
        int dy = cin.nextInt();

        // 赋值我们输入的起始和终止
        int x = cin.nextInt();
        int y = cin.nextInt();

        BFS bfs = new BFS(n, m ,dx, dy, data, mark);
        bfs.bfs(x, y);
    }

}

/**
 * 定义一个下标类，其中里面就两个属性 X Y
 * 该类用来表示当前的位置
 */
class Point{

    /**
     * 横坐标
     */
    int x;

    /**
     * 纵坐标
     */
    int y;
}

解救美女2（DFS深度度优先算法解决）

有一天，小美和你去玩迷宫，但是方向感不好的小美很快就迷路了，你得知之后便去营救，你已经弄清楚了迷宫的地图，现在要求你以最快的速度去解救小美，你能计算出最快需要几步么？以及求出其最快的路径

使用DFS深度优先算法解决

  • 1表示地图上的障碍物，0表示有路可以走

  • 邻接矩阵（二维数组）：

    0(你) 0 1 0

    0 0 0 0

    0 0 1 0

    0 1 0(小美) 0

    0 0 0 1

代码

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package com.lhb.test;

import com.alibaba.fastjson.JSONObject;

import java.util.*;

/**
 * - 有一天，小美和你去玩迷宫，但是方向感不好的小美很快就迷路了，你得知之后便去营救，你已经弄清楚了迷宫的地图，现在要求你以最快的速度去解救小美，你能计算出最快需要几步么？以及求出其最快的路径
 *
 * - 1表示地图上的障碍物，0表示有路可以走
 * - 邻接矩阵（二维数组）：
 *
 * 0（你） 0 1 0
 * 0         0 0 0
 * 0 0 1 0
 * 0 1 0（小美） 0
 * 0 0 0 1
 */
 
class Point {

	int x;
	int y;
}

public class DFS {
    /**
     * 用来表示地图总共有几行
     */
    private int n;
    /**
     * 用来表示地图总共有几列
     */
    private int m;
    /**
     * 目标的横坐标
     */
    private int dx;
    /**
     * 目标的纵坐标
     */
    private int dy;
    /**
     * 用来存储邻接矩阵
     * 就是地图
     */
    private int data[][];
    /**
     * 用来标记数据，走过的点，不能再重复入BFS的队列，避免死循环
     */
    private boolean mark[][];
    /**
     * 用来保存最小的步数 初始值设置为最大，求最小
     */
    private int minStep = Integer.MAX_VALUE;
    /**
     * 这个是个经典，以后都可以考虑，因为我们是用二维数组对其进行存储，且我们只能上下左右走，无法斜着走，所以我们应该四个方向进行判断
     * 这里定义了一个二维数组，这四个元素和我们当前的位置的横纵坐标相加，就会得到我们上下左右的点
     */
    private int next[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    /**
     * 用来保存当前路线的路径
     */
    Stack<Point> stack = new Stack<>();
    /**
     * 用来保存所有的路径 其key是步数，value是list，因为可能有多种最短路径的实现
     */
    Map<Integer, List<Stack<Point>>> result = new HashMap<>();

    /**
     * 构造函数
     */
    public DFS(int row, int col, int dx, int dy, int data[][], boolean mark[][]) {
        n = row;
        m = col;
        this.dx = dx;
        this.dy = dy;
        this.data = data;
        this.mark = mark;
    }


    /**
     * DFS深度遍历，通过深度遍历可以找到最小的步数，以及最小的路径
     * @param x 当前自己的位置的横坐标
     * @param y 当前自己的位置的纵坐标
     * @param step 当前已经走了多少步
     */
    public void dfs(int x, int y, int step) {
        // 判断当前的位置是否就是目标位置
        if (x == dx && y == dy) {
            if (!result.containsKey(step)) {
                result.put(step, new ArrayList<>());
            }
            result.get(step).add((Stack<Point>) stack.clone());
            // 如果是当前的位置，判断这次找到目标的步数是否比我们设置的最小的步数小
            if (step < minStep) {
                minStep = step;
            }
            // 退出递归
            return;
        }

        // 循环走四周的节点，上下左右
        for (int i = 0; i < 4; i++) {
            // 下一个位置的横坐标
            int nextx = x + next[i][0];
            // 下一个位置的纵坐标
            int nexty = y + next[i][1];
            // 判断是否下一个位置超过了二维数组的边界
            if (nextx < 1 || nextx > n || nexty < 1 || nexty > m) {
                continue;
            }
            // 判断其下一个位置是否可以走，即判断下一个位置是否是障碍物 0不是 1 是
            // 判断下一个位置是否已经标记，已经标记的不能走
            if (data[nextx][nexty] == 0 && !mark[nextx][nexty]) {
                // 如果此时完全正常 下一个位置可以走，则将其标志位先改为true
                mark[nextx][nexty] = true;
                Point point = new Point();
                point.x = nextx;
                point.y = nexty;
                // 将当前下标保存到栈中
                stack.push(point);
                // 递归往下一个走，直到找到为止
                dfs(nextx, nexty, step + 1);
                // 回溯，将当前的标志位取掉，因为我们回溯要假设这个位置没有走过
                mark[nextx][nexty] = false;
                // 因为回溯所以需要出栈
                stack.pop();
            }
        }
    }


    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = 5;
        int m = 4;

        int[][] data = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                data[i][j] = cin.nextInt();
            }
        }
        int dx = cin.nextInt();
        int dy = cin.nextInt();

        boolean[][] mark = new boolean[n + 1][m + 1];
        int x = cin.nextInt();
        int y = cin.nextInt();

        // 我的起始位置标记位true
        mark[x][y] = true;
        DFS dfs = new DFS(n,m,dx,dy,data,mark);
        dfs.dfs(x,y,0);
        System.out.println("最小步数是：" + dfs.minStep + "；一共有"+dfs.result.get(dfs.minStep).size()+"种方案到达目标");

        List<Stack<Point>> stacks = dfs.result.get(dfs.minStep);
        for (Stack<Point> stack: stacks) {
            for (Point point : stack) {
                System.out.print("->(" + point.x + "," + point.y + ")");
            }
            System.out.println();
        }
    }
}

深度优先代码运行结果

图的应用

  • 知识图谱：推荐算法，数据挖掘
  • 社交网络：QQ推荐好友功能
  • 图数据库：Neo4j
  • 路径问题：导航软件
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

请我喝杯咖啡吧~

支付宝
微信