1、課時1圖的實現方式與核心算法圖的實現方式圖的拓撲排序拓撲排序的實現方式圖的最短路徑總口課時15圖的實現方式鄰接矩陣法鄰接鏈表法圖的實現方式鄰接矩陣法基本思想是開一個超大的數組V0V1V2V4V30123401234destinationsource圖的實現方式234destination0123410010221224333鄰接鏈表法核心思想是把每一個節點所指向的點存儲起來sourceV00V1V2V4V3圖的拓撲排序指的是對于一個有向無環圖來說，排序所有的節點使得對于從節點 u 到節點 v 的每個有向邊 uv，u 在排序中都在 v 之前什么是拓撲排序呢圖的拓撲排序超市番茄買洗洗好的番茄切切好

2、的番茄雞蛋打散打好的雞蛋炒油、油番茄炒蛋、一個合法的拓撲排序必須使得被依賴的任務首先完成圖的拓撲排序為什么拓撲排序只適用于有向無環圖呢互聯網人實戰大學圖的拓撲排序先有雞還是先有蛋 （Chicken Egg Dilemma）是一個無法被拓撲排序的有環圖 因為雞依賴于蛋，蛋又依賴于雞你無法把雞排在蛋前面，也不能把蛋排在雞的前面圖的拓撲排序這里面隱含的一個有向無環圖就是錢指向了你想做的事情那么我們就很容易的得出一個合理的拓撲排序，要把錢排在你想做的事情之前拓撲排序的實現方式有向圖的入度指的是終止于一個節點的邊的數量有向圖的出度指的是始于一個節點的邊的數量ABCD拓撲排序的實現方式卡恩于 1962 年

3、提出的算法，其實是貪婪算法的一種形式簡單來說就是：假設 L 是存放口果的列表，我們先找到那些入度為零的節點把這些節點放到 L 中，因為這些節點沒有任何的父節點然后把與這些節點相連的邊從圖中去掉，再尋找圖中入度為零的節點對于新找到的這些入度為零的節點來說他們的父節點都已經在 L 中了，所以也可以放入 L重復上述操作，直到找不到入度為零的節點如果此時 L 中的元素個數和節點總數相同，則說明排序完成如果 L 中的元素個數和節點總數不同，則說明原圖中存在環，無法進行拓撲排序拓撲排序的實現方式卡恩算法L Empty list that will contain the sorted elementsS

4、Set of all nodes with no incoming edgewhile S is non-empty do remove a node n from S add n to tail of Lfor each node m with an edge e from n to m doremove edge e from the graphif m has no other incoming edges then insert m into Sif graph has edges thenreturn error(graph has at least one cycle) elser

5、eturn L(a topologically sorted order)圖的最短路徑在一個有權重的圖中，找到兩個點之間權重之和最短的路徑124359188201215圖的最短路徑怎樣讓計算機找到最短路徑呢便是大名鼎鼎的 Dijkstra 算法圖的最短路徑最經典的 Dijkstra 算法原始版本僅適用于找到兩個固定節點之間的最短路徑后來更常見的變體固定了一個節點作為涌節點然后找到該節點到圖中所有其他節點的最短路徑從而產生一個最短路徑樹圖的最短路徑這個算法是通過為每個節點 v 保留當前為止所找到的從 s 到 v 的最短路徑來工作的初始時：原點 s 的路徑權重被賦為 0（即原點的實際最短路徑 = 0）同時把所有其他節點的路徑長度設為無窮大，即表示我們不知道任何通向這些節點的路徑 口束時：dv 中存儲的便是從 s 到 v 的最短路徑，或者如果