图的表示
图(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