小編精選 - 技術文章翻譯 · 08月15日

你距離 Pedro Pascal 還差幾次人脈介紹？圖搜尋的實用入門

我前陣子在看《曼達洛人》的時候突然意識到，我其實不認識 Pedro Pascal，光是這件事本身就已經很悲傷了。

但也許我認識某個人，某個人又認識某個人，某個人又認識某個人，……，而這些人之間存在一條有限的介紹鏈，能把我和他連起來。所以今天我們要解的電腦科學重要問題是：到底需要幾次介紹，才能認識他？

圖片說明

我們不小心發明出一個圖論問題了！

把你的社交生活變成一張圖

想像地球上的每個人都是一個節點，而兩個人之間的任何關係或熟識關係都是一條邊：

Alexandra ── Maria ── Sofia ── Pedro
    │
    └── John ── Elena ── Carlos

這是一張無權重、無向圖。

無權重表示每個連結的計算方式都一樣。我們不在乎 Maria 是 Sofia 最好的朋友，還是她只是在咖啡廳見過一次的人。
無向表示關係是雙向的：如果 Alexandra 認識 Maria，那 Maria 也認識 Alexandra。

如果把原始問題裡那些多餘修飾拿掉，它其實就從「我要怎麼認識 Pedro Pascal？」變成了「給定一張無權重圖，節點 A 和節點 B 之間的最短路徑是什麼？」；如果你熟悉樹或圖，這聽起來就很像 BFS（廣度優先搜尋）。

在程式中，表示這類資料最簡單的方法是鄰接串列：

const graph = {
  Alexandra: ["Maria", "John"],
  Maria: ["Alexandra", "Sofia"],
  Sofia: ["Maria", "Pedro"],
  Pedro: ["Sofia"],
  John: ["Alexandra", "Elena"],
  Elena: ["John", "Carlos"],
  Carlos: ["Elena"],
};

把我們的幻想變成演算法

很遺憾，對著虛空大喊「有人認識 PEDRO PASCAL 嗎？」並不是一個演算法。它沒有順序、沒有記憶，也沒有停止條件。你如果只是隨便從一個人走到下一個人，挑看起來有趣的人繼續找，很容易變成這樣：

Alexandra → Maria → Sofia → Maria → Sofia → Maria → ...

因為這張圖是無向的，Maria 會連回 Sofia，Sofia 也會連回 Maria。如果不記住我們已經見過誰，就沒有任何東西能阻止我們永遠重複遇到同樣的人。

所以我們基本上需要兩件事：

一個決定探索順序的規則。
一種記住已經拜訪過誰的方法。

這就是佇列和已訪集合派上用場的地方。

廣度優先搜尋解釋

找最短路徑的關鍵觀察是：先檢查距離 1 個連結的人，再去檢查距離 2 個連結的人。這就是廣度優先搜尋，它會把圖整理成一層一層的結構：

第 0 層      Alexandra
                  │
           ┌──────┴──────┐
第 1 層     Maria          John
            │              │
第 2 層     Sofia          Elena
            │
第 3 層     PEDRO 🎉

BFS 會先檢查我所有直接朋友（第 1 層），如果 Pedro 不在那裡（🥲），再檢查我直接朋友的直接朋友（第 2 層），以此類推。一旦找到 Pedro，就知道這一定是最短可能路徑，因為所有更短的路徑都已經檢查過了。

把一切組合起來


function introductionsAway(graph, start, target) {
  if (start === target) return { degrees: 0, path: [start] };

  const visited = new Set([start]);
  const queue = [[start, [start]]]; 

  while (queue.length > 0) {
    const [person, path] = queue.shift();

    for (const friend of graph[person] || []) {
      if (visited.has(friend)) continue;
      if (friend === target) {
        return { degrees: path.length, path: [...path, friend] };
      }

      visited.add(friend);
      queue.push([friend, [...path, friend]]);
    }
  }

  return { degrees: -1, path: [] };
}

轉折：真實的人際關係並不相等

到目前為止，在我們的問題裡，認識某人是非黑即白的。但你我都知道那是謊言。以下兩者之間有天壤之別：

Maria 曾經在某個活動上站在 Pedro 身旁，和
Pedro？對啊，我們每週四都一起吃晚餐。

技術上來說，這兩者都算是關係，但實際上，其中一種對我的_任務_來說明顯有用得多。

Alexandra --2-- Maria --5-- Sofia --4-- Tessa --1-- Pedro

所以我們替每段關係指定一個介紹成本。親近的關係成本低，因為開口請人介紹很容易。薄弱的熟識關係成本高，因為……嗯，祝你好運。

BFS 不知道怎麼處理權重。對於加權圖，我們需要把注意力轉向Dijkstra 演算法。

Dijkstra 演算法，簡述

Dijkstra 演算法問的是稍微不同的問題：

「從 A 到 B 的最便宜路徑是什麼？」

它不是按照我們發現節點的順序來探索，而是優先處理目前從起點累積成本最低的節點。

這通常表示要把 BFS 的一般佇列換成優先佇列。

同一張圖，不同名詞

Pedro Pascal 這個情境很荒謬，我知道，但底層問題並不荒謬。只要改變節點和邊所代表的東西，同樣的概念就會到處出現。

領域	節點	邊	「最短路徑」回答什麼
社交圖	人	關係	「要幾次介紹才能認識 Pedro Pascal？」
地圖 / GPS	交叉路口	道路（以時間／距離加權）	「從 A 到 B 的最快路線是什麼？」
網頁爬蟲	網頁	超連結	「從這個頁面到那個頁面要點幾次？」
程式碼庫	模組／檔案	匯入／依賴	「如果我改這個檔案，會壞掉什麼？」
推薦系統	使用者或商品	相似度／互動強度	「對這個使用者來說，什麼最相關？」