SQL 實作最短路徑演算法：好友關聯鏈查詢實戰

在社交網路場景中，需找出兩用戶間最短的好友介紹鏈（如六度人脈）。本文展示如何在 SQL Server 中使用暫存表與迴圈，實作廣度優先搜尋（BFS）演算法，找出任意兩點間的最短路徑。

問題定義

• 資料：好友關係表，每筆記錄包含用戶 ID 與其好友清單（逗點分隔字串）。
• 目標：給定起點 @start 與終點 @end，找出經過最少中介節點的路徑。
• 限制：單次查詢只能取得直接好友。

資料範例

5  -> 1, 30, 3
7  -> 9, 5, 8
11 -> 7, 5, 30
...（其餘略）

5 到 7 的最短路徑：5 → 11 → 7（2 步），而非 5 → 30 → 21 → 7（3 步）。

T-SQL 實作 (BFS 迭代法)

DECLARE @t TABLE (id INT, f_id VARCHAR(20));
INSERT INTO @t VALUES
(5,'1,7,30,3'), (7,'11,21,9,5,8'), (11,'7,21,30'),
(21,'7,11,30,66'), (30,'5,11,21,88,99');

DECLARE @start INT = 5, @end INT = 11, @count INT = 0;
DECLARE @tmp TABLE (id INT, f_id VARCHAR(20), step INT);
INSERT INTO @tmp SELECT @start, '', @count;

WHILE @end NOT IN (SELECT id FROM @tmp)
BEGIN
    SET @count = @count + 1;
    INSERT INTO @tmp
    SELECT DISTINCT a.id, a.f_id, @count
    FROM @t a, @tmp b
    WHERE CHARINDEX(RTRIM(b.id), a.f_id) > 0
      AND a.id NOT IN (SELECT id FROM @tmp);
END

-- 回溯重建路徑
DECLARE @result VARCHAR(100) = CAST(@count AS VARCHAR) + ':' + CAST(@end AS VARCHAR);
WHILE @count > 1
BEGIN
    SET @count = @count - 1;
    SELECT TOP 1 @end = id FROM @tmp
    WHERE step = @count AND CHARINDEX(RTRIM(@end), f_id) > 0;
    SET @result = CAST(@count AS VARCHAR) + ':' + CAST(@end AS VARCHAR) + '/' + @result;
END
SET @result = '0:' + CAST(@start AS VARCHAR) + '/' + @result;
SELECT @result; -- 輸出: 0:5/1:7/2:11

關鍵技巧說明

1. 雙向關聯： 範例資料已將好友關係雙向化（A 在 B 清單，B 也在 A 清單），確保 BFS 能正確遍歷。
2. CHARINDEX 搜尋： 利用字串搜尋判斷好友關係，適用於逗點分隔格式；大量資料建議正規化為關聯表。
3. 步數記錄與回溯： @tmp 記錄每個節點被發現的步數，最後反向查找上一層相連節點重建路徑。

效能與擴展建議

• 好友關係表應正規化為 (user_id, friend_id) 兩欄，建立索引，避免字串搜尋效能瓶頸。
• 大型圖形建議使用圖資料庫（如 Neo4j）或 SQL Server 2017+ 內建 GRAPH 功能。
• 可將演算法封裝為預存程序或表值函數，供應用層呼叫。