数据结构与算法(15)_图

发表于 | 分类于

如何理解图

图是一种 非线性表数据结构,和树比起来,更加复杂.图中的元素我们叫做顶点.图中的一个顶点与任意其他顶点建立连接关系,我们把建立的关系叫做边.

社交网络就是一个非常典型的图结构.以微信举例,把每个用户看成一个顶点.如果两个用户加好友,那就在两者之间建立一条边.所以,整个微信的好友关系就可以用一张图来表示.其中每个用户有多少好友,对应到图中,就叫做顶点的度,就跟顶点相连的边的条数.

我们可以把上边的图结构改造一下,引入边的”方向”的概念.我们把这种边有方向的图叫做“有向图”,边没有方向的叫做“无向图”.

在有向图中,把度分为入度和出度.顶点的入度表示有多少条边指向这个顶点;顶点的出度表示有多少条边以这个顶点为起点指向其他顶点.

如果边带有权重,那这种图就叫做带权图,例如QQ好友的亲密度.

存储图

邻接矩阵存储

图最直观的一种存储方法就是,邻接矩阵.

邻接矩阵的底层依赖的是一个二维数组.对于无向图来说,如果顶点i与顶点j之间有边,我们就将 A[i][j] 和 A[j][i] 标记为 1; 对于有向图来说,如果有一条箭头从顶点 i 指向顶点 j 的边,那我们就将 A[i][j] 标记为 1 . 同理,如果有一条箭头从顶点 j 指向顶点 i 的边,那我们就将 A[j][i] 标记为1. 对于权重图,数组中就存储响应的权重.

用邻接矩阵表示一个图,虽然简单直观,但是比较浪费内存空间.

对于无向图来说,如果 A[i][j] 为1, 那么 A[j][i] 也肯定等于 1.实际上我们只需要存储一个就可以了.

如果我们存储的是稀疏图,也就是说顶点很多但每个顶点的边不多,那邻接矩阵的存储方法就更加浪费空间了.

邻接表存储

邻接表存储方式如图.每一个顶点都对应一条链表,链表中存储的是与这个顶点相连的其他点.图中画的是一个有向图,每个顶点对应的链表里面,存储的是指向的顶点.

//TODO 图33

邻接表存储比较节省空间,但是使用起来就比较耗时.但是我们可以将链表改成平衡二叉树.实际开发中,还可以选择红黑树.这样我们就可以更快的查找两个顶点之间是否存在边.

深度和广度优先搜索

在社交网络中有一个六度分割理论,具体的说,你与世界上的另一个的间隔的关系不会超过六度,也就是说平均只需要六步就可以联系到任何两个不认识的人.

一个用户的一度链接用户,就是他的好友.二度链接用户就是他好友的好友.三度链接好友就是他好友的好友的好友.在社交网络中,我们往往通过用户之间的链接关系,来实现推荐”可能认识的人”这么一个功能.

什么是”搜索”算法

算法是作用于具体数据结构上的,深度优先搜索算法和广度优先搜索算法都是基于”图”这种数据结构.这是因为,图这种数据结构表达能力很强,大部分设计搜索的场景都可以抽象成图.

图上的搜索算法,最直接理解的就是,在图中找出从一个顶点出发,到另一个 顶点的路径.具体方法有很多.比如最”暴力”的深度优先,广度优先,还有A, IDA 等启发式搜索算法.

今天我们会用邻接表来存储图.深度优先和广度优先算法既可以用在无向图,可以用在有向图上.今天都是以无向图来讲解.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//无向图
public class Graph{
	private int v; //顶点个数
	private LinkedList<Integer> adj[]; //邻接表

	public Graph(int v){
		this.v = v;
		adj = new LinkedList[v];
		for(int i=0; i<v; i++){
			adj[i] = new LinkedList<>();
		}
	}

	public void addEdge(int s, int t){ //无向图一条边存两次
		adj[s].add(t);
		adj[t].add(s);
	}
}

广度优先搜索 (BFS)

广度优先搜索(Breadth-First-Search),它就是一种”地毯式”层层推进的搜索策略,即先查找离起始顶点最近的,然后是次近的,依次往外搜索.如图

//TODO 图34

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
public void bfs(int s, int t){
	if(s == t) return;
	boolean[] visited = new boolean[v];
	visited[s] = true;
	Queue<Integer> queue = new LinkedList<>();
	queue.add(s);
	int[] prev = new int[v];
	for(int i=0; i<v; i++){
		prev[i] = -1;
	}

	while(queue.size() != 0){
		int w = queue.poll();
		for(int i=0; i < adj[w].size(); i++){
			int q = adj[w].get(i);
			if(!visited[q]){
				prev[q] = w;
				if(q == t){
					print(prev, s, t);
					return;
				}
				visited[q] = true;
				queue.add(q);
			}
		}	
	}
}

//递归打印s->t的路径
private void print(int[] prev, int s, int t){
	if(prev[t] != -1 && t != s){
		print(prev, s, prev[t]);
	}
	System.out.print(t + " ");
}

这里的bfs()方法就是图的广度优先搜索的代码实现,其中s表示起始顶点,t 表示终止顶点.我们搜索一条s到t 的路径.实际上这样求得的路径就是最短路径.

这段代码里有三个重要的变量 visited, queue, prev.

visited是用来标记已经访问到的顶点,用来避免重复访问.

queue是一个队列,用来存储已经被访问,但相连的顶点还没有被访问的顶点.因为广度优先是逐层访问的,也就是说我们只有把第k层的顶点都访问完成之后,才能访问第k + 1 层的顶点.当我们访问到第k层顶点的时候,我们需要把第看层的顶点记录下来稍后才能通过k层顶点来找k+1层的顶点.

prev用来记录搜索路径.当我们从s点开始,广度优先搜索到t后,prev中存储的就是搜索路径.不过这个路径是反向存储的.prev[w] 存储的是,顶点w是从哪个前驱顶点遍历过来的.比如当我们通过顶点2的邻接表访问到顶点3,那prev[3]就等于2.为了正向打印出路径,我们需要递归来打印.

广度优先分解图如下:

//TODO 图35,36,37

最坏情况下终止顶点t 离起始顶点 s 很远,需要遍历整个图才能找到.这个时候每个顶点都要进出一遍队列,每个边也会被访问一次,所以广度搜索的时间复杂度是O(V+E).其中V表示顶点个数,E表示边的个数.对于一个连通图来说,也就是说一个图中所有顶点都是连通的,E肯定要大于等于V-1,所以说时间复杂度也可以简写为O(E).

广度优先搜索的空间消耗主要在visited数据,queue队列,prev数组上,这三个存储的空间的大小不会超过顶点个数,所以空间复杂度是O(V).

深度优先搜索(DFS)

深度优先搜索,最直观的例子就是走迷宫.

//TODO 图38

搜索的起始顶点是 s ,终止顶点是 t ,我们希望从图中找到一条顶点 s 到 顶点 t 的路径.我用深度递归算法把整个搜索路径标记出来了.这里面实线箭头表示遍历,虚线箭头表示回退.

实际上深度优先算法是一种比较著名的算法思想,回溯思想.这种思想解决问题的过程非常适合用递归来实现.

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
boolean found = false; // 全局变量或者类成员变量

public void dfs(int s, int t){
	found = false;
	boolean[] visited = new boolean[v];
	int[] prev = new int[v];
	for(int i=0; i<v; i++){
		prev[i] = -1;
	}
	recurDfs(s, t, visited, prev);
	print(prev, s, t);
}

public void recurDfs(int w, int t, boolean[] visited, int[] prev){
	if(found) return;
	visited[w] = true;
	if(w == t) {
		found = true;
		return;
	}
	for(int i=0; i<adj[w].size(); i++){
		int q = adj[w].get(i);
		if(!visited[q]){
			prev[q] = w;
			recurDfs(q, t, visited, prev);
		}
	}
}

深度优先算法代码实现也用到了 visited, prev 变量,它们跟广度优先算法中的作用是一样的.不过深度优先算法有个一个特殊变量found,用来标识是否找到终点 t ,然后结束递归.

深度优先算法的时间复杂度是O(E).空间复杂度是O(V).