浙江大學-數據結構-應用實例：六度空間-6.4.1

給任何一個節點，我們想要找的就是說，跟它直接有邊相連的，直接認識的人數一下有多少個，這些人肯定是滿足六度空間理論的，然後它的這些朋友，直接認識，但是他又不認識的，是第二圈人，然後再去找第三圈，第四圈，所以我們基本上的思路是一個廣度優先搜索的思路，

首先我們是對每一個人進行廣度優先搜索，在搜索的過程中，我們不是為了搜索而搜索的，我們是為了數一下，到底有多少人滿足條件的，所以在搜索的過程中我們要累計訪問的節點數，但是我們是不是要一直遍歷所有的結點，我們有這個必要嗎?沒有這個必要，我們要驗證的是6度空間，所以我要記錄的是一個層數，僅僅計算6層以內的節點數就可以了，所以這個問題最難的一點是，在於怎麼處理這個層數的問題，其實SDS的總體解決思路是很簡單的，對圖裡面的每一個節點進行一次廣度優先搜索，當然這個廣度優先搜索我們之前的模板是一個void函數，它其實是不返回任何東西，在這裡面我們要求返回一個count,就是BFS以後，一共數出來多少人，把這個數字返回來，那麼我們需要輸出的是，我們可以在6步以內訪問到的結點數占人群總數的百分比，這是我們的一個Output,關鍵在裡面怎麼去實現BFS,這是我們最原始的BFS的模板，回憶一下我們是怎麼做的，我們先從根結點出發，把visited[V] = true,把它放到隊列里，然後就進入了廣度優先的遍歷過程，每一次遍歷我們從Q裡面Dequeue一個元素，然後把它的每一個鄰接點，只要沒有被訪問過的，我們訪問它一下，然後把它壓到隊列里，這就是BFS的過程，那麼在搜索過程中我們需要累計訪問的結點數，怎麼累計呢？每一次在visited[V] = true的時候，其實就可以在後面加一個count,

那麼在原始的結點進去的時候，count等於1，然後往下開始累計，每一次Enqueue的時候就count++一下，當然BFS應該返回一個int,到最後的時候應該return count

所以返回值要改為int,

但是還有一個很難的問題，我要怎麼記錄這個層數呢？在我們的教科書里其實給了SDS實現的源代碼，在源代碼裡面它是給了一個解決方案，給圖裡面的每一個結點V,加了一個屬性，叫做層，叫做layer,於是每一次我要Enqueue(W, Q）之前，我先把這個W的layer記一下，是它的V,也就是它上面一層那個layer加1，然後我再把它Enqueue放到隊列里，那麼彈出來的時候我要檢查一下，它是不是到6層了，到6層的話我就不再往下做了，這是一種解決方案，但是這種解決方案的問題是我對圖裡面的每一個節點都多加了一個整數，這樣我多佔的空間是O(n)數量級的，如果我有n個結點的話，有沒有一種更好的方法呢？接下來我們來看一種不一樣的解決方案，這是我們原來的BFS，加了count的

這裡留了一些空間，就是為了解決層數用的，我到底要怎麼做呢？我在這裡加了兩個變數，一個叫做level,一個叫做last,

level記得是當前這個頂點，它所在的層數，last指的是當前這一層我訪問的最後一個結點是誰？比如說我們有這麼一副圖

我從中心頂點1開始，然後我的層序遍歷就是2，3，4，5，6，7，然後從2開始8，9，10一直到19，那麼這個level最初的時候，指的是1的level,它是不算的，所以它是level 0,然後last的初始值也是等於它，因為它是它這一層的第一個，也是最後一個，當我們這個層序遍歷進入while循環的時候，我們在做什麼事情呢？我在把1的直接相連的鄰接點一個一個的壓到隊列裡面去

最後一個進隊列的是這個7,然後更新的時候就應該把last更新成7

那麼一個很重要的問題就是什麼時候我們知道這個last應該更新成誰呢？那麼我們還需要另外一個變數叫做tail,這個tail應該指向的是下一層進隊列的最後一個結點，

我們怎麼做呢？其實是在每一個鄰接點W，進隊列的時候，我都讓tail指向這個W,也就是說tail一開始的時候會指向8，指向9，指向10，指向11，指向12，以此類推，最後它會指向19，我們怎麼知道19是最後一個呢？那就是噹噹前彈出來的V是等於前一步的last的時候，我們知道這個tail指向的這個結點一定是下一層的最後一個結點，所以我們在這要加一個判斷，如果彈出來的V是等於last的話，那麼我們知道level++，然後我們更新這個last,讓last等於tail,就又往外推了一層，

什麼時候停止呢？我們要檢查一下什麼時候level等於6了，我們就不做了，跳出來，return count,