43. | 拓扑排序：如何确定代码源文件的编译依赖关系 - 开始
- 编译器如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序：
使用 '图' 这种数据结构的 '拓扑排序算法' 解决. - 什么是拓扑排序
- 多个元素,部分或全部元素的两两依赖关系已经确定,如何安排一个序列,能够满足上述元素的两两依赖关系.
-
很多时候,拓扑排序的序列不是唯一的,因为可能不是所有元素之间都具有依赖关系.
c26d0f472d9a607c0c4eb688c01959bd[1].jpg
- 拓扑排序的原理很简单,重要的是拓扑排序的实现.
- 如何确定代码源文件的编译依赖关系:
- 把源文件和源文件之间的依赖关系,抽象成1个有向图;
- 每个源文件对应图中的一个顶点;
- 源文件之间的依赖关系就是顶点之间的边;
- 如果A先于B执行,或者说B依赖于A,就在A和B之间,构建一条从A指向B的的边;
- 注意这个图必须是一个有向无环图. 因为图中一旦成环,拓扑排序就无法工作;
- 拓扑排序本身就是基于有向无环图的一个算法.
public class Graph {
//定义顶点的个数
private int v;
//每个顶点对应一个邻接表, 多个顶点构邻接表数组
private LinkeList<Integer>[] adj;
//构造函数
public Graph(int v){
this.v = v;
adj = new LinkedList<Integer>[v];
for(int i=0; i<v; i++){
adj[i] = new LinkedList<Integer>();
}
}
//s优先于t / t依赖于s
//从顶点s出发,构建一条指向t的边
public void addEdge(int s, int t){
adj[s].add(t);
}
}
- 如何在Graph这个有向无环图上,实现拓扑排序,有2种算法: Kahn算法 和 DFS深度优先搜索算法.
- 看Kahn算法 和 DFS深度优先搜索算法 之前,首先回顾下之前的'图'相关知识.
43前置知识: 图
- 图
- 图是一种非线性表数据结构.
- 图中的每个元素叫做顶点.
- 图中的1个顶点可以与其他任意顶点进行连接,连接叫做边.
- 有向图:
每条边都是有方向的.A->B:从A到B. B->A:从B到A. - 无向图:
每条边都是没有方向的.单纯代表A-B两个顶点建立连接. - 每个顶点有多少条边,叫做顶点的度.
- 有向图中,每个顶点有 入度 和 出度.
- 入度:有多少条边指向该顶点;
-
出度:从该顶点发出多少条边;
图
- 带权图
-
每条边都有1个权重/weight.
带权图
- 图的存储方法: 邻接矩阵 和 邻接表.
- 使用 邻接矩阵 存储图
- 邻接矩阵底层是1个二维数组.
- 对于有向图: 顶点i向顶点j发出一条边 , 则 A[i][j] = 1;
- 对于无向图: 顶点i和顶点j之间有边,则 A[i][j] 和 A[j][i] 都是1;
-
对于带权图: 数组元素存储连接的2个顶点之间的权重;
使用邻接矩阵存储图
练一下markdown中怎么画矩阵.
$$\begin{matrix}
A & B & C\\
D & E & F\\
G & H & I\\
\end{matrix}$$
无向图:
有向图:
带权图:
- 邻接矩阵的缺点: 浪费存储空间.
- 对于无向图,顶点i,j之间有边,需要A[i][j]和A[j][i]都存储为1,实际只存1个就够了.浪费了一半空间;
- 对于稀疏图.即顶点很多,但每个顶点的边不多,使用邻接矩阵就更加浪费存储空间.
- 比如微信十亿用户,但每个用户最多2000个好友.使用邻接矩阵会浪费绝大部分存储空间.
- 邻接矩阵的有点:
- 邻接矩阵基于数组,获取2个顶点的关系非常快;
- 临街矩阵存储图可以将很多图的运算,转换为矩阵之间的运算,效率很高.
-
使用 邻接表 存储图
使用邻接表存储图
- 邻接表存储图很像散列表.
- 每个顶点对应1条链表,存储与该顶点相连的其他顶点.
- 邻接表存储图 和 邻接矩阵存储图 比较:
- 相对于邻接数组节省空间,尤其是稀疏图场景.只有相连的顶点的边才会存储在对应顶点的链表中.
- 是用时间换空间,比如查询顶点A和顶点B是否相连,就要在A顶点对应的链表中遍历查询.
- 链表的存储对缓存不友好,所以链表中查询两个顶点之间的关系效率低.
- 可以将邻接表中的链表替换为支持快速查找的数据结构: 红黑树、跳表、有序动态数组,散列表
- 使用图,存储微博的用户之间关系
针对微博用户关系，假设我们需要支持下面这样几个操作：判断用户 A 是否关注了用户 B；判断用户 A 是否是用户 B 的粉丝；用户 A 关注用户 B；用户 A 取消关注用户 B；根据用户名称的首字母排序，分页获取用户的粉丝列表；根据用户名称的首字母排序，分页获取用户的关注列表。
public class Graph {
//微博系统中用户量
private int v;
//BestType用于指代特定的数据结构,用于替换链表,提升链表的查询效率
//followers用于存储每个用户关注的人
private BestType<Integer>[] followers;
//fans用户存储每个用户被哪些人关注
private BestType<Integer>[] fans;
public Graph(int v){
this.v = v;
followers = new BestType<Integer>[v];
fans= new BestType<Integer>[v];
for(int i=0; i<v; i++){
followers[i] = new BestType<Integer>();
fans[i] = new BestType<Integer>();
}
}
//用户a关注用户b
public void follow(User a, User b){
Integer aIndex = hash(a);
Integer bIndex = hash(b);
Integer aId = a.userId;
Integer bId = b.userId;
//将用户b的id添加到用户a对应的 关注的人 中
followers[aIndex].add(bId);
//将用户a的id添加到用户b对应的 粉丝 中
fans[bIndex].add(aId);
}
//用户a不再关注用户b
public void unfollow(User a,User b){
Integer aIndex = hash(a);
Integer bIndex = hash(b);
Integer aId = a.userId;
Integer bId = b.userId;
//将用户b的id从用户a对应的 关注的人 中删除
followers[aIndex].remove(bId);
//将用户a的id从用户b对应的 粉丝 中删除
fans[bIndex].remove(aId);
}
//BestType具体选择哪一种支持快速查询的数据结构: 跳表 .
//跳表插入、删除、查找都非常高效，时间复杂度是 O(logn)，空间复杂度上稍高，是 O(n)。
//最重要的一点，跳表中存储的数据本来就是有序的了，分页获取粉丝列表或关注列表，就非常高效
}
- 深度优先搜索算法 和 广度优先搜索算法 , 都是基于 '图' 这种数据结构.
- 广度优先搜索/BFS/Breadth-First-Search
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);
}
}
- 广度优先搜索,就是先查找离起始顶点最近的,然后是次近的,一层层往外搜索.
- 从顶点s出发,搜索一条从s到t的最短路径.
private void bfs(int s, int t){
if(s == t){
//同一顶点不用继续搜索
return;
}
//记录指定顶点是否访问过
boolean[] visited = new boolean[v];
visited[s] = true;
//保存每个访问过的顶点的前一顶点
int[] prev = new int[v];
for(int i=0;i<v;i++){
prev[i] = -1;
}
//保存待比较其后续顶点的顶点
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(s);
while(queue.size() > 0){
//获取当前顶点
int curr = queue.poll();
//遍历比较当前顶点的所有子顶点
for(int i = 0; i<adj[curr].size(); i++){
int c = adj[curr].get(i);
if(!visited[c]){
//标记当前子顶点 已被访问过
visited[c] = true;
//标记当前子顶点 的上一结点就是curr
prev[c] = curr;
//如果当前子顶点 就是 要寻找的最终顶点
if(c == t){
//打印整个搜索路径, 终止循环
printRouter(prev, s, t);
return;
}
queue.add(c);
}
}
}
}
private void printRouter(int[] prev, int start, int target){
if(prev[target] != -1 && target != start){
//继续打印 start 到 target之前1个元素的路径
printRouter(prev, start, prev[target]);
}
//打印当前元素
System.out.println("当前元素:" + target);
}
- 广度优先搜索算法的 时间复杂度,空间复杂度:
- 时间复杂度是O(V+E)
- V表示顶点的个数,E表示边的个数
- 对于1个连通图.即一个图中所有的顶点都是连通的图,E肯定大于V
- 所以广度优先搜索算法的时间复杂度简写为O(E)
- 空间复杂度的O(V)
- visited 数组,prev 数组,queue队列,这三个存储空间大小都不会超过顶点个数V.
- 所以其空间复杂度是O(V).
- 时间复杂度是O(V+E)
- 深度优先搜索 / DFS / Depth-First-Search
- 深度优先搜索算法,本质上就是回溯算法
- 每一步,都要n种走法,每一种走法都走一遍
- 回溯算法的套路
1: 整体问题最终值 存放在回溯方法体外;
2: 回溯方法中有判断终止条件 及 整体问题最终值修改逻辑;
3: 回溯方法中:
每一步都有n种走法;
都走一遍;
套路:
int bestValue = -1;
private void recur(int param, int bound){
if(shouldReturn(param, bound)){
if(shouldModifBest(param,bound)){
bestValue = **;
}
return;
}
//n种走法
recur(p1,bound);
***
recur(pn,bound);
}
调用方式:
int bestValue = -1;
recur(p1.bound);
sys: 最优解: + bestValue.
- 使用深度优先搜索算法寻找顶点s到顶点t的路径
private boolean found = false;
private void recurDfs(int curr, int target, boolean[] visited, int[] prev){
if(found){
//之前已经找到路径,避免重复执行
//终止条件
return;
}
visited[curr] = true;
if(curr == target){
//终止条件
//修改方法体外的变量
found = true;
return;
}
//获取n条可能走的路径
for(int i=0; i<adj[curr].size(); i++){
int c = adj[curr].get(i);
if(!visited[c]){
//之前没有遍历过该子顶点
prev[c] = curr;
//每一条可以走的路径,都走一次
recurDfs(c, target, visited,prev);
}
}
}
private testDFS(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)
//打印路径
printRouter(prev, s, t);
}
- 深度优先搜索算法/回溯算法 的时间复杂度 和 空间复杂度
- 遍历 + 回溯, 每条边最多访问2次: parent -> n个child; 每个child -> 包括parent在内的n个顶点.
- 时间复杂度是O(E). E是边数量
- 空间复杂度是O(V). 因为额外的visited ,prev 数量不超过V.
43. | 拓扑排序：如何确定代码源文件的编译依赖关系 - 继续
public class Graph{
private int v;
private LinkedList<Integer>[] adj;
public Graph(int v){
this.v = v;
this.adj = new LinkedList<Integer>[v];
for(int i=0;i<v;i++){
adj[i] = new LinkedList<Integer>();
}
}
//添加从顶点s到顶点t的一条边
//因为是依赖关系,所以是有向图
public void addEdge(int s, int t){
adj[s].add(t);
}
}
如何在有向无环图上,实现拓扑排序.
拓扑排序有2种实现方法: Kahn算法 及 DFS深度优先搜索算法.
- Kahn算法
- Kahn算法实际用的是贪心算法思想
- 顶点的入度为0,说明该顶点不依赖任何其他顶点,可以立即执行.
- Kahn实现步骤:
- 定义1个数组,统计图中所有顶点的入度,存储于该数组
- 定义1个队列,存储图中所有入度为0的顶点
- 从队列头部不断取入度为0的顶点,执行/打印.
- 将该顶点对应的所有子顶点的入度-1
- 若某个子顶点的入度变为0,则将该子顶点也加入队列
- Kahn代码实现
public void topoSortByKahn(){
int[] inDegree = new int[v];
for(int i = 0; i<v; i++){
for(int j=0;j<adj[i].size();j++){
int curr = adj[i].get(j);
inDegree[curr]++;
}
}
Queue<Integer> q = new LinkedList<Integer>();
for(int i=0;i<v;i++){
if(inDegree[i] == 0){
q.add(i);
}
}
int curr;
int child;
while(!q.isEmpty()){
curr = q.poll();
System.out.println("当前编译:" + curr);
for(int i=0;i<adj[curr].size();i++){
//遍历当前顶点的所有子顶点
child = adj[curr].get(i);
//每个子顶点的入度-1
inDegree[child ]--;
//若子顶点入度变为0
if(inDegree[child] == 0){
q.add(child);
}
}
}
}
- DFS算法
- DFS算法本质上是回溯算法
- 原始数据是 顶点->多个子顶点
- 要答应整个依赖关系,需要知道每个顶点都依赖哪些父顶点, 根据原始的 curr->children 构建逆邻接表 curr->parents
- 每次打印1个顶点,都要先保证其 parents 都打印完毕,再打印自身.
- DFS代码实现
public void dfsDeps(){
boolean[] visited = new boolean[v];
LinkedList<Integer>[] parents = new LinkedList<Integer>[v];
for(int i =0;i<v;i++){
parents[i] = new LinkedList<Integer>();
}
int child;
for(int i=0;i<adj.length;i++){
for(int j=0;j<adj[i].size();j++){
child = adj[i].get(j);
parents[child].add(i);
}
}
//遍历parents,将每个顶点都打印一遍
for(int i=0;i<v;i++){
if(!visited[i]){
printCurr(i,visited,parents);
}
}
}
private void printCurr(int curr,boolean[] visited,LinkedList<Integer>[] parents){
if(visited[curr]){
return;
}
//标记当前顶点已访问过
visited[curr] = true;
int parent;
//获取当前顶点所有父顶点
for(int i =0; i<parents[curr].size(); i++){
parent = parents[curr].get(i);
//打印父顶点
printCurr(parent,visited,parents);
}
//所有父顶点打印完毕,再打印自身
sysout: 当前编译项为: + curr;
}
- kahn算法的时间复杂度O(E+V)/每个顶点被访问1次,每条边也被访问1次, Kahn的空间复杂度O(V);
- DFS算法的空间复杂度是O(V),时间复杂度是O(E+V)/每个顶点被访问2次,每条边被访问1次.
- 每个顶点被访问2次: curr -> parents; parent -> parents;
- 拓扑排序的应用场景: 凡是需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决.
- 检测图中是否存在环:
6.1: Kahn算法,如果最终打印的顶点个数数量少于顶点总量,说明图中成环,部分顶点始终无法达到入度为0
6.2: 如果是A推荐B,B推荐C,C推荐D,D推荐E,E又推荐A这样的环状结构,如何检测.
只要从A开始向下递推,每个访问过的人都记录下来,如果成环,同1个人会被访问2次.
A->B->C->D->E->A.
只要记录中出现1个人被访问2次,说明成环了.
private HaseSet<Integer> visited = new HashSet<Integer>();
private int findFinalRef(int userId){
if(visited.contains(userId)){
//说明同一用户被访问第2次,说明出现了环状结构
return;
}
int refId = gainCurrUserRef(userId);
if(refId == -1){
//说明当前userId没有下一个推荐人,则返回自身
return userId;
}
return findFinalRef(refId);
}
44. | 最短路径：地图软件是如何计算出最优出行路径的
- Dijkstra算法相关文章
- 计算地图上两个地点的最优路径,可以将地图抽象成'图'这种结构.每个地点是图的1个顶点.两个地点之间的路是一条边,单向路就是A->B,双向路就是 A->B + B->A.
路的长度,就是每条边的权重.
地图就被抽象成1个有向有权图. - 地图中两个地点的最短路径,变成 有向有权图中2个顶点间的最短距离.
- 将地图抽象成图的代码
public class Graph{
//邻接表
private LinkedList<Edge>[] adj;
//顶点个数
private int v;
public Graph(int v){
this.v = v;
this.adj = new LinkedList<Edge>[v];
for(int i =0;i<v;i++){
adj[i] = new LinkedList<Edget>();
}
}
//添加一条边. 从s到t.
public void addEdge(int s,int t, int w){
this.adj[s].add(new Edge(s, t, w));
}
private class Edge{
public int sid; //边的起始顶点编号
public int tid; //边的终止顶点编号
public int w; //边的权重
public Edge(int sid, int tid, int w){
this.sid = sid;
this.tid = tid;
this.w = w;
}
}
//这个类专门为dijkstra算法实现的
private class Vertex{
//顶点id
public int id;
//从起始顶点 到这个顶点的 最短距离
public int dist;
public Vertex(int id, int dist){
this.id = id;
this.dist = dist;
}
}
}
一个顶点到另一个顶点的最短路径算法,最著名的是Dijkstra算法.
- Dijkstra算法实现
//Java提供的优先级队列,没有提供更新单个元素的接口,所以需要自行实现1个
private class PriorityQueue{
//需要根据Vertex.dist构建小顶堆
private Vertex[] nodes;
private int count;
private PriorityQueue(int v){
this.nodes = new Vertex[v + 1];
this.count = v;
}
//待实现
public Vertex poll(){}
//待实现
public void add(Vertex vertex){
}
//待实现: 更新结点的值,并且从下往上堆化, 使之重新符合小顶堆的定义
public void update(Vertex vertex){
}
//待实现
public boolean isEmpty(){
}
}
//dijkstra算法实现
public void dijkstra(int s,int t){
int[] pre = new int[v];
Vertex[] vertexes = new Vertex[v];
for(int i=0;i<v;i++){
vertexes[i] = new Vertex(i,Integer.MAX_VALUE);
}
PriorityQueue queue = new PriorityQueue(v);
boolean[] inqueue = new boolean[v];
queue.add(vertexes[s]);
inqueue[s] = true;
while(!queue.isEmpty()){
Vertex minVertex = queue.poll();
if(minVertex.id == t){
break;
}
for(int i=0;i<adj[minVertex.id].size();i++){
Edge e = adj[minVertex.id].get(i);
Vertex nextVertex = vertexes[e.tid];
if(minVertex.dist + e.w < nextVertex.dist){
nextVertex.dist = minVertex.dist + e.w;
pre[nextVertex.id] = minVertex.id;
if(inqueue[nextVertex.id]){
queue.update(nextVertex);
}else{
queue.add(nextVertex);
inqueue[nextVertex.id] = true;
}
}
}
}
System.out.println("从s到t最短路径长度:" + vertexes[t].dist);
//依次答应最短路径长度对应的每个顶点
print(s, t, pre);
}
private void print(int s, int t, int[] pre){
if(s == t){
System.out.println("当前元素:" + t);
return;
}
print(s, pre[t], pre);
//打印t
System.out.println("当前元素:" + t);
}
- Dijkstra的时间复杂度
- while循环次数: 最多是V次, V代表顶点的个数.
- while循环内,每次for循环次数不同,V次总体for循环次数 <= E. E是图中边的数量.
- 优先级队列是1个小顶堆,每次poll,add或update,时间复杂度是O(logV)
- 整个Dijkstra的时间复杂度是 O(E*logV)
- 地图软件用的更多的是类似 A* 的启发式搜索算法，不过也是在 Dijkstra 算法上的优化.
45 | 位图：如何实现网页爬虫中的URL去重功能？
前置知识
- 位运算
网友评论