当前位置：首页 > article >正文

【第九天】零基础入门刷题Python-算法篇-数据结构与算法的介绍-六种常见的图论算法（持续更新）

article 2025/1/31 6:11:19

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、Python数据结构与算法的详细介绍
- 1.Python中的常用的图论算法
- - 2. 图论算法
  - 3.详细的图论算法
  - - 1）深度优先搜索（DFS）
    - 2）广度优先搜索（BFS）
    - 3）Dijkstra算法
    - 4）Prim算法
    - 5）Kruskal算法
    - 6）Floyd-Warshall算法
总结

前言

提示：这里可以添加本文要记录的大概内容：

第一天Python数据结构与算法的详细介绍
第二天五种常见的排序算法
第三天两种常见的搜索算法
第四天两种常见的递归算法
第五天一种常见的动态规划算法
第六天一种常见的贪心算法
第七天一种常见的分治算法
第八天一种常见的回溯算法
第九天六种常见的图论算法
第十天两种常见的字符串算法

提示：以下是本篇文章正文内容，下面案例可供参考

一、Python数据结构与算法的详细介绍

1.Python中的常用的图论算法

以下是Python中的一些常用算法：

2. 图论算法

图论算法：

深度优先搜索（DFS）：
用途：用于图的遍历或路径查找。
时间复杂度：O(V+E)，其中V是顶点数，E是边数。
空间复杂度：O(V)（递归栈空间）。
广度优先搜索（BFS）：
用途：用于图的遍历或最短路径查找（无权图）。
时间复杂度：O(V+E)。
空间复杂度：O(V)（队列空间）。
Dijkstra算法：
用途：用于计算单源最短路径（有权图）。
时间复杂度：O(V^2)（朴素实现）或O((V+E) log V)（优先队列实现）。
空间复杂度：O(V)。
最小生成树算法：
Prim算法：
用途：用于求解最小生成树。
时间复杂度：
使用邻接矩阵：O(V^2)。
使用斐波那契堆等数据结构：O(E log V)。
空间复杂度：根据具体实现而定，通常与顶点数和边的数量相关。
Kruskal算法：
用途：用于求解最小生成树。
时间复杂度：O(E log E)，其中E是边的数量。
空间复杂度：O(E)（存储边）和O(V)（并查集数据结构）。
Floyd-Warshall算法：
用途：用于计算所有顶点对之间的最短路径（有权图）。
时间复杂度：O(V^3)，其中V是顶点数。注意这里的复杂度是立方，与上述算法不同。
空间复杂度：O(V^2)（存储距离矩阵）。

3.详细的图论算法

1）深度优先搜索（DFS）

# 图的表示使用邻接表
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
 
# 深度优先搜索的递归实现
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # 访问节点，这里简单打印出来
 
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
 
    return visited
 
# 从节点 'A' 开始进行深度优先搜索
dfs(graph, 'A')

2）广度优先搜索（BFS）

from collections import deque

# 图的表示使用邻接表
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 广度优先搜索的实现
def bfs(graph, start):
    visited = set()  # 用于跟踪访问过的节点
    queue = deque([start])  # 初始化队列，将起始节点入队

    while queue:
        vertex = queue.popleft()  # 从队列左侧出队一个节点
        if vertex not in visited:
            visited.add(vertex)  # 标记该节点为已访问
            print(vertex)  # 访问节点，这里简单打印出来

            # 将该节点的所有未访问过的相邻节点入队
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)

# 从节点 'A' 开始进行广度优先搜索
bfs(graph, 'A')

3）Dijkstra算法

import heapq

# 图的表示使用邻接表，其中权重作为边的值
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

def dijkstra(graph, start):
    # 初始化距离字典，所有顶点的距离都设为无穷大（float('inf')），源点的距离设为0
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    
    # 优先队列，存储（距离，顶点）对，初始时只包含源点（0，start）
    priority_queue = [(0, start)]
    heapq.heapify(priority_queue)
    
    # 已访问顶点集合，用于避免重复处理
    visited = set()
    
    while priority_queue:
        # 弹出当前距离最小的顶点
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        # 如果该顶点已被访问过，则跳过
        if current_vertex in visited:
            continue
        
        # 标记该顶点为已访问
        visited.add(current_vertex)
        
        # 更新相邻顶点的距离
        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

# 从顶点 'A' 开始进行Dijkstra算法求解最短路径
start_vertex = 'A'
shortest_paths = dijkstra(graph, start_vertex)

# 打印结果
for vertex, distance in shortest_paths.items():
    print(f"从 {start_vertex} 到 {vertex} 的最短距离是 {distance}")

4）Prim算法

import heapq

def prim(graph):
    start_vertex = next(iter(graph))  # 选择任意一个顶点作为起始点
    mst = []
    visited = set()
    min_heap = [(0, start_vertex, None)]  # (权重, 当前顶点, 前驱顶点)
    
    while min_heap:
        weight, current_vertex, prev_vertex = heapq.heappop(min_heap)
        
        if current_vertex in visited:
            continue
        
        visited.add(current_vertex)
        
        if prev_vertex is not None:
            mst.append((prev_vertex, current_vertex, weight))
        
        for neighbor, edge_weight in graph[current_vertex].items():
            if neighbor not in visited:
                heapq.heappush(min_heap, (edge_weight, neighbor, current_vertex))
    
    return mst

# 图的表示（邻接表）
graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'A': 1, 'C': 1, 'D': 6},
    'C': {'A': 3, 'B': 1, 'D': 2},
    'D': {'B': 6, 'C': 2}
}

print("Prim's MST:", prim(graph))

5）Kruskal算法

class DisjointSet:
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}
    
    def find(self, item):
        if self.parent[item] != item:
            self.parent[item] = self.find(self.parent[item])
        return self.parent[item]
    
    def union(self, set1, set2):
        root1 = self.find(set1)
        root2 = self.find(set2)
        
        if root1 != root2:
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            elif self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1

def kruskal(graph):
    edges = []
    for u in graph:
        for v, weight in graph[u].items():
            if u < v:  # 避免重复边（无向图）
                edges.append((weight, u, v))
    
    edges.sort()  # 按权重排序
    
    vertices = set(u for u in graph for v in graph[u])
    disjoint_set = DisjointSet(vertices)
    mst = []
    
    for weight, u, v in edges:
        if disjoint_set.find(u) != disjoint_set.find(v):
            disjoint_set.union(u, v)
            mst.append((u, v, weight))
    
    return mst

# 图的表示（邻接表）
graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'A': 1, 'C': 1, 'D': 6},
    'C': {'A': 3, 'B': 1, 'D': 2},
    'D': {'B': 6, 'C': 2}
}

print("Kruskal's MST:", kruskal(graph))

6）Floyd-Warshall算法

def floyd_warshall(graph):
    # 初始化距离矩阵，使用无穷大表示不可达的顶点对
    num_vertices = len(graph)
    dist = [[float('inf')] * num_vertices for _ in range(num_vertices)]
    
    # 设置顶点到自身的距离为0
    for i in range(num_vertices):
        dist[i][i] = 0
    
    # 设置图的边权重
    for u in range(num_vertices):
        for v, weight in graph[u].items():
            v = list(graph.keys()).index(v)  # 将顶点转换为索引
            dist[u][v] = weight
    
    # Floyd-Warshall算法核心
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf') and dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    # 输出结果
    for u in range(num_vertices):
        for v in range(num_vertices):
            if dist[u][v] == float('inf'):
                print(f"从顶点 {u} 到顶点 {v} 不可达", end='\t')
            else:
                print(f"从顶点 {u} 到顶点 {v} 的最短距离是 {dist[u][v]}", end='\t')
        print()

# 图的表示（邻接表转换为索引表示）
# 注意：这里为了简化，我们假设顶点已经按字母顺序排列，并可以直接用字母的ASCII码减去'A'的ASCII码来作为索引
# 在实际应用中，你可能需要一个映射来将顶点名称转换为索引
graph = [
    {'B': 1, 'C': 3},
    {'A': 1, 'C': 1, 'D': 6},
    {'A': 3, 'B': 1, 'D': 2},
    {'B': 6, 'C': 2}
]

# 由于Floyd-Warshall算法需要顶点索引，而上面的graph表示是基于顶点名称的邻接表，
# 在这里我们直接按字母顺序和数量假设了顶点索引，并跳过了转换步骤。
# 在实际应用中，请确保图的表示与算法输入要求相匹配。

# 调用Floyd-Warshall算法
floyd_warshall(graph)