43. | 拓?fù)渑判颍喝绾未_定代碼源文件的編譯依賴關(guān)系 - 開(kāi)始
- 編譯器如何通過(guò)源文件兩兩之間的局部依賴關(guān)系，確定一個(gè)全局的編譯順序：
使用 '圖' 這種數(shù)據(jù)結(jié)構(gòu)的 '拓?fù)渑判蛩惴? 解決. - 什么是拓?fù)渑判?/li>
- 多個(gè)元素,部分或全部元素的兩兩依賴關(guān)系已經(jīng)確定,如何安排一個(gè)序列,能夠滿足上述元素的兩兩依賴關(guān)系.
-
很多時(shí)候,拓?fù)渑判虻男蛄胁皇俏ㄒ坏?因?yàn)榭赡懿皇撬性刂g都具有依賴關(guān)系.
c26d0f472d9a607c0c4eb688c01959bd[1].jpg
- 拓?fù)渑判虻脑砗芎?jiǎn)單,重要的是拓?fù)渑判虻膶?shí)現(xiàn).
- 如何確定代碼源文件的編譯依賴關(guān)系:
- 把源文件和源文件之間的依賴關(guān)系,抽象成1個(gè)有向圖;
- 每個(gè)源文件對(duì)應(yīng)圖中的一個(gè)頂點(diǎn);
- 源文件之間的依賴關(guān)系就是頂點(diǎn)之間的邊;
- 如果A先于B執(zhí)行,或者說(shuō)B依賴于A,就在A和B之間,構(gòu)建一條從A指向B的的邊;
- 注意這個(gè)圖必須是一個(gè)有向無(wú)環(huán)圖. 因?yàn)閳D中一旦成環(huán),拓?fù)渑判蚓蜔o(wú)法工作;
- 拓?fù)渑判虮旧砭褪腔谟邢驘o(wú)環(huán)圖的一個(gè)算法.
public class Graph {
//定義頂點(diǎn)的個(gè)數(shù)
private int v;
//每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)鄰接表, 多個(gè)頂點(diǎn)構(gòu)鄰接表數(shù)組
private LinkeList<Integer>[] adj;
//構(gòu)造函數(shù)
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優(yōu)先于t / t依賴于s
//從頂點(diǎn)s出發(fā),構(gòu)建一條指向t的邊
public void addEdge(int s, int t){
adj[s].add(t);
}
}
- 如何在Graph這個(gè)有向無(wú)環(huán)圖上,實(shí)現(xiàn)拓?fù)渑判?有2種算法: Kahn算法 和 DFS深度優(yōu)先搜索算法.
- 看Kahn算法 和 DFS深度優(yōu)先搜索算法 之前,首先回顧下之前的'圖'相關(guān)知識(shí).
43前置知識(shí): 圖
- 圖
- 圖是一種非線性表數(shù)據(jù)結(jié)構(gòu).
- 圖中的每個(gè)元素叫做頂點(diǎn).
- 圖中的1個(gè)頂點(diǎn)可以與其他任意頂點(diǎn)進(jìn)行連接,連接叫做邊.
- 有向圖:
每條邊都是有方向的.A->B:從A到B. B->A:從B到A. - 無(wú)向圖:
每條邊都是沒(méi)有方向的.單純代表A-B兩個(gè)頂點(diǎn)建立連接. - 每個(gè)頂點(diǎn)有多少條邊,叫做頂點(diǎn)的度.
- 有向圖中,每個(gè)頂點(diǎn)有 入度 和 出度.
- 入度:有多少條邊指向該頂點(diǎn);
-
出度:從該頂點(diǎn)發(fā)出多少條邊;
圖
- 帶權(quán)圖
-
每條邊都有1個(gè)權(quán)重/weight.
帶權(quán)圖
- 圖的存儲(chǔ)方法: 鄰接矩陣 和 鄰接表.
- 使用 鄰接矩陣 存儲(chǔ)圖
- 鄰接矩陣底層是1個(gè)二維數(shù)組.
- 對(duì)于有向圖: 頂點(diǎn)i向頂點(diǎn)j發(fā)出一條邊 , 則 A[i][j] = 1;
- 對(duì)于無(wú)向圖: 頂點(diǎn)i和頂點(diǎn)j之間有邊,則 A[i][j] 和 A[j][i] 都是1;
-
對(duì)于帶權(quán)圖: 數(shù)組元素存儲(chǔ)連接的2個(gè)頂點(diǎn)之間的權(quán)重;
使用鄰接矩陣存儲(chǔ)圖
練一下markdown中怎么畫(huà)矩陣.
$$\begin{matrix}
A & B & C\\
D & E & F\\
G & H & I\\
\end{matrix}$$
無(wú)向圖:
有向圖:
帶權(quán)圖:
- 鄰接矩陣的缺點(diǎn): 浪費(fèi)存儲(chǔ)空間.
- 對(duì)于無(wú)向圖,頂點(diǎn)i,j之間有邊,需要A[i][j]和A[j][i]都存儲(chǔ)為1,實(shí)際只存1個(gè)就夠了.浪費(fèi)了一半空間;
- 對(duì)于稀疏圖.即頂點(diǎn)很多,但每個(gè)頂點(diǎn)的邊不多,使用鄰接矩陣就更加浪費(fèi)存儲(chǔ)空間.
- 比如微信十億用戶,但每個(gè)用戶最多2000個(gè)好友.使用鄰接矩陣會(huì)浪費(fèi)絕大部分存儲(chǔ)空間.
- 鄰接矩陣的有點(diǎn):
- 鄰接矩陣基于數(shù)組,獲取2個(gè)頂點(diǎn)的關(guān)系非常快;
- 臨街矩陣存儲(chǔ)圖可以將很多圖的運(yùn)算,轉(zhuǎn)換為矩陣之間的運(yùn)算,效率很高.
-
使用 鄰接表 存儲(chǔ)圖
使用鄰接表存儲(chǔ)圖
- 鄰接表存儲(chǔ)圖很像散列表.
- 每個(gè)頂點(diǎn)對(duì)應(yīng)1條鏈表,存儲(chǔ)與該頂點(diǎn)相連的其他頂點(diǎn).
- 鄰接表存儲(chǔ)圖 和 鄰接矩陣存儲(chǔ)圖 比較:
- 相對(duì)于鄰接數(shù)組節(jié)省空間,尤其是稀疏圖場(chǎng)景.只有相連的頂點(diǎn)的邊才會(huì)存儲(chǔ)在對(duì)應(yīng)頂點(diǎn)的鏈表中.
- 是用時(shí)間換空間,比如查詢頂點(diǎn)A和頂點(diǎn)B是否相連,就要在A頂點(diǎn)對(duì)應(yīng)的鏈表中遍歷查詢.
- 鏈表的存儲(chǔ)對(duì)緩存不友好,所以鏈表中查詢兩個(gè)頂點(diǎn)之間的關(guān)系效率低.
- 可以將鄰接表中的鏈表替換為支持快速查找的數(shù)據(jù)結(jié)構(gòu): 紅黑樹(shù)、跳表、有序動(dòng)態(tài)數(shù)組,散列表
- 使用圖,存儲(chǔ)微博的用戶之間關(guān)系
針對(duì)微博用戶關(guān)系，假設(shè)我們需要支持下面這樣幾個(gè)操作：判斷用戶 A 是否關(guān)注了用戶 B；判斷用戶 A 是否是用戶 B 的粉絲；用戶 A 關(guān)注用戶 B；用戶 A 取消關(guān)注用戶 B；根據(jù)用戶名稱的首字母排序，分頁(yè)獲取用戶的粉絲列表；根據(jù)用戶名稱的首字母排序，分頁(yè)獲取用戶的關(guān)注列表。
public class Graph {
//微博系統(tǒng)中用戶量
private int v;
//BestType用于指代特定的數(shù)據(jù)結(jié)構(gòu),用于替換鏈表,提升鏈表的查詢效率
//followers用于存儲(chǔ)每個(gè)用戶關(guān)注的人
private BestType<Integer>[] followers;
//fans用戶存儲(chǔ)每個(gè)用戶被哪些人關(guān)注
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關(guān)注用戶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對(duì)應(yīng)的 關(guān)注的人 中
followers[aIndex].add(bId);
//將用戶a的id添加到用戶b對(duì)應(yīng)的 粉絲 中
fans[bIndex].add(aId);
}
//用戶a不再關(guān)注用戶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對(duì)應(yīng)的 關(guān)注的人 中刪除
followers[aIndex].remove(bId);
//將用戶a的id從用戶b對(duì)應(yīng)的 粉絲 中刪除
fans[bIndex].remove(aId);
}
//BestType具體選擇哪一種支持快速查詢的數(shù)據(jù)結(jié)構(gòu): 跳表 .
//跳表插入、刪除、查找都非常高效，時(shí)間復(fù)雜度是 O(logn)，空間復(fù)雜度上稍高，是 O(n)。
//最重要的一點(diǎn)，跳表中存儲(chǔ)的數(shù)據(jù)本來(lái)就是有序的了，分頁(yè)獲取粉絲列表或關(guān)注列表，就非常高效
}
- 深度優(yōu)先搜索算法 和 廣度優(yōu)先搜索算法 , 都是基于 '圖' 這種數(shù)據(jù)結(jié)構(gòu).
- 廣度優(yōu)先搜索/BFS/Breadth-First-Search
public class Graph { // 無(wú)向圖
private int v; // 頂點(diǎn)的個(gè)數(shù)
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) { // 無(wú)向圖一條邊存兩次
adj[s].add(t);
adj[t].add(s);
}
}
- 廣度優(yōu)先搜索,就是先查找離起始頂點(diǎn)最近的,然后是次近的,一層層往外搜索.
- 從頂點(diǎn)s出發(fā),搜索一條從s到t的最短路徑.
private void bfs(int s, int t){
if(s == t){
//同一頂點(diǎn)不用繼續(xù)搜索
return;
}
//記錄指定頂點(diǎn)是否訪問(wèn)過(guò)
boolean[] visited = new boolean[v];
visited[s] = true;
//保存每個(gè)訪問(wèn)過(guò)的頂點(diǎn)的前一頂點(diǎn)
int[] prev = new int[v];
for(int i=0;i<v;i++){
prev[i] = -1;
}
//保存待比較其后續(xù)頂點(diǎn)的頂點(diǎn)
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(s);
while(queue.size() > 0){
//獲取當(dāng)前頂點(diǎn)
int curr = queue.poll();
//遍歷比較當(dāng)前頂點(diǎn)的所有子頂點(diǎn)
for(int i = 0; i<adj[curr].size(); i++){
int c = adj[curr].get(i);
if(!visited[c]){
//標(biāo)記當(dāng)前子頂點(diǎn) 已被訪問(wèn)過(guò)
visited[c] = true;
//標(biāo)記當(dāng)前子頂點(diǎn) 的上一結(jié)點(diǎn)就是curr
prev[c] = curr;
//如果當(dāng)前子頂點(diǎn) 就是 要尋找的最終頂點(diǎn)
if(c == t){
//打印整個(gè)搜索路徑, 終止循環(huán)
printRouter(prev, s, t);
return;
}
queue.add(c);
}
}
}
}
private void printRouter(int[] prev, int start, int target){
if(prev[target] != -1 && target != start){
//繼續(xù)打印 start 到 target之前1個(gè)元素的路徑
printRouter(prev, start, prev[target]);
}
//打印當(dāng)前元素
System.out.println("當(dāng)前元素:" + target);
}
- 廣度優(yōu)先搜索算法的 時(shí)間復(fù)雜度,空間復(fù)雜度:
- 時(shí)間復(fù)雜度是O(V+E)
- V表示頂點(diǎn)的個(gè)數(shù),E表示邊的個(gè)數(shù)
- 對(duì)于1個(gè)連通圖.即一個(gè)圖中所有的頂點(diǎn)都是連通的圖,E肯定大于V
- 所以廣度優(yōu)先搜索算法的時(shí)間復(fù)雜度簡(jiǎn)寫(xiě)為O(E)
- 空間復(fù)雜度的O(V)
- visited 數(shù)組,prev 數(shù)組,queue隊(duì)列,這三個(gè)存儲(chǔ)空間大小都不會(huì)超過(guò)頂點(diǎn)個(gè)數(shù)V.
- 所以其空間復(fù)雜度是O(V).
- 時(shí)間復(fù)雜度是O(V+E)
- 深度優(yōu)先搜索 / DFS / Depth-First-Search
- 深度優(yōu)先搜索算法,本質(zhì)上就是回溯算法
- 每一步,都要n種走法,每一種走法都走一遍
- 回溯算法的套路
1: 整體問(wèn)題最終值 存放在回溯方法體外;
2: 回溯方法中有判斷終止條件 及 整體問(wèn)題最終值修改邏輯;
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);
}
調(diào)用方式:
int bestValue = -1;
recur(p1.bound);
sys: 最優(yōu)解: + bestValue.
- 使用深度優(yōu)先搜索算法尋找頂點(diǎn)s到頂點(diǎn)t的路徑
private boolean found = false;
private void recurDfs(int curr, int target, boolean[] visited, int[] prev){
if(found){
//之前已經(jīng)找到路徑,避免重復(fù)執(zhí)行
//終止條件
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]){
//之前沒(méi)有遍歷過(guò)該子頂點(diǎn)
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);
}
- 深度優(yōu)先搜索算法/回溯算法 的時(shí)間復(fù)雜度 和 空間復(fù)雜度
- 遍歷 + 回溯, 每條邊最多訪問(wèn)2次: parent -> n個(gè)child; 每個(gè)child -> 包括parent在內(nèi)的n個(gè)頂點(diǎn).
- 時(shí)間復(fù)雜度是O(E). E是邊數(shù)量
- 空間復(fù)雜度是O(V). 因?yàn)轭~外的visited ,prev 數(shù)量不超過(guò)V.
43. | 拓?fù)渑判颍喝绾未_定代碼源文件的編譯依賴關(guān)系 - 繼續(xù)
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>();
}
}
//添加從頂點(diǎn)s到頂點(diǎn)t的一條邊
//因?yàn)槭且蕾囮P(guān)系,所以是有向圖
public void addEdge(int s, int t){
adj[s].add(t);
}
}
如何在有向無(wú)環(huán)圖上,實(shí)現(xiàn)拓?fù)渑判?
拓?fù)渑判蛴?種實(shí)現(xiàn)方法: Kahn算法 及 DFS深度優(yōu)先搜索算法.
- Kahn算法
- Kahn算法實(shí)際用的是貪心算法思想
- 頂點(diǎn)的入度為0,說(shuō)明該頂點(diǎn)不依賴任何其他頂點(diǎn),可以立即執(zhí)行.
- Kahn實(shí)現(xiàn)步驟:
- 定義1個(gè)數(shù)組,統(tǒng)計(jì)圖中所有頂點(diǎn)的入度,存儲(chǔ)于該數(shù)組
- 定義1個(gè)隊(duì)列,存儲(chǔ)圖中所有入度為0的頂點(diǎn)
- 從隊(duì)列頭部不斷取入度為0的頂點(diǎn),執(zhí)行/打印.
- 將該頂點(diǎn)對(duì)應(yīng)的所有子頂點(diǎn)的入度-1
- 若某個(gè)子頂點(diǎn)的入度變?yōu)?,則將該子頂點(diǎn)也加入隊(duì)列
- Kahn代碼實(shí)現(xiàn)
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("當(dāng)前編譯:" + curr);
for(int i=0;i<adj[curr].size();i++){
//遍歷當(dāng)前頂點(diǎn)的所有子頂點(diǎn)
child = adj[curr].get(i);
//每個(gè)子頂點(diǎn)的入度-1
inDegree[child ]--;
//若子頂點(diǎn)入度變?yōu)?
if(inDegree[child] == 0){
q.add(child);
}
}
}
}
- DFS算法
- DFS算法本質(zhì)上是回溯算法
- 原始數(shù)據(jù)是 頂點(diǎn)->多個(gè)子頂點(diǎn)
- 要答應(yīng)整個(gè)依賴關(guān)系,需要知道每個(gè)頂點(diǎn)都依賴哪些父頂點(diǎn), 根據(jù)原始的 curr->children 構(gòu)建逆鄰接表 curr->parents
- 每次打印1個(gè)頂點(diǎn),都要先保證其 parents 都打印完畢,再打印自身.
- DFS代碼實(shí)現(xiàn)
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,將每個(gè)頂點(diǎn)都打印一遍
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;
}
//標(biāo)記當(dāng)前頂點(diǎn)已訪問(wèn)過(guò)
visited[curr] = true;
int parent;
//獲取當(dāng)前頂點(diǎn)所有父頂點(diǎn)
for(int i =0; i<parents[curr].size(); i++){
parent = parents[curr].get(i);
//打印父頂點(diǎn)
printCurr(parent,visited,parents);
}
//所有父頂點(diǎn)打印完畢,再打印自身
sysout: 當(dāng)前編譯項(xiàng)為: + curr;
}
- kahn算法的時(shí)間復(fù)雜度O(E+V)/每個(gè)頂點(diǎn)被訪問(wèn)1次,每條邊也被訪問(wèn)1次, Kahn的空間復(fù)雜度O(V);
- DFS算法的空間復(fù)雜度是O(V),時(shí)間復(fù)雜度是O(E+V)/每個(gè)頂點(diǎn)被訪問(wèn)2次,每條邊被訪問(wèn)1次.
- 每個(gè)頂點(diǎn)被訪問(wèn)2次: curr -> parents; parent -> parents;
- 拓?fù)渑判虻膽?yīng)用場(chǎng)景: 凡是需要通過(guò)局部順序來(lái)推導(dǎo)全局順序的，一般都能用拓?fù)渑判騺?lái)解決.
- 檢測(cè)圖中是否存在環(huán):
6.1: Kahn算法,如果最終打印的頂點(diǎn)個(gè)數(shù)數(shù)量少于頂點(diǎn)總量,說(shuō)明圖中成環(huán),部分頂點(diǎn)始終無(wú)法達(dá)到入度為0
6.2: 如果是A推薦B,B推薦C,C推薦D,D推薦E,E又推薦A這樣的環(huán)狀結(jié)構(gòu),如何檢測(cè).
只要從A開(kāi)始向下遞推,每個(gè)訪問(wèn)過(guò)的人都記錄下來(lái),如果成環(huán),同1個(gè)人會(huì)被訪問(wèn)2次.
A->B->C->D->E->A.
只要記錄中出現(xiàn)1個(gè)人被訪問(wèn)2次,說(shuō)明成環(huán)了.
private HaseSet<Integer> visited = new HashSet<Integer>();
private int findFinalRef(int userId){
if(visited.contains(userId)){
//說(shuō)明同一用戶被訪問(wèn)第2次,說(shuō)明出現(xiàn)了環(huán)狀結(jié)構(gòu)
return;
}
int refId = gainCurrUserRef(userId);
if(refId == -1){
//說(shuō)明當(dāng)前userId沒(méi)有下一個(gè)推薦人,則返回自身
return userId;
}
return findFinalRef(refId);
}
44. | 最短路徑：地圖軟件是如何計(jì)算出最優(yōu)出行路徑的
- Dijkstra算法相關(guān)文章
- 計(jì)算地圖上兩個(gè)地點(diǎn)的最優(yōu)路徑,可以將地圖抽象成'圖'這種結(jié)構(gòu).每個(gè)地點(diǎn)是圖的1個(gè)頂點(diǎn).兩個(gè)地點(diǎn)之間的路是一條邊,單向路就是A->B,雙向路就是 A->B + B->A.
路的長(zhǎng)度,就是每條邊的權(quán)重.
地圖就被抽象成1個(gè)有向有權(quán)圖. - 地圖中兩個(gè)地點(diǎn)的最短路徑,變成 有向有權(quán)圖中2個(gè)頂點(diǎn)間的最短距離.
- 將地圖抽象成圖的代碼
public class Graph{
//鄰接表
private LinkedList<Edge>[] adj;
//頂點(diǎn)個(gè)數(shù)
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; //邊的起始頂點(diǎn)編號(hào)
public int tid; //邊的終止頂點(diǎn)編號(hào)
public int w; //邊的權(quán)重
public Edge(int sid, int tid, int w){
this.sid = sid;
this.tid = tid;
this.w = w;
}
}
//這個(gè)類專門(mén)為dijkstra算法實(shí)現(xiàn)的
private class Vertex{
//頂點(diǎn)id
public int id;
//從起始頂點(diǎn) 到這個(gè)頂點(diǎn)的 最短距離
public int dist;
public Vertex(int id, int dist){
this.id = id;
this.dist = dist;
}
}
}
一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑算法,最著名的是Dijkstra算法.
- Dijkstra算法實(shí)現(xiàn)
//Java提供的優(yōu)先級(jí)隊(duì)列,沒(méi)有提供更新單個(gè)元素的接口,所以需要自行實(shí)現(xiàn)1個(gè)
private class PriorityQueue{
//需要根據(jù)Vertex.dist構(gòu)建小頂堆
private Vertex[] nodes;
private int count;
private PriorityQueue(int v){
this.nodes = new Vertex[v + 1];
this.count = v;
}
//待實(shí)現(xiàn)
public Vertex poll(){}
//待實(shí)現(xiàn)
public void add(Vertex vertex){
}
//待實(shí)現(xiàn): 更新結(jié)點(diǎn)的值,并且從下往上堆化, 使之重新符合小頂堆的定義
public void update(Vertex vertex){
}
//待實(shí)現(xiàn)
public boolean isEmpty(){
}
}
//dijkstra算法實(shí)現(xiàn)
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最短路徑長(zhǎng)度:" + vertexes[t].dist);
//依次答應(yīng)最短路徑長(zhǎng)度對(duì)應(yīng)的每個(gè)頂點(diǎn)
print(s, t, pre);
}
private void print(int s, int t, int[] pre){
if(s == t){
System.out.println("當(dāng)前元素:" + t);
return;
}
print(s, pre[t], pre);
//打印t
System.out.println("當(dāng)前元素:" + t);
}
- Dijkstra的時(shí)間復(fù)雜度
- while循環(huán)次數(shù): 最多是V次, V代表頂點(diǎn)的個(gè)數(shù).
- while循環(huán)內(nèi),每次for循環(huán)次數(shù)不同,V次總體for循環(huán)次數(shù) <= E. E是圖中邊的數(shù)量.
- 優(yōu)先級(jí)隊(duì)列是1個(gè)小頂堆,每次poll,add或update,時(shí)間復(fù)雜度是O(logV)
- 整個(gè)Dijkstra的時(shí)間復(fù)雜度是 O(E*logV)
- 地圖軟件用的更多的是類似 A* 的啟發(fā)式搜索算法，不過(guò)也是在 Dijkstra 算法上的優(yōu)化.
45 | 位圖：如何實(shí)現(xiàn)網(wǎng)頁(yè)爬蟲(chóng)中的URL去重功能？
前置知識(shí)
- 位運(yùn)算
