图论基础题实战：DFS、BFS与最短路径算法
图论是计算机科学中一个重要的分支，它广泛应用于网络设计、路径规划、社交网络分析等领域。在LeetCode等编程竞赛平台中，图论题目也是高频考点。本文将围绕图论基础题，通过DFS（深度优先搜索）、BFS（广度优先搜索）以及最短路径算法（如Dijkstra算法和Floyd算法）进行实战讲解。
DFS与BFS
DFS（深度优先搜索）
DFS是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着一条路径一直走到尽头，然后回溯到上一个节点，再沿着另一条路径继续搜索。
以下是一个使用Python实现的DFS算法示例，用于遍历一个无向图：
python
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
print(vertex)
visited.add(vertex)
stack.extend(graph[vertex] - visited)
示例图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
dfs(graph, 'A')
BFS（广度优先搜索）
BFS是一种用于遍历或搜索树或图的算法。它从根节点开始，按照层次遍历所有节点，直到找到目标节点或遍历完所有节点。
以下是一个使用Python实现的BFS算法示例，用于遍历一个无向图：
python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex)
visited.add(vertex)
queue.extend(graph[vertex] - visited)
bfs(graph, 'A')
最短路径算法
Dijkstra算法
Dijkstra算法是一种用于计算图中两点之间最短路径的算法。它适用于带权重的无向图或带权重的有向图。
以下是一个使用Python实现的Dijkstra算法示例：
python
import heapq
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
dijkstra(graph, 'A')
Floyd算法
Floyd算法是一种用于计算图中所有节点对之间最短路径的算法。它适用于带权重的有向图。
以下是一个使用Python实现的Floyd算法示例：
python
def floyd(graph):
distances = [[float('infinity')] len(graph) for _ in range(len(graph))]
for i in range(len(graph)):
distances[i][i] = 0
for i in range(len(graph)):
for j in range(len(graph)):
for k in range(len(graph)):
distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])
return distances
floyd(graph)
总结
本文通过DFS、BFS以及最短路径算法（Dijkstra算法和Floyd算法）的实战讲解，帮助读者更好地理解图论基础题。在实际应用中，根据具体问题选择合适的算法，能够提高算法的效率和准确性。希望本文对您的学习有所帮助。
Comments NOTHING