特點(diǎn)

? ? 一種更加復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)

? ? 名詞解釋

? ??????頂點(diǎn)(vertex): 圖中的元素

? ? ? ? 邊(edge): 圖中的一個(gè)頂點(diǎn)可以與任意其他頂點(diǎn)建立連接關(guān)系

? ??????度(degree):?跟頂點(diǎn)相連接的邊的條數(shù)

? ??????有向圖: 邊有方向的圖

? ??????無向圖:?邊沒有方向的圖

? ? ? ? 入度(In-degree): 有多少條邊指向這個(gè)頂點(diǎn)

? ? ? ? 出度(Out-degree):?有多少條邊是以這個(gè)頂點(diǎn)為起點(diǎn)指向其他頂點(diǎn)

有向圖

? ??????????帶權(quán)圖(weighted graph):?在帶權(quán)圖中每條邊都有一個(gè)權(quán)重(weight)

? ??內(nèi)存中存儲(chǔ)圖這種數(shù)據(jù)結(jié)構(gòu)方法

? ? ? ? 1.鄰接矩陣(Adjacency Matrix)存儲(chǔ)

? ??????????鄰接矩陣的底層依賴一個(gè)二維數(shù)組

????????????對(duì)于無向圖來說恕刘，如果頂點(diǎn)i與頂點(diǎn)j之間有邊积担，就將A[i][j]和A[j][i]標(biāo)記為1庆杜；

????????????對(duì)于有向圖來說伯病，如果有一條箭頭從頂點(diǎn)i指向頂點(diǎn)j的邊逛球，就將A[i][j]標(biāo)記為1蕴忆；

????????????同理仗岖，如果有一條箭頭從頂點(diǎn)j指向頂點(diǎn)i的邊，我們就將A[j][i]標(biāo)記為1刃鳄。

????????????對(duì)于帶權(quán)圖盅弛，數(shù)組中就存儲(chǔ)相應(yīng)的權(quán)重

鄰接矩陣存儲(chǔ)方法

? ? ? ? ? ? 無向圖中，adj[0][0]沒邊為0，adj[0][1]有邊為1挪鹏，adj[0][2]有邊為1见秽，adj[0][3]無邊為0

? ? ? ? ? ? 總結(jié)

? ??????????????1.存儲(chǔ)方式簡單、直接讨盒，因?yàn)榛跀?shù)組在獲取兩個(gè)頂點(diǎn)的關(guān)系非常高效

????????????????2.方便計(jì)算解取，可以將很多圖的運(yùn)算轉(zhuǎn)換成矩陣之間的運(yùn)算

????????????????????比如求解最短路徑問題的Floyd-Warshall算法，利用矩陣循環(huán)相乘若干次得到結(jié)果

? ? ? ? ? ? ? ? 3.比較浪費(fèi)存儲(chǔ)空間返顺，特別針對(duì)稀疏圖(Sparse Matrix): 頂點(diǎn)很多但每個(gè)頂點(diǎn)邊不多

????????2.鄰接表(Adjacency List)存儲(chǔ)

? ? ? ? ? ? 每個(gè)頂點(diǎn)對(duì)應(yīng)一條鏈表禀苦，鏈表中存儲(chǔ)的是與這個(gè)頂點(diǎn)相連接的其他頂點(diǎn)

????????????有向圖: 每個(gè)頂點(diǎn)對(duì)應(yīng)的鏈表里面，存儲(chǔ)的是指向的頂點(diǎn)

? ? ? ? ? ? 無向圖:?每個(gè)頂點(diǎn)對(duì)應(yīng)的鏈表里面遂鹊，存儲(chǔ)的是跟這個(gè)頂點(diǎn)有邊相連的頂點(diǎn)

有向鄰接表

? ? ? ? ? ? 總結(jié)

? ??????????????鄰接表存儲(chǔ)起來比較節(jié)省空間振乏，但使用比較耗時(shí)

? ??????????????鏈表的存儲(chǔ)方式對(duì)緩存不友好，查詢兩個(gè)頂點(diǎn)之間的關(guān)系不高效

? ? ? ? ? ? ? ? 鄰接表升級(jí)(鏈表數(shù)據(jù)結(jié)構(gòu)替換)

? ? ? ? ? ? ? ? ? ? 1.換成平衡二叉查找樹(紅黑樹)秉扑，可以快速地查找兩個(gè)頂點(diǎn)之間是否存在邊了

? ? ? ? ? ? ? ? ? ? 2.換成其他動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu):?跳表慧邮、散列表等

? ? ? ? ? ? ? ? ? ? 3.有序動(dòng)態(tài)數(shù)組，可以通過二分查找的方法來快速定位兩個(gè)頂點(diǎn)之間否是存在邊

? ? ? ? 應(yīng)用場(chǎng)景

? ? ? ? ? ? 例如: 存儲(chǔ)微博(有向圖)舟陆、微信(無向圖)等社交網(wǎng)絡(luò)中的好友關(guān)系

? ? ? ? ? ? 針對(duì)微博用戶關(guān)系误澳，假設(shè)我們需要支持下面這樣幾個(gè)操作：

????????????????判斷用戶A是否關(guān)注了用戶B；

????????????????判斷用戶A是否是用戶B的粉絲秦躯；

????????????????用戶A關(guān)注用戶B忆谓；

????????????????用戶A取消關(guān)注用戶B；

????????????????根據(jù)用戶名稱的首字母排序踱承，分?獲取用戶的粉絲列表倡缠；

????????????????根據(jù)用戶名稱的首字母排序，分?獲取用戶的關(guān)注列表

? ??????????因社交網(wǎng)絡(luò)是一張稀疏圖勾扭，所以采用鄰接表來存儲(chǔ)

? ? ? ? ? ? 具體用鄰接表 + 逆鄰接表來存儲(chǔ)

? ??????????鄰接表中存儲(chǔ)了用戶的關(guān)注關(guān)系: 每個(gè)頂點(diǎn)的鏈表中毡琉，存儲(chǔ)這個(gè)頂點(diǎn)指向的頂點(diǎn)

????????????逆鄰接表中存儲(chǔ)了用戶被關(guān)注關(guān)系:?每個(gè)頂點(diǎn)的鏈表中，存儲(chǔ)指向這個(gè)頂點(diǎn)的頂點(diǎn)

鄰接表 & 逆鄰接表

? ??????????鄰接表不適合快速判斷兩用戶之間關(guān)系妙色，將鏈表改為支持快速查找的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)

? ??????????因?yàn)樾枰凑沼脩裘Q的首字母排序，分?來獲取用戶的粉絲列表或者關(guān)注列表

????????????????用跳表最合適慧耍。因跳表插入身辨、刪除、查找時(shí)間復(fù)雜度是O(logn)芍碧，空間復(fù)雜度上是O(n)

????????????????最重要一點(diǎn)煌珊，跳表中存儲(chǔ)的數(shù)據(jù)本來有序，分?獲取粉絲列表或關(guān)注列表泌豆，非常高效

????????????如果對(duì)于小規(guī)模的數(shù)據(jù),可以將整個(gè)社交關(guān)系存儲(chǔ)在內(nèi)存中

? ? ? ? ? ? 如果數(shù)據(jù)規(guī)模太大定庵，

? ? ? ? ? ? ? ? 方式一: 可以通過哈希算法等數(shù)據(jù)分片方式，將鄰接表存儲(chǔ)在不同的機(jī)器上

? ? ? ? ? ? ? ? ????查詢頂點(diǎn)之間關(guān)系時(shí)，先用同樣哈希算法定位頂點(diǎn)所在機(jī)器蔬浙，再在相應(yīng)機(jī)器上查找

采用數(shù)據(jù)分片方式存儲(chǔ)

? ? ? ? ? ? ????方式二: 利用外部存儲(chǔ)(例如:硬盤)

? ??????????????????例如:?數(shù)據(jù)庫存儲(chǔ)方式:?為了高效地支持前面定義的操作猪落，可以在表上建立多個(gè)索引

總結(jié)

? ??概念：無向圖、有向圖畴博、帶權(quán)圖笨忌、頂點(diǎn)、邊俱病、度官疲、入度、出度

? ??存儲(chǔ)方式：鄰接矩陣和鄰接表

? ??????鄰接矩陣存儲(chǔ)方法的缺點(diǎn)是比較浪費(fèi)空間亮隙，但是優(yōu)點(diǎn)是查詢效率高途凫，而且方便矩陣運(yùn)算

? ??????鄰接表存儲(chǔ)方式比較節(jié)省存儲(chǔ)空間，但鏈表不方便查找溢吻，查詢效率沒有鄰接矩陣高

? ??????????改進(jìn)升級(jí): 將鏈表換成更加高效動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)维费，比如平衡二叉查找樹、跳表煤裙、散列表等

搜索算法

? ??算法是作用于具體數(shù)據(jù)結(jié)構(gòu)之上掩完，深度優(yōu)先和廣度優(yōu)先搜索算法都是基于“圖”這種數(shù)據(jù)結(jié)構(gòu)

????圖數(shù)據(jù)結(jié)構(gòu)的表達(dá)能力很強(qiáng)，大部分涉及搜索的場(chǎng)景都可以抽象成“圖”

? ??圖上的搜索算法硼砰，最直接的理解: 在圖中找出從一個(gè)頂點(diǎn)出發(fā)且蓬，到另一個(gè)頂點(diǎn)的路徑

? ??包括: 深度優(yōu)先、廣度優(yōu)先搜索题翰、啟發(fā)式搜索

? ??深度優(yōu)先搜索算法和廣度優(yō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) { //無向圖一條邊存兩次

? ? ????????adj[s].add(t);

? ? ????????adj[t].add(s);

? ????}

????}

廣度優(yōu)先搜索(Breadth-First-Search)

? ? 一種“地毯式”層層推進(jìn)搜索策略豹障，先查找離起始頂點(diǎn)最近的冯事，然后是次近的，依次往外搜索??

BFS搜索算法分解圖(無向圖)

????bfs()函數(shù)就是基于之前定義的血公，圖的廣度優(yōu)先搜索的代碼實(shí)現(xiàn)昵仅。

????其中s表示起始頂點(diǎn)，t表示終止頂點(diǎn)累魔。我們搜索一條從s到t的路徑摔笤。

????實(shí)際上，這樣求得的路徑就是從s到t的最短路徑

? ??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);

????}

????visited用來記錄已經(jīng)被訪問的頂點(diǎn)垦写，如果頂點(diǎn)q被訪問吕世，那相應(yīng)的visited[q]會(huì)被設(shè)置為true

? ??queue是隊(duì)列，用來存儲(chǔ)已經(jīng)被訪問但相連的頂點(diǎn)還沒有被訪問的頂點(diǎn)來實(shí)現(xiàn)記錄的功能

????prev用來記錄搜索路徑梯投。當(dāng)我們從頂點(diǎn)s開始搜索到頂點(diǎn)t后命辖，prev數(shù)組中存儲(chǔ)的是搜索路徑

? ??????這個(gè)路徑是反向存儲(chǔ)的况毅，prev[w]存儲(chǔ)的是，頂點(diǎn)w是從哪個(gè)前驅(qū)頂點(diǎn)遍歷過來的

廣度優(yōu)先搜索分解圖1

廣度優(yōu)先搜索分解圖2

? ? 時(shí)間復(fù)雜度

? ??????最壞情況下尔艇，終止頂點(diǎn)t離起始頂點(diǎn)s很遠(yuǎn)尔许，需要遍歷完整個(gè)圖才能找到

? ??????這時(shí)每個(gè)頂點(diǎn)都要進(jìn)出一遍隊(duì)列，每個(gè)邊也都會(huì)被訪問一次漓帚，所以時(shí)間復(fù)雜度是O(V+E)

? ??????其中V表示頂點(diǎn)的個(gè)數(shù)母债，E表示邊的個(gè)數(shù)，因E>=V尝抖，所以可以簡寫為O(E)

????空間復(fù)雜度

????????空間消耗主要在幾個(gè)輔助變量visited數(shù)組毡们、queue隊(duì)列、prev數(shù)組上昧辽。

????????這三個(gè)存儲(chǔ)空間的大小都不會(huì)超過頂點(diǎn)的個(gè)數(shù)衙熔，所以空間復(fù)雜度為O(V)

深度優(yōu)先搜索(Depth-First-Search)

? ??用的是一種比較著名的回溯思想，這種思想解決問題的過程非常適合用遞歸來實(shí)現(xiàn)

? ? 深度優(yōu)先搜索策略

????????從一個(gè)頂點(diǎn)隨意選擇一個(gè)路徑往下搜索搅荞，當(dāng)無法繼續(xù)時(shí)回退上一個(gè)頂點(diǎn)红氯，

????????換一條邊繼續(xù)，直到找到目標(biāo)頂點(diǎn)為止

深度優(yōu)先搜索策略

????????????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);

? ? ????????????????????}

? ????????????????}

????????????}

? ? ? ? 代碼實(shí)現(xiàn)用到prev咕痛、visited變量以及print()函數(shù)痢甘，跟廣度優(yōu)先搜索代碼實(shí)現(xiàn)里作用是一樣

? ??????有個(gè)特殊變量found，作用是當(dāng)我們已經(jīng)找到終止頂點(diǎn)t之后茉贡，就不再遞歸地繼續(xù)查找

? ? 時(shí)間復(fù)雜度

? ??????每條邊最多會(huì)被訪問兩次塞栅，一次是遍歷，一次是回退

? ??????時(shí)間復(fù)雜度是O(E)腔丧，E表示邊的個(gè)數(shù)

? ? 空間復(fù)雜度

? ??????消耗內(nèi)存主要是visited放椰、prev數(shù)組和遞歸調(diào)用棧

????????visited、prev數(shù)組大小跟頂點(diǎn)個(gè)數(shù)V成正比愉粤，遞歸調(diào)用棧最大深度不會(huì)超過頂點(diǎn)的個(gè)數(shù)

????????所以總空間復(fù)雜度為O(V)

總結(jié)

? ? 廣度優(yōu)先搜索和深度優(yōu)先搜索是圖上的兩種最常用砾医、最基本的搜索算法

????比起其他高級(jí)的搜索算法,比如A*、IDA*等衣厘，要簡單粗暴如蚜，所以也被叫作暴力搜索算法

? ??這兩種搜索算法僅適用于狀態(tài)空間不大，也就是說圖不大的搜索

? ??廣度優(yōu)先搜索

? ? ? ? 通俗來講: 地毯式層層推進(jìn)影暴，從起始頂點(diǎn)開始怖亭，依次往外遍歷

? ??????廣度優(yōu)先搜索需要借助隊(duì)列來實(shí)現(xiàn)，遍歷得到的路徑就是起始頂點(diǎn)到終止頂點(diǎn)的最短路徑

? ??????時(shí)間復(fù)雜度都是O(E)坤检，空間復(fù)雜度是O(V)

????深度優(yōu)先搜索

????????用的是回溯思想，非常適合用遞歸實(shí)現(xiàn)

? ??????深度優(yōu)先搜索是借助棧來實(shí)現(xiàn)的

? ??????時(shí)間復(fù)雜度都是O(E)期吓，空間復(fù)雜度是O(V)? ? ? ??