數據結構學習筆記（01背包問題/圖問題）

01背包問題:在M件物品取出若干件放在空間為W的背包里，每件物品的體積為W1，W2……Wn，與之相對應的價值為P1,P2……Pn。求如何安排能帶走最多價值的物品？

動態規劃解決背包問題：

設f(i,W)表示，從前i件物品中挑選一些，放進一個空間為W的背包中能獲得的最大總價值。

那么如果第i件物品也在最優解中，那么f(i,W)=f(i-1,W-Wi)+Pi，因為從最優解中吧i去掉，前面選中的物品肯定能使一個空間為W-Wi的背包價值最大化，不然它們也不會出現在最優解中。

而如果第i件物品不在最優解中，那么f(i,W)=f(i-1,W)，第i件物品沒有占用空間。

通過比較上面兩個表達式的大小可以決定第i個物品是不是在最優解中。這就形成了一個遞歸。

但是如果W<Wi，也就是這個背包裝不下第i個物品了，自然只能是f(i,W)=f(i-1,W)。

遞歸的終止條件是i=1.第一件物品如果能裝下，價值就是Pi,裝不下就是0.

有許多計算過程重復，可以把重復的f(i,w)保存下來降低復雜度。

圖：

圖可以用鄰接表法表示。每個點擁有一個數組，記錄了和它相鄰的點。

圖也可以用矩陣法表示，橫縱是各個點，如果這兩個點是相鄰的則矩陣的值為1，否則0。只需要對角線的一半，因為另一半是重復的。橫縱相同的點設為0.

廣度優先搜索BFS：

選取某一點作為源點開始搜索，每一輪將某個點所有相鄰的點搜索完畢(稱為將此點探索完畢)，然后從剩下未探索完畢點里選取一個作為下一輪探索的起點(選一個距離最近的，使用隊列維護)。

因為每個點只能被發現一次，每個點（除了源）都有確定的父結點，因此廣度優先搜索會形成一棵樹。（廣度優先樹）

具體算法：

每個點有除了數據域，有三個字段。第一個是顏色，白色的表示沒被發現，灰色的表示已經被發現了但是沒有探索完畢(會出現在待探索隊列中，或者剛出隊，是本輪搜索的起點。)，黑色的表示探索完畢(與其相鄰的點全部被發現了)。第二個字段表示點的父親(P,C相鄰，探索P周邊的時候第一次發現C使得C由白邊灰,則P是C的父親)。第三個結點表示深度(和源點的距離，兒子結點的深度為父親結點的深度加一)。從源點開始，對其所有相鄰的點進行搜索，每新發現一個點就涂成灰色，并且加入待探索隊列中。如果某點周邊探索完畢，此點就被涂成黑色，然后從隊列中取出一個來進行下一輪搜索，直到所有結點變黑，隊列中也變空，則整個圖搜索完畢。

深度優先搜索：

從源點開始搜索，如果其存在未被發現(白色)的相鄰點，就涂成灰色，并以那個點為起點繼續往深處探索(遞歸)。如果某個點的所有鄰點都被發現并且依次遞歸探索過了，那么把此點涂成黑色(形成了一棵樹，此結點是樹的根節點。)。如果地圖中還存在白色的點，那么設為源點開始新一輪搜索（又形成一棵樹）。因此深度優先搜索形成一個森林。

深度優先搜索會維護一個全局的時間戳變量，每次新發現一個點并開始一次遞歸搜索的時候時間戳自增一次。每個點會記錄兩個時間戳，一個是它被發現的時刻，一個是它被探索完畢的時刻（所有鄰點都變黑）

最小生成樹：能連通所有點，并且使得各邊權值和最小的樹.

構造最小生成樹使用貪心算法（貪心算法：每一步都采取對當前狀況最有利的選擇）。假設有一個邊的集合A，是一棵最小生成樹的一個子集。如果每次都能找到一條邊來加入A(稱為安全邊)，并且保證A依舊是某個最小生成樹的子集，那么最終就能構造出最小生成樹。

尋找安全邊的依據：A是某最小生成樹的子集，S是圖中的一個割集且S不妨害A（S沒有割到A的邊），那么S中權值最小的一條邊可以安全的加入A中而保持A的性質。

Kruskal算法:

并查集是一種維護集合關系的數據結構，能夠快速的判斷一個元素是否在某個集合中(或者兩個元素是否在同一個集合中)，以及將兩個集合合并起來。

Kruskal算法首先將每個點都生成一棵樹(一個并查集合)，然后按照權值由小到大遍歷各邊（安全邊）。如果某邊兩點屬于不同的并查集則合并兩個集合，直到最后形成一棵樹，也就是最小生成樹。

Prim算法:

把一個點作為樹的跟結點，從剩下的點里，每次選取一個離樹最近的點連入樹中，最終形成最小生成樹(最近的意思是說，把這個點連接到樹上的某個點，連線的權值最小。通常使用用斐波那契堆實現的最小優先隊列來維護剩余的點)

具體算法：每個點有一個d字段表示和樹的最小距離，初始時根結點的d設為0，其余結點的設為無窮大。每個結點還有一個p字段表示其父。準備一個以d為依據的最小優先隊列將圖中各點放入。

每次從最小優先隊列中取出一個點S并進行如下操作：

1.將S加入樹中(通過其父，隊列中第一個取出的是d為0的根節點，無父)

2.遍歷和S相鄰的結點，如果某個鄰結點C在隊列中且SC的權值比C的d字段要小，則將d字段降低為此權值(自然在隊列中的順序得到提升)，然后將C的父設為S。

單源最短路徑:求從某源點出發，到圖中各點的最短路徑(各邊權值不同)

最短估計路徑和松弛:給每個點一個屬性d，表示這個點距離源點的估計值，使得實際的最短路徑權值不會超過這個值.

對點u和v進行松弛，是有可能降低v點的路徑估計值的操作（d值）。如果d(v)>d(u)+uv，那么就將d(v)改為d(u)+uv，且將v的父設為u。意思是，u對v說，大哥啊，你原來的路太長了，改從我這經過吧！

對于從S到某一點v的最短路徑，從s開始一路松弛下去，最終v的d值一定等于最短路徑的權值。Dijkstra算法依據此條性質求最短路徑。

Dijkstra算法:（要求圖中不存在負權邊）

使用一個以d為依據的最小優先隊列來維護未求得最短路徑的各點(初始時，源點的d值為零,其余點的d值為無窮大)。每次從最小優先隊列取出一點，并對其相鄰的點依次進行松弛操作，以期降低估計值。這樣下次從隊列中取出的點就是剩余估計值最小的那個點，最小優先隊列可以保證對于某一條最短路徑而言，各點事依據估計值依次松弛下去的，最終估計值就是最短路徑的權值，并通過松弛得到的父子關系確定路徑。本質也是一種貪心策略。

最大流解決最大二分匹配問題:

流網絡：

一個有向圖，擁有一對源點s和匯點v,圖中每點都出現在s到v的一條路徑中。對每一點而言，凈流入為零（類似基爾霍夫電流定律）,每邊有個容量值(類似于線路的最大電流)，實際流量（類似于電流）不能超過容量。

殘留網絡，增廣路徑和最大流的Ford-Fulkerson方法：

一個流網絡的殘留網絡的每邊的權值等于容量-實際流量，反應了一個流量網絡還剩余的運載能力。殘留網絡中如果存在從源點到匯點的路徑，則成為增光路徑。順著此路徑增加沿路的流即可增加整個網絡的流。反復尋找增廣路徑并沿路增加，如果最終找不到增廣路徑了，說明已經找到了網絡的最大流。這個尋找最大流的方法就是Ford-Fulkerson方法。如果各路徑的容量是有理數，此方法一定可以找到最大流。如果各路徑是整數，復雜度則相對較低（每次增廣至少增加一個整數單位）

Edmonds-Karp算法：

對Ford-Fulkerson方法的改進，每次在殘留網絡中尋找增廣路徑時，是尋找一個源點到匯點的最短路徑。

Floyd-Warshall算法求兩點間最短路徑:

此算法通過動態規劃的方式，遞歸求得圖中任意兩點間的最短路徑。設某個圖中前k個頂點的集合為Ak，若從i到j有若干這樣的路徑：i到k之間的中間點必須從集合Ak中選取。那么用d(i,j,k)來表示這些路徑中最短的一條。顯然當k為圖的頂點樹的時候，d(i,j,k)就是i和j之間的最短路徑。

對于d(i,j,k),假如第k個點不i到j之間的中間點，那么d(i,j,k)=d(i,j,k-1),因為第k個點不影響路徑；如果第k個點是i到j的中間點，那么路徑分成兩半，每一半都是對應兩個端點間的最短路徑，因此d(i,j,k)=d(i,k,k)+d(k,j,k)。因此d(i,k,k)+d(k,j,k)和d(i,j,k-1)誰比較小，決定了第k個點是否在i到j的最短路徑上，形成遞歸。

遞歸的終止條件是k=0,此時沒有中間點（空集）,i和j直接相連，d(i,j,0)=W(i,j)，也就是ij線的距離。

另外當k為i或j本身時，k必然不在中間點上，此時d(i,j,k)=d(i,j,k-1)

最大二分匹配：

二分圖：一個所有回路長度均為偶數的無向圖，這樣的圖能夠將頂點分為兩部分，每部分內部各頂點間均不相連。

匹配：一個匹配是一個圖的一組邊的集合，圖的每個頂點之多連接匹配中的一條邊，如果沒有就是這個點未被匹配到。一個匹配相當于將圖中的若干頂點兩兩一對相連。

最大二分匹配：假設一個二分圖，頂點分為左，右兩側。每側頂點內部互不相連。左側每個頂點表示一個人，右側每個頂點表示一份工作。二分圖中每個連接人-工作的邊表示這個人有能力做這項工作。每項工作最多只需要一個人，每個人最多只能完成一項工作，如何分配工作(匹配)才能人盡其用呢？這就是一個求二分圖中最大匹配的問題。

最大流解決最大二分匹配問題：

在左側頂點的左邊加入源點，右側頂點的右邊加入匯點，連接源點-左側各點-右側各點-匯點的各邊賦予1的容量，于是就構造出了一個流網絡。由于各邊容量均為1，那么使得此流網絡形成最大流的方案，也就是原二分圖的最大匹配了。