图的学习总结

1 什么是图？

图是一种更加复杂的非线性表结构。树中的元素我们称为节点，图中的元素我们就叫做顶点（vertex）。图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫做边（edge）。

拿微信举例子，我们可以把每个用户看作一个顶点。如果两个用户之间互加好友，那就在两者之间建立一条边。所以，整个微信的好友关系就可以用一张图来表示。

图 1

2 什么是有向图和无向图？

微信是双向关注，而微博是允许单向关注的，用户 A 关注了用户 B，但用户 B 可以不关注用户 A。得到的知识城邦也是这样。所以就引入了边的“方向”的概念。

我们把边有方向的图叫做“有向图”。而把边没有方向的图就叫做“无向图”。

3 什么是度以及什么是入度和出度？

度（degree），就是跟顶点相连接的边的条数。

在有向图中，把度分为入度（In-degree）和出度（Out-degree）。

顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。微博的例子，入度就表示有多少粉丝，出度就表示关注了多少人。

4 什么是带权图？

每条边都有一个权重（weight），比如，我们可以通过这个权重来表示 QQ 好友间的亲密度。

图 4

5 如何存储一个图？

5.1 邻接矩阵存储方法

无向图存储方法：底层依赖一个二维数组，如果顶点 i 与顶点 j 之间有边，我们就将 A[i][j]和 A[j][i]标记为 1；

有向图存储方法：同样底层依赖一个二维数组，如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，则 A[i][j]标记为 1。同理，如果有一条箭头从顶点 j 指向顶点 i 的边，则 A[j][i]标记为 1。对于带权图，数组中就存储相应的权重。

优点：

ü 存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。

ü 方便计算。这是因为，用邻接矩阵的方式存储图，可以将很多图的运算转换成矩阵之间的运算。

缺点：

ü 浪费存储空间，如果我们存储的是稀疏图（Sparse Matrix），也就是说，顶 点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。

图 5

5.2 邻接表存储方法

存储方法：基于链表存储每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。

优点：

ü 节省存储空间

缺点：

ü 使用起来比较耗时

改进方法：

ü 将邻接表中的链表改成平衡二叉查找树。实际开发中，我们可以选择用红黑树。这样，我们就可以更加快速地查找两个顶点之间是否存在边了

ü 将链表改成有序动态数组，可以通过二分查找的方法来快速定位两个顶点之间否是存在边。

图 6

6 图的应用和实现？

6.1 图的应用-什么是 BFS、DFS？

图可以表示社交网络中用户之间的连接关系，算法是作用于具体数据结构之上的，深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构的。这是因为，图这种数据结构的表达能力很强，大部分涉及搜索的场景都可以抽象成“图”。

BFS：广度优先搜索（Breadth-First-Search），简称 BFS。直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

DFS：深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是“走迷宫”。

6.2 图的代码实现

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 + " ");}

DFS 的代码实现

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);    }  }}

参考自《数据结构与算法之美》专栏学习