数据结构与算法-图

图的表示

图(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