图的表示
图(Graph)相关的定义:
- 顶点(Vertex):图中的元素
- 边(Edge):一个顶点可以与其他任意顶点建立连接关系,这种连接关系叫做边
- 度(Degree):跟顶点相连接的边的条数叫做顶点的度
用箭头代表边的方向,边有方向的图叫做有向图,没有方向的图叫做无向图
无向图的示意图如下:
有向图的示意图如下:
在有向图中,度分为:
- 入度(In-degree):表示有多少边指向这个顶点
- 出度(Out-degree):表示有多少边是以这个顶点为起点指向其他顶点
带权图(Weighted Graph):在图中每条边都有一个权重(Weight),可以用权重来表示QQ好友间的亲密度,示意图如下:
图的存储方法
邻接矩阵 Adjacency Matrix
图最直观的存储方式就是邻接矩阵,利用一个二维数组表示,示意图如下:
邻接矩阵表示比较浪费存储空间:
- 对于无向图,将其按照对角线划分为上下两部分,只需存储其中一部分即可
- 稀疏图(Sparse Matrix):顶点很多,但是每个顶点的边并不多,邻接矩阵中将会有很多的空点
邻接矩阵的优点是存储方式简单、直接,因为基于数组,所以在获取两个顶点的关系时,非常高效;可以利用邻接矩阵将图的运算转换成矩阵之间的运算,比如求解最短路径问题时会提到一个Floyd-Warshall算法,就是利用矩阵循环相乘若干次得到结果。
邻接表 Adjacency List
邻接表中每个顶点对应一条链表,链表中存储的是与这个顶点相连接的其他顶点,下图是有向图额邻接表存储方式,每个顶点对应的链表里边,存储的是指向的顶点。对于无向图来说,每个顶点的链表里边存储的是与这个顶点相连的顶点。
在邻接表中查询两个顶点之间的关系不高效,因为要遍历相应顶点的链表,而链表是非连续存储的,对缓存不够友好。
可以将邻接表中的链表改进为平衡二叉查找树,实际开发中可以选择红黑树,也可以换成其他动态数据结构,如跳表、散列表等。或者改为有序动态数组,这样可以通过二分查找法来快速定位两个顶点之间是否存在边。
如何存储微博、微信等社交网络中的好友关系
由于社交关系通常是稀疏的,使用邻接矩阵会浪费空间,因此使用用一个邻接表存储用户的关注关系,使用一个逆邻接表存储用户的被关注关系,示意图如下:
基础邻接表中的链表查询太慢,可以改为高效的动态数据结构,用跳表可以实现高效的按照用户名称的首字母排序,分页来获取用户的粉丝列表或者关注列表,因为跳表中的数据已经是有序的了。
对于用户量少的社交网络,可以直接将邻接表存储到内存中,但是对于微博、微信等过亿的用户,数据规模太大,无法全部存储。解决方法是通过哈希算法等数据分片的方式,将邻接表存储在不同的机器上,示意图如下:
当要查询顶点与顶点关系时,利用同样的哈希算法,先定位顶点所在机器,然后再在相应的机器上查找即可。
另一种存储方式是数据库存储,数据库是用来持久化存储关系数据的,示意图如下:
微信社交关系的存储方式不同点是:微信是无向图,仅需要一个邻接表即可。
图相关的算法
在社交网络中,有一个六度分割理论:你与世界上的另一个人间隔的关系不会超过六度,也就是说平均6步就可以联系到任何两个互不相识的人。
无向图的代码实现:
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),简称为BFS,是一种地毯式层层推进的搜索策略,即先查找离起始点最近的,然后次近的,依次往外搜索,示意图如下:
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);
}
}
}
}
private void print(int[] prev, int s, int t) { // 递归打印 s->t 的路径
if (prev[t] != -1 && t != s) {
print(prev, s, prev[t]);
}
System.out.print(t + " ");
}
代码中:
- Visited: 用来记录已经被访问的顶点,用来避免顶点被重复访问
- Queue是一个队列,用来存储已经被访问、但相连的顶点还没有被访问的顶点
- prev用来记录搜索路径。这个路径是反向存储的。prev[w]存储的是,顶点w是从哪个前驱顶点遍历过来的
示意图如下:
最快情况下,终止顶点t离起始顶点s很远,需要遍历完这两个图才能找到,这个时候,每个顶点都要进出一遍队列,每个边也都会被访问一次,所以BFS的时间复杂度树O(V+E),V表示顶点个数,E表示边的个数。对于连通图来说,所有顶点都是连通的,E肯定大于等于V-1,所以BFS的时间复杂度可以简写为O(E)。BFS的空间复杂度是O(V)。
深度优先搜索 DFS
深度优先搜索(Depth-First-Search),简称DFS,示意图如下:
从图中可以看出来,深度优先搜索找出来的路径,并不是顶点s到顶点t的最短路径。
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);
}
private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
if (found == true) 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);
}
}
}
从上图可以看出,每条边最多被访问两次,一次遍历,一次回退,所以DFS的时间复杂度是O(E),E表示边的个数。空间复杂度是O(V)。
如何找出社交网络中某个用户的三度好友关系
利用广度优先搜索先遍历用户的一度好友,然后遍历用户的二度好友,最后遍历用户的三度好友。DFS和BFS简单粗暴,是暴力搜索算法,适用于状态空间不大,图不大的搜索。
DFS与BFS小结
BFS需要借助队列来实现,遍历得到的路径是起始顶点到终止顶点的最短路径,DFS是回溯思想,利用递归或者栈来实现,两者的时间复杂度都是O(E),空间复杂度是O(V)。
注:本文是《数据结构与算法之美》的读书笔记,配套代码地址GitHub。本文仅限个人学习,请勿用作商业用途,谢谢。
Note: Cover Picture