深度優先搜索（DFS）和廣度優先搜索（BFS）是兩種常用的圖遍歷算法，用于解決圖相關的問題。它們在搜索問題中具有廣泛的應用，如路徑搜索、連通性檢測等。
以下是具體區別：

（圖片引自：https://www.cnblogs.com/xuxinstyle/p/13261651.html）

深度優先搜索（DFS）

深度優先搜索是一種先探索到盡可能深的節點，再回溯到之前的節點的搜索策略。在實現上，DFS通常使用遞歸或棧來實現。

模板：

def dfs(node, visited):if node in visited:returnvisited.add(node)# Process current node# Explore neighborsfor neighbor in node.neighbors:dfs(neighbor, visited)

講解：

1. 從起始節點開始，訪問當前節點并標記為已訪問。
2. 對當前節點的鄰居節點進行遍歷，若鄰居節點未被訪問過，則以該鄰居節點為新的當前節點，繼續進行深度優先搜索。
3. 遞歸地進行上述步驟，直到所有可達節點都被訪問。

例題：

問題：給定一個無向圖，判斷是否存在從節點A到節點B的路徑。

def hasPath(graph, start, end):"""判斷是否存在從start到end的路徑Args:graph: 圖的鄰接表表示start: 起始節點end: 目標節點Returns:bool: 如果存在路徑返回True，否則返回False"""visited = set()return dfs(start, end, visited, graph)def dfs(node, end, visited, graph):"""深度優先搜索的輔助函數Args:node: 當前節點end: 目標節點visited: 已訪問過的節點集合graph: 圖的鄰接表表示Returns:bool: 如果存在路徑返回True，否則返回False"""if node == end:return Truevisited.add(node)for neighbor in graph[node]:if neighbor not in visited:if dfs(neighbor, end, visited, graph):return Truereturn False

廣度優先搜索（BFS）

廣度優先搜索是一種先探索到當前節點的所有鄰居節點，再逐層向外搜索的策略。通常使用隊列來實現。把每個還沒有搜索到的點依次放入隊列，然后再彈出隊列的頭部元素當做當前遍歷點。模板：
?

from collections import dequedef bfs(start):"""廣度優先搜索Args:start: 起始節點Returns:None"""queue = deque([start])visited = set()while queue:node = queue.popleft()if node not in visited:visited.add(node)# Process current node# 處理當前節點# Explore neighbors# 探索當前節點的鄰居節點for neighbor in node.neighbors:queue.append(neighbor)

要點

1. 將起始節點加入隊列，并標記為已訪問。
2. 當隊列不為空時，彈出隊首節點，對其未被訪問的鄰居節點進行遍歷。
3. 將未被訪問的鄰居節點加入隊列，并標記為已訪問。
4. 重復上述步驟，直到隊列為空。
分類模板：如果不需要確定當前遍歷到了哪一層，模板如下（這里參考：https://www.cnblogs.com/xuxinstyle/p/13261651.html）
?

while queue 不空：cur = queue.pop()for 節點 in cur的所有相鄰節點：if 該節點有效且未訪問過：queue.push(該節點)

如果要確定當前遍歷到了哪一層，BFS模板如下
這里增加了level表示當前遍歷到二叉樹中的哪一層了，也可以理解為在一個圖中，現在已經走了多少步了。size表示在當前遍歷層有多少個元素，也就是隊列中的元素數，我們把這些元素一次性遍歷完，即把當前層的所有元素都向外走了一步。

level = 0
while queue 不空：size = queue.size()while (size --) {cur = queue.pop()for 節點 in cur的所有相鄰節點：if 該節點有效且未被訪問過：queue.push(該節點)}level ++;

例題：

問題：給定一個無向圖，從節點A開始，找到到節點B的最短路徑的長度。

from collections import dequedef shortestPath(graph, start, end):"""尋找從start到end的最短路徑長度Args:graph: 圖的鄰接表表示start: 起始節點end: 目標節點Returns:int: 最短路徑長度，如果不存在路徑則返回-1"""queue = deque([(start, 0)])visited = set()while queue:node, distance = queue.popleft()if node == end:return distancevisited.add(node)for neighbor in graph[node]:if neighbor not in visited:queue.append((neighbor, distance + 1))return -1 ?# If no path found# Example graph representation: {node: [neighbors]}
graph = {'A': ['B', 'C'],'B': ['A', 'D', 'E'],'C': ['A', 'F'],'D': ['B'],'E': ['B', 'F'],'F': ['C', 'E']
}print(shortestPath(graph, 'A', 'F')) ?# Output: 2

這里使用了BFS算法來搜索從節點A到節點B的最短路徑的長度。

下面是代碼的一些區別：這里使用字典來存圖

BFS實現

#BFS實現
graph = {"A":["B","C"],"B":["A","C","D"],"C":["A","B","D","F"],"D":["B","C","E","F"],"E":["C","D"],"F":["D"]}
def BFS(graph,s):queue = []queue.append(s)#將元素 s 加入到隊列的尾部（隊尾）seen = set()#儲存出現過的量seen.add(s)while(len(queue)>0):vertex ?= queue.pop(0)#從隊列的頭部（隊首）彈出元素nodes = graph[vertex]#vertex的所有臨接點for w in nodes:if w not in seen:queue.append(w)seen.add(w)print(vertex)
BFS(graph,"A")

DFS實現 ?隊列—>棧

graph = {"A":["B","C"],"B":["A","C","D"],"C":["A","B","D","F"],"D":["B","C","E","F"],"E":["C","D"],"F":["D"]}
def BFS(graph,s):queue = []queue.append(s)seen = set()#儲存出現過的量seen.add(s)while(len(queue)>0):vertex ?= queue.pop()#pop(0)->pop() 先彈出最后一個元素 這里體現出棧nodes = graph[vertex]#vertex的所有臨接點for w in nodes:if w not in seen:queue.append(w)seen.add(w)print(vertex)BFS(graph,"A")