從廣義上來(lái)講：數(shù)據(jù)結(jié)構(gòu)就是
一組數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)， 算法就是操作數(shù)據(jù)的方法數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的，算法是要作用在特定的數(shù)據(jù)結(jié)構(gòu)上的。
10個(gè)最常用的數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊(duì)列、散列表、二叉樹、堆、跳表、圖、Trie樹
10個(gè)最常用的算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動(dòng)態(tài)規(guī)劃、字符串匹配算法
本文總結(jié)了20個(gè)最常用的數(shù)據(jù)結(jié)構(gòu)和算法，不管是應(yīng)付面試還是工作需要，只要集中精力攻克這20個(gè)知識(shí)點(diǎn)就足夠了。
數(shù)據(jù)結(jié)構(gòu)和算法（一）：復(fù)雜度、數(shù)組、鏈表、棧、隊(duì)列的傳送門
數(shù)據(jù)結(jié)構(gòu)和算法（二）：遞歸、排序、通用排序算法的傳送門
數(shù)據(jù)結(jié)構(gòu)和算法（三）：二分查找、跳表、散列表、哈希算法的傳送門
數(shù)據(jù)結(jié)構(gòu)和算法（四）：二叉樹、紅黑樹、遞歸樹、堆和堆排序、堆的應(yīng)用的傳送門
數(shù)據(jù)結(jié)構(gòu)和算法（五）：圖、深度優(yōu)先搜索和廣度優(yōu)先搜索、字符串匹配算法、Trie樹、AC自動(dòng)機(jī)的傳送門
數(shù)據(jù)結(jié)構(gòu)和算法（六）：貪心算法、分治算法、回溯算法、動(dòng)態(tài)規(guī)劃、拓?fù)渑判虻膫魉烷T
第二十六章 貪心算法
一、什么是貪心算法
- 貪心算法是指在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇，也就是說(shuō)不從整體考慮，而是從局部看來(lái)是最優(yōu)解，所以貪心算法得到的結(jié)果不一定是最優(yōu)的。
- 貪心算法沒(méi)有固定的算法解決框架，算法的關(guān)鍵就是貪婪策略的選擇，根據(jù)不同問(wèn)題選擇不同的策略。
- 貪心算法的適用場(chǎng)景比較有限，更多是用來(lái)指導(dǎo)設(shè)計(jì)基礎(chǔ)算法，比如最小生成樹算法、單源最短路徑算法等。
二、使用貪心算法的解決問(wèn)題的思路
- 當(dāng)我們看到此類數(shù)據(jù)時(shí)，首先要聯(lián)想到貪心算法：針對(duì)一組數(shù)據(jù)，我們定義了限制值和期望值，希望從中選擇幾個(gè)數(shù)據(jù)，在滿足限制值的前提下，期望值最大。（例如：從寶庫(kù)中只能拿100kg的物品，從黃金、白銀、純鐵怎么選擇，使得價(jià)值最大，這里面限制值就是100kg，期望值就是價(jià)值最大。）
- 將問(wèn)題抽象成限制值、期望值后，就可以嘗試選擇合適的貪婪策略去解決了，在剛才那個(gè)例子中，貪婪策略就是盡量多拿單價(jià)最高的金屬。
- 選擇不同的貪婪策略后，看下貪心算法產(chǎn)生的結(jié)果是否是最優(yōu)的。從實(shí)踐的角度來(lái)說(shuō)，大部分能用貪心算法解決的問(wèn)題，貪心算法的正確性都是顯而易見(jiàn)的，也不需要嚴(yán)格證明。
三、貪心算法實(shí)戰(zhàn)分析
-
- 分糖果
(1). 假設(shè)我們有m個(gè)糖果和n個(gè)孩子，要把糖果分給孩子吃，糖果多孩子少，每個(gè)糖果的大小不等，每個(gè)孩子對(duì)糖果的需求也不相同，只要糖果的大小超過(guò)了孩子的需求，那么這個(gè)孩子就會(huì)得到滿足，請(qǐng)問(wèn)：如何分配糖果，才能滿足最多數(shù)量的孩子呢？
(2). 解決這個(gè)問(wèn)題的第一步，我們把問(wèn)題抽象成：在n個(gè)孩子中，選擇一部分孩子分配糖果，使得滿足的孩子最多。這里m個(gè)糖果就是限制值，最多滿足的孩子就是期望值。
(3). 解決這個(gè)問(wèn)題的第二步，嘗試用貪心算法解決。對(duì)應(yīng)一個(gè)孩子來(lái)說(shuō)，如果小的糖果就可以解決，那么沒(méi)必要用大的糖果，所以分配糖果的時(shí)候我們可以用需求最小的孩子開(kāi)始分配。
(4). 我們的分配策略就是：每次從剩下的孩子中選擇需求最小的孩子，分配給能滿足他的最少糖果，這樣的分配方案，就是滿足孩子最多的方案，這也是顯而易見(jiàn)的最優(yōu)方案。
-
- 區(qū)間覆蓋
(1). 假設(shè)有n個(gè)區(qū)間，區(qū)間的起始端點(diǎn)和結(jié)束端點(diǎn)分別是[a1,a2]、[b1,b2]...，我們從這n個(gè)區(qū)間內(nèi)選取一部分不相交的區(qū)間，問(wèn)：怎么選擇，才能使得不相交的區(qū)間個(gè)數(shù)最多呢？
(2). 解決問(wèn)題第一步，我們把問(wèn)題抽象化，假設(shè)n個(gè)區(qū)間的最左側(cè)是min端點(diǎn)，最右側(cè)是max端點(diǎn)，這個(gè)問(wèn)題就相當(dāng)于，從n個(gè)區(qū)間中選取幾個(gè)不相交的區(qū)間，從左到右將[min，max]覆蓋完。
-
(3). 解決問(wèn)題的第二步，選擇合適的貪婪策略嘗試解決，我們每次選擇的時(shí)候，選擇左邊端點(diǎn)不重合，右邊端點(diǎn)盡可能小的區(qū)間，使得剩下的區(qū)域盡可能大，就可以放置更多的區(qū)間。如下圖：
區(qū)間覆蓋.png
-
- 如何用貪心算法實(shí)現(xiàn)霍夫曼壓縮編碼
- (1). 假設(shè)有1000個(gè)字符，每個(gè)字符占1個(gè)字節(jié)，一共占1000個(gè)字節(jié)，也就是8000bit的存儲(chǔ)空間；如果我們統(tǒng)計(jì)發(fā)現(xiàn)這1000個(gè)字符，只有6種字符，分別為a、b、c、d、e、f的話，我們就可以用3個(gè)bit來(lái)表示他們，如下圖，這樣我們就可以只占用3000bit的空間了，比原來(lái)節(jié)省了很多，那么我們還有更節(jié)省空間的方法嗎？（3個(gè)bit其實(shí)可以存放8種不同的字符，2 x 2 x 2 = 8）
a(000)、b(001)、c(010)、d(011)、e(100)、f(101)(2). 霍夫曼編碼就登場(chǎng)了，霍夫曼編碼廣泛應(yīng)用于數(shù)據(jù)壓縮中，壓縮率在20%~90%之間，霍夫曼編碼不僅會(huì)考察文本中有多少個(gè)字符，還會(huì)統(tǒng)計(jì)字符出現(xiàn)的頻率，根據(jù)頻率不同，選擇不同長(zhǎng)度的編碼，頻率高的字符選用短編碼，頻率低的字符選用稍長(zhǎng)編碼，霍夫曼編碼試圖使用不等長(zhǎng)的編碼方式，來(lái)進(jìn)一步增加壓縮效率。
(3). 由于霍夫曼編碼是不等長(zhǎng)的，所以解壓縮的時(shí)候就比較困難，不知道該讀取1位還是2位還是3位來(lái)解壓縮，所以為了避免這種歧義，霍夫曼編碼要求各個(gè)字符的編碼之間，不能出現(xiàn)一個(gè)字符的編碼是另一個(gè)字符編碼的前綴。
-
(4). 在上面那個(gè)例子中，我們假設(shè)這6個(gè)字符出現(xiàn)的頻率從高到低依次是a、b、c、d、e、f，我們采用霍夫曼編碼的方式進(jìn)行編碼后，就是下圖的樣子，任意一個(gè)字符的編碼都不是其他字符編碼的前綴，在解壓縮的時(shí)候，就可以以 讀取盡可能長(zhǎng)的可解壓二進(jìn)制串 的方式來(lái)解壓，就不會(huì)出現(xiàn)解壓歧義了，通過(guò)霍夫曼編碼來(lái)壓縮，這1000個(gè)字符只需要占用2100bit的存儲(chǔ)空間就夠了。
采用霍夫曼編碼對(duì)1000個(gè)字符進(jìn)行壓縮 -
(5). 霍夫曼編碼的思想并不難理解，但是如何根據(jù)字符出現(xiàn)的頻率，選用不同長(zhǎng)度的編碼呢？ 這里可以這樣處理，如下圖：把每個(gè)字符都看作一個(gè)節(jié)點(diǎn)，把頻率最低的兩個(gè)節(jié)點(diǎn)f、c組合在一起生成一個(gè)父節(jié)點(diǎn)x，x的頻率為f、c頻率之和，再把x節(jié)點(diǎn)和頻率次低的d節(jié)點(diǎn)組合生成父節(jié)點(diǎn)y，一直重復(fù)下去，直到把字符處理完；接下來(lái)，給每條邊上畫一個(gè)權(quán)值，指向左節(jié)點(diǎn)的邊統(tǒng)一記做0，指向右節(jié)點(diǎn)的邊統(tǒng)一記做1，那么從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，就是葉子節(jié)點(diǎn)對(duì)應(yīng)字符的霍夫曼編碼了。
霍夫曼編碼如何根據(jù)字符頻率選編碼
第二十七章 分治算法
一、什么是分治算法？
- 分治算法的核心思想就是四個(gè)字：分而治之，就是將原問(wèn)題分解成n個(gè)小問(wèn)題，解決這些小問(wèn)題后，將結(jié)果合并，就可以得到原問(wèn)題的解了。
-
- 想用分治算法解決問(wèn)題，一般需要滿足以下條件：
- (1). 原問(wèn)題與分解成的小問(wèn)題具有相同模式
- (2). 子問(wèn)題之間沒(méi)有關(guān)聯(lián)性，可以獨(dú)立求解（需要跟動(dòng)態(tài)規(guī)劃區(qū)分開(kāi)）
- (3). 具有分解終止條件，也就是說(shuō)，當(dāng)問(wèn)題足夠小時(shí)，可以直接求解
- (4). 可以將子問(wèn)題合并成原問(wèn)題，并且合并操作復(fù)雜度不能太高，不然就起不到降低總體算法復(fù)雜度的目的了
二、分治思想在海量數(shù)據(jù)處理中的應(yīng)用
- 假設(shè)要給10G的訂單數(shù)據(jù)按照金額進(jìn)行排序，但是我們機(jī)器的內(nèi)存只有2G，無(wú)法一次性加載到內(nèi)存，也就無(wú)法單純的利用快排、歸并算法來(lái)解決了，就可以使用分治思想來(lái)解決
- 面對(duì)10G的訂單數(shù)據(jù)，我們可以先掃描一遍訂單，根據(jù)訂單金額劃分出幾個(gè)金額區(qū)間，例如1到100元的放到一個(gè)文件中，100到200元的放到另一個(gè)文件中，以此類推，這樣每個(gè)小文件都可以加載到內(nèi)存中，最后將這些小文件合并，就得到有序的10G訂單數(shù)據(jù)了。
- 如果訂單數(shù)據(jù)存儲(chǔ)在類似于GFS的分布式系統(tǒng)上，就可以將多個(gè)小文件并行加載到多臺(tái)機(jī)器上并行處理，這樣處理速度就會(huì)加快很多，這就是分治思想的一個(gè)應(yīng)用。
第二十八章 回溯算法
第二十九章 初始動(dòng)態(tài)規(guī)劃
第三十章 動(dòng)態(tài)規(guī)劃實(shí)戰(zhàn)
第三十一章 拓?fù)渑判?/h4>
一、什么是拓?fù)渑判颍?/h6>
- 從局部有序推斷出全局的順序就叫做拓?fù)渑判?/strong>，例如，我們穿衣服的時(shí)候是有一定順序的，你必須先穿襪子才能穿鞋，你必須先穿內(nèi)褲才能穿秋褲，假設(shè)我們有8件衣服，可以按照下面的順序進(jìn)行穿衣服，就可以滿足局部關(guān)系的前提下滿足全局有序。
![]()
拓?fù)渑判?png
- 我們知道，算法是構(gòu)建在具體數(shù)據(jù)結(jié)構(gòu)之上的，我們想進(jìn)行拓?fù)渑判?，就需要先把?wèn)題背景抽象成具體的數(shù)據(jù)結(jié)構(gòu)，我們把衣服之間的依賴關(guān)系抽象成一個(gè)有向圖，每件衣服對(duì)應(yīng)圖中的一個(gè)點(diǎn)，依賴關(guān)系就是頂點(diǎn)之間的邊，而且這個(gè)圖不僅是有向圖，還得是有向無(wú)環(huán)圖，因?yàn)閳D中一旦有了環(huán)，就無(wú)法進(jìn)行拓?fù)渑判蛄?，所以拓?fù)渑判蚴腔?strong>有向無(wú)環(huán)圖的一個(gè)算法。抽象成的數(shù)據(jù)結(jié)構(gòu)如下：
public class Graph {
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) { // s先于t，邊s->t
adj[s].add(t);
}
}
二、如何在有向無(wú)環(huán)圖上進(jìn)行拓?fù)渑判颍?/h6>
-
- Kahn算法
(1). 我們從圖中找到入度為0的頂點(diǎn)，進(jìn)行輸出（如果一個(gè)頂點(diǎn)的入度為0，就意味著沒(méi)有頂點(diǎn)先于這個(gè)頂點(diǎn)了，所以這個(gè)頂點(diǎn)就應(yīng)該輸出了），并且把這個(gè)頂點(diǎn)從圖中刪除，即把這個(gè)頂點(diǎn)可達(dá)的頂點(diǎn)的入度都減一；
(2). 然后我們重復(fù)上述過(guò)程，直到輸出所有頂點(diǎn)，這樣輸出的序列就是拓?fù)渑判蛑蟮男蛄辛恕＃ㄝ敵龅男蛄芯褪菨M足局部依賴關(guān)系的全局序列）
(3). 具體代碼實(shí)現(xiàn)如下
public void topoSortByKahn() {
int[] inDegree = new int[v]; // 統(tǒng)計(jì)每個(gè)頂點(diǎn)的入度
for (int i = 0; i < v; ++i) {
for (int j = 0; j < adj[i].size(); ++j) {
int w = adj[i].get(j); // i->w
inDegree[w]++;
}
}
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < v; ++i) {
if (inDegree[i] == 0) queue.add(i);
}
while (!queue.isEmpty()) {
int i = queue.remove();
System.out.print("->" + i);
for (int j = 0; j < adj[i].size(); ++j) {
int k = adj[i].get(j);
inDegree[k]--;
if (inDegree[k] == 0) queue.add(k);
}
}
}
-
- DFS算法
- (1). 首先根據(jù)鄰接表，構(gòu)造出逆鄰接表，在逆鄰接表中，邊s->t表示s依賴于t，也就是s后于t執(zhí)行。
- (2). 然后我們遞歸處理每個(gè)頂點(diǎn)，先輸出這個(gè)頂點(diǎn)可以到達(dá)的所有頂點(diǎn)，然后在輸出它自己。
- (3). 代碼實(shí)現(xiàn)如下：
public void topoSortByDFS() {
// 先構(gòu)建逆鄰接表，邊s->t表示，s依賴于t，t先于s
LinkedList<Integer> inverseAdj[] = new LinkedList[v];
for (int i = 0; i < v; ++i) { // 申請(qǐng)空間
inverseAdj[i] = new LinkedList<>();
}
for (int i = 0; i < v; ++i) { // 通過(guò)鄰接表生成逆鄰接表
for (int j = 0; j < adj[i].size(); ++j) {
int w = adj[i].get(j); // i->w
inverseAdj[w].add(i); // w->i
}
}
boolean[] visited = new boolean[v];
for (int i = 0; i < v; ++i) { // 深度優(yōu)先遍歷圖
if (visited[i] == false) {
visited[i] = true;
dfs(i, inverseAdj, visited);
}
}
}
private void dfs(
int vertex, LinkedList<Integer> inverseAdj[], boolean[] visited) {
for (int i = 0; i < inverseAdj[vertex].size(); ++i) {
int w = inverseAdj[vertex].get(i);
if (visited[w] == true) continue;
visited[w] = true;
dfs(w, inverseAdj, visited);
} // 先把vertex這個(gè)頂點(diǎn)可達(dá)的所有頂點(diǎn)都打印出來(lái)之后，再打印它自己
System.out.print("->" + vertex);
}
三、Kahn算法和DFS算法進(jìn)行拓?fù)渑判虻臅r(shí)間復(fù)雜度
- 從Kahn算法的代碼中可以看出，每個(gè)頂點(diǎn)和每條邊都被訪問(wèn)了一次，所以時(shí)間復(fù)雜度是O(V+E)，V是頂點(diǎn)個(gè)數(shù)，E是邊的個(gè)數(shù)
- 從DFS算法可以看出，每個(gè)頂點(diǎn)被訪問(wèn)兩次，每條邊被訪問(wèn)一次，所以時(shí)間復(fù)雜度也是O(V+E)，V是頂點(diǎn)個(gè)數(shù)，E是邊的個(gè)數(shù)
- 如果我們想知道數(shù)據(jù)庫(kù)中所有用戶的推薦關(guān)系之間，有沒(méi)有存在環(huán)，就可以使用拓?fù)渑判颍延脩糁g的的推薦關(guān)系從數(shù)據(jù)庫(kù)加載到內(nèi)存中，構(gòu)建成今天所講的這種有向圖數(shù)據(jù)結(jié)構(gòu)，再利用拓?fù)渑判颍涂梢院芸鞕z測(cè)出是否存在環(huán)了。
第三十二章 最短路徑
第三十三章 位圖
- 從局部有序推斷出全局的順序就叫做拓?fù)渑判?/strong>，例如，我們穿衣服的時(shí)候是有一定順序的，你必須先穿襪子才能穿鞋，你必須先穿內(nèi)褲才能穿秋褲，假設(shè)我們有8件衣服，可以按照下面的順序進(jìn)行穿衣服，就可以滿足局部關(guān)系的前提下滿足全局有序。
拓?fù)渑判?png
- 從局部有序推斷出全局的順序就叫做拓?fù)渑判?/strong>，例如，我們穿衣服的時(shí)候是有一定順序的，你必須先穿襪子才能穿鞋，你必須先穿內(nèi)褲才能穿秋褲，假設(shè)我們有8件衣服，可以按照下面的順序進(jìn)行穿衣服，就可以滿足局部關(guān)系的前提下滿足全局有序。
- 我們知道，算法是構(gòu)建在具體數(shù)據(jù)結(jié)構(gòu)之上的，我們想進(jìn)行拓?fù)渑判?，就需要先把?wèn)題背景抽象成具體的數(shù)據(jù)結(jié)構(gòu)，我們把衣服之間的依賴關(guān)系抽象成一個(gè)有向圖，每件衣服對(duì)應(yīng)圖中的一個(gè)點(diǎn)，依賴關(guān)系就是頂點(diǎn)之間的邊，而且這個(gè)圖不僅是有向圖，還得是有向無(wú)環(huán)圖，因?yàn)閳D中一旦有了環(huán)，就無(wú)法進(jìn)行拓?fù)渑判蛄?，所以拓?fù)渑判蚴腔?strong>有向無(wú)環(huán)圖的一個(gè)算法。抽象成的數(shù)據(jù)結(jié)構(gòu)如下：
public class Graph {
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) { // s先于t，邊s->t
adj[s].add(t);
}
}
二、如何在有向無(wú)環(huán)圖上進(jìn)行拓?fù)渑判颍?/h6>
-
- Kahn算法
(1). 我們從圖中找到入度為0的頂點(diǎn)，進(jìn)行輸出（如果一個(gè)頂點(diǎn)的入度為0，就意味著沒(méi)有頂點(diǎn)先于這個(gè)頂點(diǎn)了，所以這個(gè)頂點(diǎn)就應(yīng)該輸出了），并且把這個(gè)頂點(diǎn)從圖中刪除，即把這個(gè)頂點(diǎn)可達(dá)的頂點(diǎn)的入度都減一；
(2). 然后我們重復(fù)上述過(guò)程，直到輸出所有頂點(diǎn)，這樣輸出的序列就是拓?fù)渑判蛑蟮男蛄辛恕＃ㄝ敵龅男蛄芯褪菨M足局部依賴關(guān)系的全局序列）
(3). 具體代碼實(shí)現(xiàn)如下
public void topoSortByKahn() {
int[] inDegree = new int[v]; // 統(tǒng)計(jì)每個(gè)頂點(diǎn)的入度
for (int i = 0; i < v; ++i) {
for (int j = 0; j < adj[i].size(); ++j) {
int w = adj[i].get(j); // i->w
inDegree[w]++;
}
}
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < v; ++i) {
if (inDegree[i] == 0) queue.add(i);
}
while (!queue.isEmpty()) {
int i = queue.remove();
System.out.print("->" + i);
for (int j = 0; j < adj[i].size(); ++j) {
int k = adj[i].get(j);
inDegree[k]--;
if (inDegree[k] == 0) queue.add(k);
}
}
}
-
- DFS算法
- (1). 首先根據(jù)鄰接表，構(gòu)造出逆鄰接表，在逆鄰接表中，邊s->t表示s依賴于t，也就是s后于t執(zhí)行。
- (2). 然后我們遞歸處理每個(gè)頂點(diǎn)，先輸出這個(gè)頂點(diǎn)可以到達(dá)的所有頂點(diǎn)，然后在輸出它自己。
- (3). 代碼實(shí)現(xiàn)如下：
public void topoSortByDFS() {
// 先構(gòu)建逆鄰接表，邊s->t表示，s依賴于t，t先于s
LinkedList<Integer> inverseAdj[] = new LinkedList[v];
for (int i = 0; i < v; ++i) { // 申請(qǐng)空間
inverseAdj[i] = new LinkedList<>();
}
for (int i = 0; i < v; ++i) { // 通過(guò)鄰接表生成逆鄰接表
for (int j = 0; j < adj[i].size(); ++j) {
int w = adj[i].get(j); // i->w
inverseAdj[w].add(i); // w->i
}
}
boolean[] visited = new boolean[v];
for (int i = 0; i < v; ++i) { // 深度優(yōu)先遍歷圖
if (visited[i] == false) {
visited[i] = true;
dfs(i, inverseAdj, visited);
}
}
}
private void dfs(
int vertex, LinkedList<Integer> inverseAdj[], boolean[] visited) {
for (int i = 0; i < inverseAdj[vertex].size(); ++i) {
int w = inverseAdj[vertex].get(i);
if (visited[w] == true) continue;
visited[w] = true;
dfs(w, inverseAdj, visited);
} // 先把vertex這個(gè)頂點(diǎn)可達(dá)的所有頂點(diǎn)都打印出來(lái)之后，再打印它自己
System.out.print("->" + vertex);
}
三、Kahn算法和DFS算法進(jìn)行拓?fù)渑判虻臅r(shí)間復(fù)雜度
- 從Kahn算法的代碼中可以看出，每個(gè)頂點(diǎn)和每條邊都被訪問(wèn)了一次，所以時(shí)間復(fù)雜度是O(V+E)，V是頂點(diǎn)個(gè)數(shù)，E是邊的個(gè)數(shù)
- 從DFS算法可以看出，每個(gè)頂點(diǎn)被訪問(wèn)兩次，每條邊被訪問(wèn)一次，所以時(shí)間復(fù)雜度也是O(V+E)，V是頂點(diǎn)個(gè)數(shù)，E是邊的個(gè)數(shù)
- 如果我們想知道數(shù)據(jù)庫(kù)中所有用戶的推薦關(guān)系之間，有沒(méi)有存在環(huán)，就可以使用拓?fù)渑判颍延脩糁g的的推薦關(guān)系從數(shù)據(jù)庫(kù)加載到內(nèi)存中，構(gòu)建成今天所講的這種有向圖數(shù)據(jù)結(jié)構(gòu)，再利用拓?fù)渑判颍涂梢院芸鞕z測(cè)出是否存在環(huán)了。
第三十二章 最短路徑
第三十三章 位圖
- Kahn算法
(1). 我們從圖中找到入度為0的頂點(diǎn)，進(jìn)行輸出（如果一個(gè)頂點(diǎn)的入度為0，就意味著沒(méi)有頂點(diǎn)先于這個(gè)頂點(diǎn)了，所以這個(gè)頂點(diǎn)就應(yīng)該輸出了），并且把這個(gè)頂點(diǎn)從圖中刪除，即把這個(gè)頂點(diǎn)可達(dá)的頂點(diǎn)的入度都減一；
(2). 然后我們重復(fù)上述過(guò)程，直到輸出所有頂點(diǎn)，這樣輸出的序列就是拓?fù)渑判蛑蟮男蛄辛恕＃ㄝ敵龅男蛄芯褪菨M足局部依賴關(guān)系的全局序列）
(3). 具體代碼實(shí)現(xiàn)如下
public void topoSortByKahn() {
int[] inDegree = new int[v]; // 統(tǒng)計(jì)每個(gè)頂點(diǎn)的入度
for (int i = 0; i < v; ++i) {
for (int j = 0; j < adj[i].size(); ++j) {
int w = adj[i].get(j); // i->w
inDegree[w]++;
}
}
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < v; ++i) {
if (inDegree[i] == 0) queue.add(i);
}
while (!queue.isEmpty()) {
int i = queue.remove();
System.out.print("->" + i);
for (int j = 0; j < adj[i].size(); ++j) {
int k = adj[i].get(j);
inDegree[k]--;
if (inDegree[k] == 0) queue.add(k);
}
}
}
- DFS算法
- (1). 首先根據(jù)鄰接表，構(gòu)造出逆鄰接表，在逆鄰接表中，邊s->t表示s依賴于t，也就是s后于t執(zhí)行。
- (2). 然后我們遞歸處理每個(gè)頂點(diǎn)，先輸出這個(gè)頂點(diǎn)可以到達(dá)的所有頂點(diǎn)，然后在輸出它自己。
- (3). 代碼實(shí)現(xiàn)如下：
public void topoSortByDFS() {
// 先構(gòu)建逆鄰接表，邊s->t表示，s依賴于t，t先于s
LinkedList<Integer> inverseAdj[] = new LinkedList[v];
for (int i = 0; i < v; ++i) { // 申請(qǐng)空間
inverseAdj[i] = new LinkedList<>();
}
for (int i = 0; i < v; ++i) { // 通過(guò)鄰接表生成逆鄰接表
for (int j = 0; j < adj[i].size(); ++j) {
int w = adj[i].get(j); // i->w
inverseAdj[w].add(i); // w->i
}
}
boolean[] visited = new boolean[v];
for (int i = 0; i < v; ++i) { // 深度優(yōu)先遍歷圖
if (visited[i] == false) {
visited[i] = true;
dfs(i, inverseAdj, visited);
}
}
}
private void dfs(
int vertex, LinkedList<Integer> inverseAdj[], boolean[] visited) {
for (int i = 0; i < inverseAdj[vertex].size(); ++i) {
int w = inverseAdj[vertex].get(i);
if (visited[w] == true) continue;
visited[w] = true;
dfs(w, inverseAdj, visited);
} // 先把vertex這個(gè)頂點(diǎn)可達(dá)的所有頂點(diǎn)都打印出來(lái)之后，再打印它自己
System.out.print("->" + vertex);
}
- 從Kahn算法的代碼中可以看出，每個(gè)頂點(diǎn)和每條邊都被訪問(wèn)了一次，所以時(shí)間復(fù)雜度是O(V+E)，V是頂點(diǎn)個(gè)數(shù)，E是邊的個(gè)數(shù)
- 從DFS算法可以看出，每個(gè)頂點(diǎn)被訪問(wèn)兩次，每條邊被訪問(wèn)一次，所以時(shí)間復(fù)雜度也是O(V+E)，V是頂點(diǎn)個(gè)數(shù)，E是邊的個(gè)數(shù)
- 如果我們想知道數(shù)據(jù)庫(kù)中所有用戶的推薦關(guān)系之間，有沒(méi)有存在環(huán)，就可以使用拓?fù)渑判颍延脩糁g的的推薦關(guān)系從數(shù)據(jù)庫(kù)加載到內(nèi)存中，構(gòu)建成今天所講的這種有向圖數(shù)據(jù)結(jié)構(gòu)，再利用拓?fù)渑判颍涂梢院芸鞕z測(cè)出是否存在環(huán)了。
