743. Network Delay Time

輸入：int[][] times times[i]= new int[]{v,u,w} 表示從節(jié)點v到節(jié)點u需要時間w。注意這里是有向圖。
　　 int N 節(jié)點總數(shù)。
　　 int k 起始節(jié)點

輸出：從節(jié)點k到其他各個節(jié)點的最短路徑和。如果有一個節(jié)點不能達(dá)到則返回-1。

分析：從題目描述直觀地看到求一個節(jié)點到其他各個節(jié)點的最短路徑和。適用于迪杰斯特拉算法（Dijkstra’s Algorithm ）。
DijStra’s Algorithm描述
　　迪杰斯特拉算法是屬于圖論中的一個算法。
　　定義一個int[] dist 存儲各個節(jié)點到k節(jié)點的最小路徑長度。數(shù)組初始化為Integer.MAX_VALUE。定義一個Set seen，保存已經(jīng)處理過的節(jié)點。定義一個最小堆minHeap，堆頂存放的是當(dāng)前情況下距離k點最近的點。初始化放入K,0。
　　計算過程：
　　1 在minHeap不為空的情況下，取得堆頂元素[v,dis]。
　　2 如果v已經(jīng)在seen中出現(xiàn)，則已經(jīng)處理過，跳轉(zhuǎn)到1。
　　3 如果v不在seen中，先設(shè)置dist[v]=dis，將節(jié)點v加入到seen。其次檢查v可以達(dá)到的節(jié)點列表list。對每個節(jié)點u判斷dist[u] 與dist[v]+times[v][u][2]的大小關(guān)系。大于，則v節(jié)點可能是到達(dá)u節(jié)點的一條最短路徑，將[u,dist[v]+times[v][u][2]]入minHeap。否則不做處理。跳轉(zhuǎn)到1。
　　4 直到所有節(jié)點都處理完成。
　　這個過程對于節(jié)點v，做處理；接著將未處理過的鄰接點u放入隊列中等待處理。典型的BFS思路。
　　當(dāng)我把代碼寫完用測試用例測試。[[2,1,1],[2,3,1],[3,4,1]]，4，2。發(fā)現(xiàn)標(biāo)準(zhǔn)答案是2，而我出的結(jié)果是4。我在想：節(jié)點2到節(jié)點1耗時1；節(jié)點2到節(jié)點3耗時1；節(jié)點3到節(jié)點4耗時1，所以節(jié)點2到節(jié)點4耗時2。1+1+2=4沒有問題呀。想想，解釋只可能是從節(jié)點2發(fā)出的節(jié)點可以同時達(dá)到節(jié)點1和節(jié)點3，所以耗時1。節(jié)點3到節(jié)點4耗時1。所以總耗時1+1=2。節(jié)點1，節(jié)點3是節(jié)點2的臨節(jié)點，可以同時發(fā)送。應(yīng)該是這樣解釋吧。處理的技巧就是從dist數(shù)組中找最大值，當(dāng)然最大值不能是Integer.MAX_VALUE。
代碼
感悟：Dijstra’s 算法可以用兩個for循環(huán)實現(xiàn)，也可以借助最小堆。代碼實現(xiàn)的一些細(xì)節(jié)也影響執(zhí)行時間。

111 Minimum Depth of Binary Tree

輸入：二叉樹
輸出：二叉樹的最小深度，也就是根節(jié)點到葉子結(jié)點的最短路徑。
分析：
　對于node3來說，如果左右子樹都為null，那直接得到答案1。如果左右子樹都不為null，那就是取左子樹最小深度和右子樹最小深度的最小值+1。如果左右子樹一個為null（我一開始忘記分析了），那么就是不為null的子樹的最小深度+1。
　用DFS遞歸實現(xiàn)最直白。

分析2:
　我們也可以把樹看做3層，哪層最先有葉子節(jié)點，那最小深度就在這里了。上圖中在第2層就有葉子節(jié)點，所以最小深度是2。
　雖然是easy題目，但是思路明顯比以前好多了，知道為什么對。
代碼

總結(jié)

以上是生活随笔為你收集整理的Breadth-first Search(广度优先搜索)专题2的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。