锐客网

  1. 首页 > it技术 > >

数据结构与算法-图(Graph)

特点
一种更加复杂的非线性数据结构
名词解释
顶点(vertex): 图中的元素
边(edge): 图中的一个顶点可以与任意其他顶点建立连接关系
度(degree): 跟顶点相连接的边的条数
有向图: 边有方向的图
无向图: 边没有方向的图
入度(In-degree): 有多少条边指向这个顶点
出度(Out-degree): 有多少条边是以这个顶点为起点指向其他顶点
数据结构与算法-图(Graph)
文章图片
有向图 带权图(weighted graph): 在带权图中每条边都有一个权重(weight)
内存中存储图这种数据结构方法
1.邻接矩阵(Adjacency Matrix)存储
邻接矩阵的底层依赖一个二维数组
对于无向图来说，如果顶点i与顶点j之间有边，就将A[i][j]和A[j][i]标记为1；
对于有向图来说，如果有一条箭头从顶点i指向顶点j的边，就将A[i][j]标记为1；
同理，如果有一条箭头从顶点j指向顶点i的边，我们就将A[j][i]标记为1。
对于带权图，数组中就存储相应的权重
邻接矩阵存储方法 无向图中，adj[0][0]没边为0，adj[0][1]有边为1，adj[0][2]有边为1，adj[0][3]无边为0
总结
1.存储方式简单、直接，因为基于数组在获取两个顶点的关系非常高效
2.方便计算，可以将很多图的运算转换成矩阵之间的运算
比如求解最短路径问题的Floyd-Warshall算法，利用矩阵循环相乘若干次得到结果
3.比较浪费存储空间，特别针对稀疏图(Sparse Matrix): 顶点很多但每个顶点边不多
2.邻接表(Adjacency List)存储
每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点
有向图: 每个顶点对应的链表里面，存储的是指向的顶点
无向图: 每个顶点对应的链表里面，存储的是跟这个顶点有边相连的顶点
有向邻接表 总结
邻接表存储起来比较节省空间，但使用比较耗时
链表的存储方式对缓存不友好，查询两个顶点之间的关系不高效
邻接表升级(链表数据结构替换)
1.换成平衡二叉查找树(红黑树)，可以快速地查找两个顶点之间是否存在边了
2.换成其他动态数据结构: 跳表、散列表等
3.有序动态数组，可以通过二分查找的方法来快速定位两个顶点之间否是存在边
应用场景
例如: 存储微博(有向图)、微信(无向图)等社交网络中的好友关系
针对微博用户关系，假设我们需要支持下面这样几个操作：
判断用户A是否关注了用户B；
判断用户A是否是用户B的粉丝；
用户A关注用户B；
用户A取消关注用户B；
根据用户名称的首字母排序，分?获取用户的粉丝列表；
根据用户名称的首字母排序，分?获取用户的关注列表
因社交网络是一张稀疏图，所以采用邻接表来存储
具体用邻接表 + 逆邻接表来存储
邻接表中存储了用户的关注关系: 每个顶点的链表中，存储这个顶点指向的顶点
逆邻接表中存储了用户被关注关系: 每个顶点的链表中，存储指向这个顶点的顶点
邻接表 & 逆邻接表 邻接表不适合快速判断两用户之间关系，将链表改为支持快速查找的动态数据结构
因为需要按照用户名称的首字母排序，分?来获取用户的粉丝列表或者关注列表
用跳表最合适。因跳表插入、删除、查找时间复杂度是O(logn)，空间复杂度上是O(n)
最重要一点，跳表中存储的数据本来有序，分?获取粉丝列表或关注列表，非常高效
如果对于小规模的数据,可以将整个社交关系存储在内存中
如果数据规模太大，
方式一: 可以通过哈希算法等数据分片方式，将邻接表存储在不同的机器上
查询顶点之间关系时，先用同样哈希算法定位顶点所在机器，再在相应机器上查找
采用数据分片方式存储 方式二: 利用外部存储(例如:硬盘)
例如: 数据库存储方式: 为了高效地支持前面定义的操作，可以在表上建立多个索引
总结
概念：无向图、有向图、带权图、顶点、边、度、入度、出度
存储方式：邻接矩阵和邻接表
邻接矩阵存储方法的缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算
邻接表存储方式比较节省存储空间，但链表不方便查找，查询效率没有邻接矩阵高
改进升级: 将链表换成更加高效动态数据结构，比如平衡二叉查找树、跳表、散列表等
搜索算法
算法是作用于具体数据结构之上，深度优先和广度优先搜索算法都是基于“图”这种数据结构
图数据结构的表达能力很强，大部分涉及搜索的场景都可以抽象成“图”
图上的搜索算法，最直接的理解: 在图中找出从一个顶点出发，到另一个顶点的路径
包括: 深度优先、广度优先搜索、启发式搜索
深度优先搜索算法和广度优先搜索算法，既可以用在无向图，也可以用在有向图上
public class Graph { //无向图
private int v; //顶点的个数
private LinkedList adj[]; //邻接表
public Graph(int v) {
this.v = v;
adj = new LinkedList[v];
for (int i=0; i adj[i] = new LinkedList<>();
}
}
public void addEdge(int s, int t) { //无向图一条边存两次
adj[s].add(t);
adj[t].add(s);
}
}
广度优先搜索(Breadth-First-Search)
一种“地毯式”层层推进搜索策略，先查找离起始顶点最近的，然后是次近的，依次往外搜索
BFS搜索算法分解图(无向图) bfs()函数就是基于之前定义的，图的广度优先搜索的代码实现。
其中s表示起始顶点，t表示终止顶点。我们搜索一条从s到t的路径。
实际上，这样求得的路径就是从s到t的最短路径
public void bfs(int s, int t) {
if (s == t) return;
boolean[] visited = new boolean[v];
visited[s]=true;
Queue 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用来记录已经被访问的顶点，如果顶点q被访问，那相应的visited[q]会被设置为true
queue是队列，用来存储已经被访问但相连的顶点还没有被访问的顶点来实现记录的功能
prev用来记录搜索路径。当我们从顶点s开始搜索到顶点t后，prev数组中存储的是搜索路径
这个路径是反向存储的，prev[w]存储的是，顶点w是从哪个前驱顶点遍历过来的
广度优先搜索分解图1 广度优先搜索分解图2 时间复杂度
最坏情况下，终止顶点t离起始顶点s很远，需要遍历完整个图才能找到
这时每个顶点都要进出一遍队列，每个边也都会被访问一次，所以时间复杂度是O(V+E)
其中V表示顶点的个数，E表示边的个数，因E>=V，所以可以简写为O(E)
空间复杂度
空间消耗主要在几个辅助变量visited数组、queue队列、prev数组上。
这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度为O(V)
深度优先搜索(Depth-First-Search)

用的是一种比较著名的回溯思想，这种思想解决问题的过程非常适合用递归来实现
深度优先搜索策略
从一个顶点随意选择一个路径往下搜索，当无法继续时回退上一个顶点，
换一条边继续，直到找到目标顶点为止
数据结构与算法-图(Graph)
文章图片
深度优先搜索策略 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);
}
}
}
代码实现用到prev、visited变量以及print()函数，跟广度优先搜索代码实现里作用是一样
有个特殊变量found，作用是当我们已经找到终止顶点t之后，就不再递归地继续查找
时间复杂度
每条边最多会被访问两次，一次是遍历，一次是回退
时间复杂度是O(E)，E表示边的个数
空间复杂度
消耗内存主要是visited、prev数组和递归调用栈
visited、prev数组大小跟顶点个数V成正比，递归调用栈最大深度不会超过顶点的个数
所以总空间复杂度为O(V)
总结
广度优先搜索和深度优先搜索是图上的两种最常用、最基本的搜索算法
比起其他高级的搜索算法,比如A*、IDA*等，要简单粗暴，所以也被叫作暴力搜索算法
这两种搜索算法仅适用于状态空间不大，也就是说图不大的搜索
广度优先搜索
通俗来讲: 地毯式层层推进，从起始顶点开始，依次往外遍历
广度优先搜索需要借助队列来实现，遍历得到的路径就是起始顶点到终止顶点的最短路径
时间复杂度都是O(E)，空间复杂度是O(V)
深度优先搜索
用的是回溯思想，非常适合用递归实现
深度优先搜索是借助栈来实现的
【数据结构与算法-图(Graph)】时间复杂度都是O(E)，空间复杂度是O(V)

    推荐阅读


    上一篇：6.从尾到头打印链表

    下一篇：你说我不文艺，把我憋成内伤