新的一週，祝你開心！

好久沒分享面經了，今天來個大的---字節的後端實習二面，簡直就是八股盛宴，問的太多太全面了。

面經詳解

1. 數據庫的隔離級別有哪些？

數據庫事務隔離級別主要分為四種，從低到高依次為：

1. 讀未提交（Read Uncommitted）

   • 允許事務讀取其他事務未提交的數據，可能導致髒讀、不可重複讀和幻讀。

2. 讀已提交（Read Committed）

   • 只能讀取其他事務已提交的數據，避免髒讀，但可能出現不可重複讀和幻讀。
   • 是 Oracle 和 SQL Server 的默認級別。

3. 可重複讀（Repeatable Read）

   • 確保同一事務內多次讀取同一數據結果一致，避免髒讀和不可重複讀，但可能發生幻讀。
   • 是 MySQL InnoDB 的默認級別。

4. 串行化（Serializable）

   • 最高隔離級別，強制事務串行執行，避免所有併發問題（髒讀、不可重複讀、幻讀），但性能開銷最大。

對比總結：

2. 可重複讀隔離級別是通過什麼機制來實現的？

可重複讀隔離級別通過 MVCC（多版本併發控制） 和 鎖機制 實現：

1. MVCC：

   • Read View：事務啓動時創建數據快照，後續所有讀操作基於此快照，確保數據一致性。
   • Undo Log：存儲數據的歷史版本。事務讀取數據時，通過版本鏈找到符合快照可見性的版本。

2. 鎖機制：

   • 行級鎖：更新數據時加鎖，防止其他事務修改當前行。
   • 間隙鎖（Gap Lock）：鎖定索引範圍內的間隙，防止其他事務插入新數據（解決幻讀）。

示例：事務 A 啓動後讀取賬户餘額為 1000 元，即使事務 B 修改餘額並提交，事務 A 再次讀取仍為 1000 元。

3. 説明 MVCC（多版本併發控制）的具體實現流程

MVCC 的核心是通過數據多版本實現讀寫併發控制，流程如下：

1. 隱藏字段：

   • 每行數據包含 DB_TRX_ID（最近修改的事務 ID）和 DB_ROLL_PTR（指向 Undo Log 的回滾指針）。

2. Read View 生成：

   • 事務首次讀操作時創建 Read View，記錄當前活躍事務 ID 列表，用於判斷數據版本的可見性。

3. 數據讀取流程：

   • 根據數據行的DB_TRX_ID與 Read View 對比：

     • 若 DB_TRX_ID 小於 Read View 中最小活躍 ID，説明數據已提交，可見。
     • 若 DB_TRX_ID 在活躍事務 ID 列表內，説明數據未提交，不可見，需沿 DB_ROLL_PTR 在 Undo Log 中查找舊版本。

4. 寫操作流程：

   • 更新數據時，將舊數據拷貝到 Undo Log，新數據覆蓋原行並更新 DB_TRX_ID。

5. 版本清理：

   • 後台線程定期清理無活躍事務引用的舊版本數據（Purge 機制）。

案例：事務 A（ID=101）更新數據時，事務 B（ID=102）通過 Read View 讀取 Undo Log 中的舊版本，避免髒讀。

4. 不可重複讀與幻讀的區別是什麼？

5. mysql的日誌都有哪些，用途？

6. redo log的實現？

Redo Log 通過 Write-Ahead Logging（WAL） 機制實現事務持久性：

1. 物理結構：

   • 固定大小的循環文件（如 ib_logfile0, ib_logfile1），寫滿後覆蓋舊數據。
   • Write Pos：當前寫入位置；Checkpoint：已刷盤的數據位置。

2. 寫入流程：

   • 事務修改數據前，先寫 Redo Log Buffer（內存）→ 提交時刷盤到 Redo Log 文件。

   • 刷盤策略由

     innodb_flush_log_at_trx_commit

     控制：

     • 1（默認）：每次提交同步刷盤（強一致）
     • 0 或 2：異步刷盤（可能丟失 1 秒數據）。

3. 崩潰恢復：

   • 重啓後根據 Redo Log 中的 LSN（日誌序列號）恢復未刷盤的數據。

優化點：順序 I/O 寫日誌（性能高於隨機寫數據頁）。

7. binlog的格式有哪幾種？

8. Redis中的漏桶算法

漏桶算法通過固定速率處理請求，控制流量：

1. 原理：

   • 請求如水流入桶（容量固定），桶底以恆定速率漏水（處理請求）。桶滿則拒絕新請求。

2. Redis 實現：

   • 數據結構：用 INCR 統計請求數，EXPIRE 重置桶計數。

   • 關鍵參數：

     • capacity：桶容量（最大請求數）
     • leak_rate：漏水速率（每秒處理數）。

3. 桶滿策略：

   • 直接拒絕：返回錯誤（簡單但體驗差）。
   • 排隊等待：請求入隊列，桶空閒時處理（需額外維護隊列）。

9. redis的持久化機制

Redis 提供兩種持久化方式：

1. RDB（快照）：

   • 原理：定時 fork 子進程生成內存數據快照（二進制文件 dump.rdb）。
   • 優點：恢復速度快，文件緊湊適合備份。
   • 缺點：可能丟失最後一次快照後的數據（默認間隔 5 分鐘）。

2. AOF（追加文件）：

   • 原理：記錄每個寫操作命令（文本文件），重啓時重放命令恢復數據。

   • 刷盤策略：

     • always：每次寫操作刷盤（安全但性能差）
     • everysec：每秒刷盤（默認，最多丟 1 秒數據）。

3. 混合持久化（Redis 4.0+）：

   • AOF 文件包含 RDB 頭 + 增量操作，兼顧恢復速度和數據安全。

10. redis的數據類型

11. 講一下Go語言的垃圾回收機制

Go語言的垃圾回收（GC）採用併發標記-清除算法，結合三色標記法和寫屏障技術，旨在減少停頓時間（STW）並支持高併發場景。其核心機制如下：

1. 三色標記法：

   • 白色對象：未被訪問的對象（待回收）。
   • 灰色對象：已訪問但引用的對象未完全掃描。
   • 黑色對象：已訪問且所有引用已掃描（存活對象）。
     標記階段從根對象（全局變量、棧變量等）開始，遞歸遍歷可達對象並標記為灰色，逐步轉為黑色。

2. 併發與並行執行：

   • 併發標記：GC線程與用户程序併發運行，通過寫屏障（Write Barrier）記錄對象引用變化，防止漏標。
   • 並行清除：標記完成後，清理白色對象的內存（與程序並行）。

3. 觸發條件：

   • 內存閾值：當堆內存達到上次GC後存活對象的2倍（默認GOGC=100%），自動觸發。
   • 手動觸發：調用runtime.GC()。
   • 系統內存壓力：操作系統要求釋放內存時。

4. 分代收集優化：

   • 對象分為新生代（頻繁回收）和老生代（較少回收），優先掃描新生代，減少全局遍歷開銷。

5. 性能優化建議：

   • 減少堆分配：複用對象（如sync.Pool）。
   • 避免小對象頻繁分配：使用數組替代切片或預分配內存。

GC對程序的影響：最大停頓時間通常控制在10ms以內，但高頻分配仍可能導致延遲升高。

12. slice的擴容機制

Go中slice的擴容通過append觸發，底層調用runtime.growslice函數，策略兼顧效率與內存利用率：

1. 擴容時機：

   • 當len(slice) + 新增元素數 > cap(slice)時觸發擴容。

2. 擴容策略（Go 1.18+）：

   • 容量 < 256：雙倍擴容（newcap = oldcap * 2）。
   • 容量 ≥ 256：按公式newcap = oldcap + (oldcap + 3*256) / 4逐步增加（約1.25倍），避免過度浪費。
   • 特殊處理：若擴容後仍不足，直接採用所需容量。

3. 內存對齊：

   • 計算newcap後，根據元素大小向上取整到內存頁大小（如int類型按8字節對齊）。

4. 數據遷移：

   • 分配新內存空間，拷貝舊數據到新數組，原數組由GC回收。

示例：

s := []int{1, 2}  
s = append(s, 3, 4)  // 原cap=2，擴容後cap=4（2*2）

優化建議：預分配容量（make([]int, 0, 100)）以減少擴容開銷。

13. Go 協程調度模型（GMP）是什麼？

GMP是Go語言實現高併發的核心調度模型，包含三個組件：

1. G（Goroutine）：輕量級協程，初始棧2KB，由Go運行時管理。
2. M（Machine）：操作系統線程（內核線程），負責執行G的代碼。
3. P（Processor）：邏輯處理器，維護本地G隊列（runq），數量默認為CPU核心數（可通過GOMAXPROCS調整）。

工作流程：

• G創建：go func()將G加入當前P的本地隊列；若隊列滿，則轉移一半G到全局隊列。

• M綁定P：M需綁定P才能執行G，從P的本地隊列獲取G；若本地隊列空，則：

  • 從全局隊列獲取一批G。
  • 從其他P的隊列竊取（Work Stealing） 一半G。

• 阻塞處理：

  • 系統調用：M解綁P，P被其他M接管繼續執行G。
  • 恢復後：M嘗試綁定空閒P執行原G，否則G加入全局隊列，M休眠。

優勢：

• 高併發：百萬級Goroutine可被少量M調度。
• 低延遲：協作式調度 + 搶佔機制（基於信號）減少長任務阻塞。

14. Channel 的底層實現和阻塞機制是怎樣的？

Channel的底層結構為hchan（源碼定義），核心機制如下：

type hchan struct {
    buf      unsafe.Pointer // 環形緩衝區
    qcount   uint           // 當前緩衝區元素數
    dataqsiz uint           // 緩衝區大小
    lock     mutex          // 互斥鎖
    sendq    waitq          // 發送等待隊列（sudog鏈表）
    recvq    waitq          // 接收等待隊列（sudog鏈表）
}

1. 阻塞條件：

   • 發送阻塞：無緩衝Channel無接收者，或緩衝Channel緩衝區滿（qcount == dataqsiz）。
   • 接收阻塞：無緩衝Channel無發送者，或緩衝Channel緩衝區空（qcount == 0）。

2. 阻塞處理：

   • 阻塞的G被封裝為sudog加入sendq或recvq隊列，M切出執行其他G。
   • 當條件滿足時（如新數據到達），喚醒隊列中第一個等待的G（FIFO順序）。

3. 直傳優化：

   • 若發送時recvq非空，數據直接拷貝給等待的接收者，避免經過緩衝區。

示例：

ch := make(chan int, 2)
ch <- 1  // 寫入緩衝區
ch <- 2  // 緩衝區滿，再次寫入會阻塞

15. defer 關鍵字的執行順序

defer延遲執行函數，規則如下：

1. 執行順序：

   • 多個defer按後進先出（LIFO） 順序執行（類似棧）。

     defer fmt.Print("A")  
     defer fmt.Print("B")  // 先輸出"B"，再輸出"A"

2. 參數求值時機：

   • defer的參數在聲明時立即求值，而非執行時。

     i := 0
     defer fmt.Print(i)  // 輸出0（i的值在聲明時確定）
     i = 1

3. 執行時機：

   • 在函數返回前執行（包括return賦值後、函數結束前），即使發生panic也會執行。

4. 常見陷阱：

   • 循環中的defer：若在循環內使用defer，可能因延遲執行導致資源未及時釋放（如文件句柄）。建議改用匿名函數包裹。
   • 返回值修改：若defer修改命名的返回值，會影響最終結果。

應用場景：資源釋放（文件關閉）、錯誤恢復（recover）等。

16. 説下TCP和UDP的區別

TCP與UDP是傳輸層協議的核心區別在於可靠性與連接機制：

| 特性 | TCP | UDP |
|----------------|-----------------------------------|----------------------------------|
| 連接性 | 面向連接（三次握手） | 無連接 |
| 可靠性 | 可靠（確認重傳、有序） | 不可靠（可能丟包、亂序） |
| 數據格式 | 字節流（無邊界） | 數據報（有邊界） |
| 頭部開銷 | 較大（20-60字節） | 較小（8字節） |
| 速度 | 慢（擁塞控制、握手開銷） | 快（無控制開銷） |
| 應用場景 | 文件傳輸、HTTP、郵件 | 視頻流、DNS、實時遊戲 |

關鍵差異解釋：

• 有序性：TCP通過序列號保證數據順序；UDP不保證。
• 流量控制：TCP使用滑動窗口；UDP無控制機制。
• 適用性：TCP適合需高可靠性的場景；UDP適合低延遲容忍丟包的場景。

17. TCP具體採用了哪些機制來保證其可靠性

TCP通過以下6大機制確保數據傳輸可靠：

1. 序列號與確認應答（ACK）：

   • 每個數據包分配唯一序列號，接收方返回ACK確認收到數據（累積確認）。

2. 超時重傳：

   • 發送方啓動定時器（RTO動態計算），未收到ACK則重傳數據。

3. 流量控制（滑動窗口）：

   • 接收方通過Window字段告知剩餘緩衝區大小，發送方據此調整發送速率（避免淹沒接收方）。

4. 擁塞控制：

   • 慢啓動：初始窗口小，每RTT翻倍。
   • 擁塞避免：窗口達到閾值後線性增長。
   • 快重傳/快恢復：收到3個重複ACK立即重傳，避免等待超時。

5. 校驗和：

   • 16位校驗和驗證數據完整性，錯誤則丟棄包並觸發重傳。

6. 連接管理：

   • 三次握手：建立可靠連接（同步序列號）。
   • 四次揮手：確保雙方數據發送完成後再關閉連接。

總結：TCP通過上述機制實現無丟失、無重複、無錯誤、有序的數據傳輸。

18. HTTP協議的不同版本對比

| 版本 | 核心改進 | 主要特性 |
|-------------|---------------------------------------------|----------------------------------------------------------------------------|
| HTTP/1.0 | 基礎版本 | 短連接（每次請求新建TCP）、無Host頭、無管道化 |
| HTTP/1.1 | 解決1.0性能瓶頸 | 持久連接（Keep-Alive）、Host頭（支持虛擬主機）、管道化（但隊頭阻塞未解決） |
| HTTP/2 | 性能優化 | 二進制分幀、頭部壓縮（HPACK）、多路複用（解決隊頭阻塞）、服務器推送 |
| HTTP/3 | 基於QUIC協議（UDP） | 0-RTT快速連接、傳輸層多路複用（徹底解決隊頭阻塞）、內置TLS 1.3加密 |

關鍵演進：

• HTTP/1.1 → HTTP/2：從文本到二進制協議，多路複用提升併發效率。
• HTTP/2 → HTTP/3：從TCP到QUIC（UDP），避免傳輸層隊頭阻塞，更適合高丟包網絡。

記憶口訣：

HTTP/1.1：持久連接省握手，Host區分虛擬節點。
HTTP/2：二部曲（二進制、頭部壓縮、亂序傳輸）。

19. 操作系統中的進程調度算法

操作系統的進程調度算法旨在高效分配CPU資源，核心算法包括：

1. 先來先服務（FCFS）：

   • 按就緒隊列順序執行，非搶佔式。
   • 缺點：長任務阻塞短任務（"護航效應"）。

2. 短作業優先（SJF）：

   • 優先執行預估運行時間短的進程。
   • 缺點：長任務可能飢餓。

3. 輪轉法（Round Robin, RR）：

   • 每個進程分配固定時間片（如10ms），超時後放回隊列尾部。
   • 優點：公平性強，適合分時系統。

4. 優先級調度：

   • 靜態/動態優先級（如高響應比優先：優先級 = (等待時間 + 執行時間) / 執行時間）。
   • 缺點：低優先級進程可能飢餓。

5. 多級反饋隊列（MLFQ）：

   • 多隊列（優先級遞減 + 時間片遞增），新進程加入最高優先級隊列。
   • 優勢：平衡響應時間與吞吐量，結合RR與優先級優點。

評價指標：吞吐量、週轉時間、響應時間、CPU利用率。

20. 用户態和內核態之間的區別

用户態和內核態是CPU特權級的兩種模式，核心區別如下：

| 維度 | 用户態 | 內核態 |
|----------------|------------------------------------------|----------------------------------------|
| 特權級別 | Ring 3（低特權） | Ring 0（高特權） |
| 內存訪問 | 僅限用户空間（不可訪問內核內存） | 可訪問全部內存空間 |
| 指令權限 | 禁止執行特權指令（如I/O操作、中斷管理） | 可執行所有指令 |
| 穩定性 | 進程崩潰不影響系統 | 內核崩潰導致系統宕機 |
| 性能開銷 | 常規代碼執行 | 系統調用需上下文切換（約1μs~10μs開銷） |

切換方式：

• 用户態 → 內核態：通過系統調用（如read()）、中斷或異常觸發。
• 內核態 → 用户態：系統調用返回前恢復用户態上下文。

示例：

read(file_fd, buffer, size);  // 系統調用，觸發切換至內核態

意義：隔離用户程序與內核，防止惡意操作破壞系統穩定性。

21. 怎麼從用户態切換到內核態

用户態切換到內核態主要通過以下三種方式觸發，核心機制是CPU特權級的轉換（從Ring 3切換到Ring 0）和上下文保存：

1. 系統調用（主動觸發）

   • 原理：用户進程通過調用操作系統提供的接口（如read()、write()）主動請求內核服務。
   • 步驟：
     ① 用户程序將系統調用號存入寄存器（如rax），參數存入rdi、rsi等寄存器。
     ② 執行syscall或int 80h指令，觸發軟中斷，CPU切換到內核態（Ring 0）。
     ③ 內核保存用户態上下文（RIP、RSP、RFLAGS等寄存器值）到內核棧，跳轉至中斷處理程序。

2. 異常（被動觸發）

   • 原理：用户程序執行時發生不可預知的錯誤（如除零、缺頁異常），CPU自動切換至內核態處理。

   • 示例：

     • 缺頁異常：進程訪問未分配的內存頁，觸發內核分配物理頁並更新頁表。
     • 處理流程：保存用户態上下文→執行異常處理程序→修復後返回用户態（若可恢復）。

3. 中斷（被動觸發）

   • 原理：外部設備（如磁盤、網卡）完成任務後發送中斷信號，強制CPU暫停當前指令並處理中斷。

   • 流程：

     • 設備中斷觸發，CPU保存用户態上下文，切換到內核態執行中斷處理程序（如磁盤I/O完成後的回調）。
     • 中斷處理結束，通過iret指令恢復用户態上下文。

切換的底層步驟：

1. 從進程描述符中獲取內核棧指針（ss0和esp0）。
2. 將用户態寄存器狀態（CS、EIP、EFLAGS等）壓入內核棧。
3. 加載中斷處理程序的入口地址到寄存器，執行內核代碼。

關鍵點：

• 系統調用是主動切換，異常和中斷是被動切換。
• 切換開銷：上下文保存與恢復耗時約1μs~10μs，頻繁切換影響性能。

22. 進程之間的通信方式

進程間通信（IPC）主要用於數據傳輸、資源共享或事件通知，分為以下五類：

| 方式 | 原理 | 適用場景 |
|----------------|--------------------------------------------------------------------------|----------------------------------|
| 管道（Pipe） | 單向數據流，基於內核緩衝區，匿名管道僅用於父子進程，命名管道（FIFO）支持無關進程。 | 命令行工具鏈（如ls \| grep） |
| 消息隊列 | 內核管理的消息鏈表，進程通過唯一標識符讀寫消息，支持異步通信。 | 解耦生產者與消費者（如日誌系統） |
| 共享內存 | 多個進程映射同一塊物理內存，直接讀寫數據，需配合同步機制（如信號量）。 | 高性能數據共享（如大型矩陣計算） |
| 信號量 | 計數器，控制多進程對共享資源的訪問（P/V操作），解決互斥與同步問題。 | 資源池管理（如數據庫連接池） |
| 套接字（Socket） | 跨網絡通信，支持TCP/UDP協議，適用於分佈式系統。 | 客户端-服務器模型（如Web請求） |

對比與選擇：

• 性能：共享內存 > 消息隊列 > 管道 > 套接字（本地通信）。
• 複雜度：套接字 > 共享內存 > 消息隊列 > 管道。

• 建議：

  • 父子進程協作：匿名管道。
  • 無關進程通信：命名管道或消息隊列。
  • 高頻數據交換：共享內存+信號量。

23. 進程之間同步的方式有哪些

進程同步解決資源競爭與執行順序問題，核心機制如下：

1. 信號量（Semaphore）

   • 原理：整數計數器，通過P()（等待）和V()（通知）操作控制資源訪問。

   • 類型：

     • 二進制信號量：值0/1，實現互斥鎖。
     • 計數信號量：限制資源數量（如線程池）。

2. 互斥鎖（Mutex）

   • 原理：二值鎖，同一時間僅一個進程持有鎖，其他進程阻塞等待。
   • 場景：保護臨界區（如共享文件寫入）。

3. 條件變量（Condition Variable）

   • 原理：與互斥鎖配合使用，當條件不滿足時阻塞進程，條件達成時喚醒（如pthread_cond_wait）。
   • 示例：生產者-消費者模型，緩衝區空時消費者等待。

4. 讀寫鎖（Read-Write Lock）

   • 原理：允許多個讀操作併發，寫操作獨佔資源。
   • 場景：讀多寫少（如數據庫查詢）。

5. 屏障（Barrier）

   • 原理：多個進程到達屏障點後同時繼續執行，用於並行計算同步。

同步問題的本質：

• 互斥：確保資源不被同時訪問（如打印機使用）。
• 同步：協調進程執行順序（如A進程輸出後B進程才能處理）。

24. 介紹一下單例模式

單例模式確保一個類僅有一個實例，並提供全局訪問點，常用於資源管理（如配置、線程池）。

實現方式：

1. 餓漢式：類加載時創建實例，線程安全但可能浪費內存。

   public class Singleton {  
       private static final Singleton instance = new Singleton();  
       private Singleton() {}  
       public static Singleton getInstance() { return instance; }  
   }  

2. 懶漢式（雙重檢查鎖）：首次調用時創建實例，避免資源浪費。

   public class Singleton {  
       private static volatile Singleton instance;  
       private Singleton() {}  
       public static Singleton getInstance() {  
           if (instance == null) {  
               synchronized (Singleton.class) {  
                   if (instance == null) instance = new Singleton();  
               }  
           }  
           return instance;  
       }  
   }  

特點：

• 優點：避免重複創建，節省內存；統一訪問入口。
• 缺點：需處理多線程安全問題；可能隱藏代碼依賴關係。

應用場景：

• 數據庫連接池（避免多次初始化連接）。
• 日誌管理器（全局唯一寫入點）。

25. 策略模式

策略模式定義一組算法，封裝每個算法使其可互換，讓算法獨立於客户端變化。

核心組件：

1. 策略接口（Strategy）：聲明算法方法（如execute()）。
2. 具體策略類（ConcreteStrategy）：實現不同算法（如支付寶支付、微信支付）。
3. 上下文類（Context）：持有策略引用，調用策略方法。

示例：支付系統

interface PaymentStrategy { void pay(int amount); }  
class AlipayStrategy implements PaymentStrategy {  
    public void pay(int amount) { /* 支付寶支付邏輯 */ }  
}  
class WeChatPayStrategy implements PaymentStrategy {  
    public void pay(int amount) { /* 微信支付邏輯 */ }  
}  
class ShoppingCart {  
    private PaymentStrategy strategy;  
    public void setStrategy(PaymentStrategy strategy) { this.strategy = strategy; }  
    public void checkout(int amount) { strategy.pay(amount); }  
}  

優勢：

• 靈活擴展：新增支付方式無需修改上下文。
• 解耦：算法與客户端分離，避免條件分支（如if-else）。

適用場景：

• 支付方式、排序算法等需動態切換的場景。
• 算法需獨立測試或複用。

26. 圖的遍歷算法有哪些，並簡要説明它們的特點

圖的遍歷分為兩類，特點對比如下：

| 算法 | 數據結構 | 遍歷順序 | 特點 | 應用場景 |
|------------------|--------------|------------------------|--------------------------------------------------------------------------|----------------------------|
| 深度優先搜索（DFS） | 棧（遞歸） | 深度優先，一條路徑到底 | 可能陷入深分支，空間複雜度O(V)（頂點數） | 拓撲排序、連通性檢測 |
| 廣度優先搜索（BFS） | 隊列 | 層次優先，按距離擴展 | 可求最短路徑（無權圖），空間複雜度O(V) | 最短路徑、社交網絡關係 |

關鍵差異：

• 路徑探索：DFS適合探索所有可能路徑（如迷宮求解），BFS適合最短路徑（如社交關係鏈）。
• 複雜度：時間複雜度均為O(V+E)（V為頂點數，E為邊數），但BFS空間開銷可能更大（隊列存儲）。

27. 介紹圖的廣度優先算法

廣度優先搜索（BFS）按層次遍歷圖，核心是隊列管理和層級擴散，確保先訪問的節點其鄰接點優先訪問。

算法流程：

1. 初始化：

   • 將起始節點標記為已訪問，加入隊列。

2. 迭代訪問：

   • 隊首節點出隊，訪問其所有未訪問鄰接節點，標記併入隊。
   • 重複直至隊列為空。

特點：

• 最短路徑：在無權圖中，BFS首次訪問到目標節點的路徑一定是最短路徑。
• 層級性：隊列中節點按距離起始點的層級排序。

應用場景：

• 網絡爬蟲（按鏈接深度抓取）。
• 社交網絡好友推薦（N度關係）。

性能優化：稀疏圖使用鄰接表存儲，避免鄰接矩陣的O(V²)遍歷開銷。

歡迎關注 ❤

我們搞了一個免費的面試真題共享羣，互通有無，一起刷題進步。

沒準能讓你能刷到自己意向公司的最新面試題呢。

感興趣的朋友們可以加我微信：wangzhongyang1993，備註：面試羣。