導(dǎo)讀：隨著現(xiàn)代社會的發(fā)展，信息的形式和數(shù)量正在迅猛增長。其中很大一部分是圖像，圖像可以把事物生動地呈現(xiàn)在我們面前，讓我們更直觀地接受信息。

定義

? ? ? ? ?圖像處理（image processing）又稱為影像處理，是用計算機對圖像進行達到所需結(jié)果的技術(shù)。應(yīng)用廣泛，多用于測繪學(xué)、大氣科學(xué)、天文學(xué)、美圖、使圖像提高辨識等 圖像處理是對圖像進行分析、加工、和處理，使其滿足視覺、心理以及其他要求的技術(shù)。圖像處理是信號處理在圖像域上的一個應(yīng)用，目前大多數(shù)的圖像是以數(shù)字形式存儲，因而圖像處理很多情況下指數(shù)字圖像處理。?

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

? ? ? ?DFS（Depth-First-Search）深度優(yōu)先搜索，是計算機術(shù)語，是一種在開發(fā)爬蟲早期使用較多的方法，是搜索算法的一種。它的目的是要達到被搜索結(jié)構(gòu)的葉結(jié)點(即那些不包含任何超鏈的HTML文件) 。

深度優(yōu)先遍歷圖的算法是，假定給定圖G的初始狀態(tài)是所有頂點均未被訪問過，在G中任選一個頂點i作為遍歷的初始點，則深度優(yōu)先搜索遞歸調(diào)用步驟：

1、訪問搜索到的未被訪問的鄰接點；

2、將此頂點標(biāo)記為已訪問節(jié)點；

3、搜索該頂點的未被訪問的鄰接點，若該鄰接點存在，則從此鄰接點開始進行同樣的訪問和搜索，反復(fù)進行直到所有節(jié)點都被訪問為止。?

算法詳解:

? ? ? ?首先選定圖的類別（有向圖、無向圖），再選定圖的存儲結(jié)構(gòu)，根據(jù)輸入的頂點或者邊建立圖；并把相應(yīng)的鄰接表或者鄰接矩陣輸出；

根據(jù)已有的鄰接矩陣或鄰接表用遞歸方法編寫深度優(yōu)先搜索遍歷算法，并輸出遍歷結(jié)果；

圖的深度遍歷原則：

1 如果有可能，訪問一個領(lǐng)接的未訪問的節(jié)點，標(biāo)記它，并把它放入棧中。

2 當(dāng)不能執(zhí)行規(guī)則 1 時，如果棧不為空，則從棧中彈出一個元素。

3 如果不能執(zhí)行規(guī)則 1 和規(guī)則 2 時，則完成了遍歷。

代碼中的圖使用的是Graph 圖－鄰接矩陣法 來表示，其他的表示法請見：Graph 圖－鄰接表法

代碼中的Stack為輔助結(jié)構(gòu)，用來記載訪問過的節(jié)點。棧的詳細描述可以見：ArrayStack 棧 ，LinkedStack 棧 。

Vertex表示圖中的節(jié)點，其中包含訪問，是否訪問，清除訪問標(biāo)志的方法。 Graph.main：提供簡單測試。代碼可以以指定下標(biāo)的節(jié)點開始作深度遍歷。 代碼比較簡單，除了Graph.dsf(int i)深度優(yōu)先遍歷算法外沒有過多注釋。

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

? ? ? ??廣度優(yōu)先搜索算法（英語：Breadth-First-Search，縮寫為BFS），又譯作寬度優(yōu)先搜索，或橫向優(yōu)先搜索，是一種圖形搜索算法。簡單的說，BFS是從根節(jié)點開始，沿著樹的寬度遍歷樹的節(jié)點。如果所有節(jié)點均被訪問，則算法中止。廣度優(yōu)先搜索的實現(xiàn)一般采用open-closed表。

作法:

BFS是一種盲目搜索法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能地址，徹底地搜索整張圖，直到找到結(jié)果為止。BFS并不使用經(jīng)驗法則算法。

從算法的觀點，所有因為展開節(jié)點而得到的子節(jié)點都會被加進一個先進先出的隊列中。一般的實現(xiàn)里，其鄰居節(jié)點尚未被檢驗過的節(jié)點會被放置在一個被稱為 open 的容器中（例如隊列或是鏈表），而被檢驗過的節(jié)點則被放置在被稱為 closed 的容器中。（open-closed表）

A*搜索算法?

? ? ? ? A*算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法。之后涌現(xiàn)了很多預(yù)處理算法（ALT，CH，HL等等），在線查詢效率是A*算法的數(shù)千甚至上萬倍。

A*算法操作：首先將起始結(jié)點S放入OPEN表，CLOSE表置空，算法描述：

1、如果OPEN表不為空，從表頭取一個結(jié)點n，如果為空算法失敗。

2、n是目標(biāo)解嗎？是，找到一個解（繼續(xù)尋找，或終止算法）。

3、將n的所有后繼結(jié)點展開，就是從n可以直接關(guān)聯(lián)的子結(jié)點，如果不在CLOSE表中，就將它們放入OPEN表，并把S放入CLOSE表，同時計算每一個后繼結(jié)點的估價值f(n)，將OPEN表按f(x)排序，最小的放在表頭，重復(fù)算法，回到1。

Dijkstra算法

? ? ? ?戴克斯特拉算法（又譯迪杰斯特拉算法） 是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

Dijkstra算法采用的是一種貪心的策略，基本算法思想：

1、通過Dijkstra計算圖G中的最短路徑時，需要指定起點s。

2、引進兩個集合S和U。S的作用是記錄已求出最短路徑的頂點，而U則是記錄還未求出最短路徑的頂點。

3、初始時，S中只有起點s，U中是除s之外的頂點，并且U中頂點的路徑是"起點s到該頂點的路徑"。然后，從U中找出路徑最短的頂點，并將其加入到S中；更新U中的頂點和頂點對應(yīng)的路徑。 … 重復(fù)該操作，直到遍歷完所有頂點。?

Bellman-Ford算法?

? ? ? ? Bellman - ford算法是求含負權(quán)圖的單源最短路徑的一種算法，其原理為連續(xù)進行松弛，在每次松弛時把每條邊都更新一下，若在n-1次松弛后還能更新，則說明圖中有負環(huán)，因此無法得出結(jié)果，否則就完成。

Bellman-Ford算法能在更普遍的情況下解決單源點最短路徑問題，算法描述：

1、初始化：將除源點外的所有頂點的最短距離估計值。

2、迭代求解：反復(fù)對邊集E中的每條邊進行松弛操作，使得頂點集V中的每個頂點v的最短距離估計值逐步逼近其最短距離。

3、檢驗負權(quán)回路：判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點，則算法返回false，表明問題無解。否則算法返回true，并且從源點可達的頂點v的最短距離保存在集合dist[v]中。

Floyd-Warshall算法

? ? ? Floyd-Warshall算法是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權(quán)的最短路徑問題。

算法思想：

1、創(chuàng)建源頂點 v 到圖中所有頂點的距離的集合S，為圖中的所有頂點指定一個距離值，初始均為I，源頂點距離為0。

2、計算最短路徑，執(zhí)行 V - 1 次遍歷。

3、對于圖中的每條邊：如果起點u的距離d 加上邊的權(quán)值w小于終點v的距離d，則更新終點v的距離值d。

4.檢測圖中是否有負權(quán)邊形成了環(huán)，遍歷圖中的所有邊，計算u至v的距離，如果對于v存在更小的距離，則說明存在環(huán)。?

Prim算法

? ? ? ?圖論的一種算法，可在加權(quán)連通圖里搜索最小生成樹。由此算法搜索到的邊子集所構(gòu)成的樹中，不但包括了連通圖里的所有頂點，且其所有邊的權(quán)值之和亦為最小。

Prim算法在找當(dāng)前最近頂點時使用到了貪婪算法，算法描述：

1、 在一個加權(quán)連通圖中，頂點集合V，邊集合為E。

2、任意選出一個點作為初始頂點,標(biāo)記為visit,計算所有與之相連接的點的距離，選擇距離最短的，標(biāo)記visit。

3、在剩下的點，計算與已標(biāo)記visit點距離最小的點，標(biāo)記visit,證明加入了最小生成樹，重復(fù)操作，直到所有點都被標(biāo)記為visit。

Kruskal算法?

? ? ? Kruskal算法是一種用來尋找最小生成樹的算法,在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構(gòu)成回路，則放棄，選取次小邊。

Kruskal算法就是基于并查集的貪心算法,算法描述：

1、將圖G看做一個森林，每個頂點為一棵獨立的樹。

2、將所有的邊加入集合S，即一開始S = E 。

3、從S中拿出一條最短的邊(u,v)，如果(u,v)不在同一棵樹內(nèi)，則連接u,v合并這兩棵樹，同時將(u,v)加入生成樹的邊集E'。

4、重復(fù)3直到所有點屬于同一棵樹，邊集E'就是一棵最小生成樹。

匈牙利算法

? ? ?匈牙利算法是一種在多項式時間內(nèi)求解任務(wù)分配問題的組合優(yōu)化算法，并推動了后來的原始對偶方法。美國數(shù)學(xué)家哈羅德·庫恩于1955年提出該算法。此算法之所以被稱作匈牙利算法，是因為算法很大一部分是基于以前匈牙利數(shù)學(xué)家Dénes K?nig和Jen? Egerváry的工作之上創(chuàng)建起來的。?

算法輪廓：

1、置M為空

2、找出一條增廣路徑P，通過異或操作獲得更大的匹配M'代替M.

3、重復(fù)2操作直到找不出增廣路徑為止。

Ford-Fulkerson算法

? ? ? ?也稱最大流量算法，常用于作為一個距離向量路由協(xié)議例如RIP， BGP， ISO IDRP， NOVELL IPX的算法。

Ford-Fulkerson 算法是一種迭代方法。開始時，對所有 u, v ∈ V 有 f(u, v) = 0，即初始狀態(tài)時流的值為 0。在每次迭代中，可通過尋找一條增廣路徑來增加流值。增廣路徑可以看做是從源點 s 到匯點 t 之間的一條路徑，沿該路徑可以壓入更多的流，從而增加流的值。反復(fù)進行這一過程，直至增廣路徑都被找出為止。

復(fù)雜:

? ? ? ?通過將流量增加路徑添加到已在圖中建立的流量，當(dāng)在圖表中不再能夠找到流量增加路徑時，將達到最大流量。但是，無法確定是否會達到這種情況，因此可以保證的最佳方案是，如果算法終止，答案將是正確的。在算法永遠運行的情況下，流可能甚至不會收斂到最大流量。但是，這種情況只發(fā)生在不合理的流量值。當(dāng)容量為整數(shù)時，F(xiàn)ord-Fulkerson的運行時間受O（E f）的限制（參見大O表示法），其中E是數(shù)字圖中的邊和f是圖中的最大流量。這是因為每個擴充路徑都可以在O（E））時間內(nèi)找到并且將流量增加至少1 的整數(shù)量，其上限f 。

? ? ? ?具有保證終止和獨立于最大流量值的運行時間的Ford-Fulkerson算法的變體是Edmonds-Karp算法，該算法在中運行O(VE2)時間。?

需要人工智能學(xué)習(xí)資料的可以關(guān)注微信公眾號：AI技術(shù)星球? 回復(fù)：211? 領(lǐng)取

100G入門到進階AI資源包+專家一對一論文指導(dǎo)/TOP大佬帶隊kaggle/就業(yè)指導(dǎo)+技術(shù)問題答疑

1、超詳細的人工智能學(xué)習(xí)路線

2、OpenCV、Pytorch、YOLO等主流框架算法實戰(zhàn)教程

3、人工智能快速入門視頻教程合集（Python基礎(chǔ)、數(shù)學(xué)基礎(chǔ)、NLP）附源碼課件數(shù)據(jù)

4、機器學(xué)習(xí)算法+深度學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)基礎(chǔ)教程

5、人工智能必看書籍（花書、西瓜書、蜥蜴書等）

6、上千篇CVPR、ICCV頂會論文

7、人工智能行業(yè)報告?