• 博客主頁：誓則盟約
• 系列專欄：IT競賽 專欄
• 關注博主，后期持續更新系列文章
• 如果有錯誤感謝請大家批評指出，及時修改
• 感謝大家點贊👍收藏?評論??

---

1. 圖的定義和基本概念：

   • 圖（Graph）是一種由頂點（Vertex，也稱為節點 Node）和邊（Edge）組成的數據結構。

     頂點是圖中的基本元素，表示某個對象或實體。頂點可以用一個標識符來表示，例如一個數字或一個字符串。

     邊則用于連接圖中的頂點，表示頂點之間的關系。邊可以是有向的，也可以是無向的。

     在無向圖中，邊沒有方向，頂點之間的連接是雙向的。如果頂點?v?和頂點?w?之間有一條無向邊，那么我們可以說?v?和?w?是相鄰的，并且從?v?可以到達?w?，從?w?也可以到達?v?。

     在有向圖中，邊是有方向的，從一個頂點指向另一個頂點。如果有一條從頂點?u?到頂點?v?的有向邊，我們表示為?(u, v)?，那么可以說?u?是?v?的前驅，v?是?u?的后繼。從?u?可以沿著邊到達?v?，但從?v?不一定能直接到達?u?，除非存在另一條從?v?到?u?的有向邊。

有向圖（Directed Graph）和無向圖（Undirected Graph）是圖的兩種主要類型，它們的主要區別在于邊的方向性：

無向圖：
?

• 邊的特征：在無向圖中，邊沒有方向，頂點之間的連接是雙向的。如果存在一條連接頂點?u?和頂點?v?的邊，那么既可以從?u?到達?v，也可以從?v?到達?u?。
• 表示方法：通常用一對頂點來表示一條邊，例如?(u, v)?表示頂點?u?和頂點?v?之間有一條邊。由于邊是無向的，所以?(u, v)?和?(v, u)?表示的是同一條邊。
• 應用場景：適用于表示頂點之間對稱的關系，比如朋友關系（如果 A 是 B 的朋友，那么 B 也是 A 的朋友）。
• ?

  有向圖：

• 邊的特征：在有向圖中，邊是有方向的，從一個頂點指向另一個頂點。如果存在一條從頂點?u?到頂點?v?的有向邊，那么只能從?u?沿著邊的方向到達?v，而不能從?v?沿著這條邊到達?u?，除非存在另一條從?v?到?u?的有向邊。
• 表示方法：用一個有序對來表示一條有向邊，例如?(u, v)?表示從頂點?u?到頂點?v?的有向邊，與?(v, u)?是不同的邊。
• 應用場景：常用于表示具有方向性的關系，比如網頁中的鏈接（從一個網頁指向另一個網頁）、任務之間的依賴關系（一個任務必須在另一個任務完成后才能開始）等。

圖的表示方法：

• 鄰接矩陣是用一個二維矩陣來表示圖的連接關系。矩陣的行和列都對應圖的頂點。若頂點和頂點之間有邊相連，矩陣中的值為（或邊的權值），否則為。這種表示法簡單直觀，適用于頂點數較少的圖。

• 鄰接表是一種用于表示圖的常見數據結構。對于圖中的每個頂點，使用一個鏈表或數組來存儲與其相鄰的頂點。

  ?

  具體來說，為圖中的每個頂點創建一個鏈表（或動態數組）。鏈表（或數組）中的每個節點表示與該頂點相鄰的一個頂點，并可以選擇性地包含邊的權值等信息。

圖的遍歷算法：

????????深度優先搜索（Depth-First Search，DFS）是一種圖（或者樹）的遍歷算法。它從起始節點開始，沿著一條路徑盡可能深地訪問節點，直到無法繼續或達到目標節點，然后回溯到上一個未完全探索的節點，繼續探索其他路徑。

DFS 的原理：

• 選擇一個起始節點并將其標記為已訪問。
• 對于該節點的未訪問相鄰節點，選擇一個進行遞歸訪問。
• 重復上述過程，直到沒有未訪問的相鄰節點，然后回溯。

DFS 的實現步驟：

1. 訪問起始節點，并將其標記為已訪問。
2. 對于起始節點的每個未訪問相鄰節點，進行遞歸的 DFS 調用。
3. 當一個節點的所有相鄰節點都已被訪問，回溯到上一個節點，繼續探索其他未訪問的相鄰節點。

以下是使用 Python 實現 DFS 的代碼示例：

# 定義一個圖（以鄰接表的形式表示）
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': [],'F': []
}# 用于標記已訪問的節點
visited = set()def dfs(node):if node in visited:returnvisited.add(node)print(node)for neighbor in graph[node]:dfs(neighbor)# 選擇一個起始節點，例如 'A'
dfs('A')