写点什么

图的学习总结

用户头像
Nick
关注
发布于: 6 小时前
图的学习总结

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); } }}
复制代码

 

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

发布于: 6 小时前阅读数: 2
用户头像

Nick

关注

终身学习,向死而生 2020.03.18 加入

得到、极客时间重度学习者,来infoQ 是为了输出倒逼输入

评论

发布
暂无评论
图的学习总结