图算法基础教程

class GraphMatrix:
    def __init__(self, vertices):
        self.V = vertices
        # 初始化邻接矩阵，0 表示无边
        self.graph = [[0] * vertices for _ in range(vertices)]
    
    def add_edge(self, u, v, weight=1):
        """添加边（无向图）"""
        self.graph[u][v] = weight
        self.graph[v][u] = weight
    
    def display(self):
        """显示邻接矩阵"""
        for row in self.graph:
            print(row)

# 使用示例
g = GraphMatrix(4)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 3)
g.add_edge(1, 3, 2)
g.display()

def dfs_recursive(graph, vertex, visited=None):
    """
    深度优先搜索（递归版本）
    :param graph: 邻接表表示的图
    :param vertex: 当前顶点
    :param visited: 已访问集合
    """
    if visited is None:
        visited = set()
    
    visited.add(vertex)
    print(vertex, end=' ')  # 处理当前节点
    
    # 递归访问所有未访问的邻居
    for neighbor, weight in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# 测试
graph = {
    0: [(1, 1), (2, 1)],
    1: [(0, 1), (3, 1)],
    2: [(0, 1), (3, 1)],
    3: [(1, 1), (2, 1)]
}
print("DFS 遍历结果:")
dfs_recursive(graph, 0)
# 输出: 0 1 3 2

from collections import deque

def bfs(graph, start):
    """
    广度优先搜索
    :param graph: 邻接表表示的图
    :param start: 起始顶点
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')  # 处理当前节点
        
        # 将所有未访问的邻居加入队列
        for neighbor, weight in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 测试
print("\nBFS 遍历结果:")
bfs(graph, 0)
# 输出: 0 1 2 3

def bellman_ford(graph, vertices, start):
    """
    Bellman-Ford 算法
    :param graph: 边列表 [(u, v, weight), ...]
    :param vertices: 顶点数量
    :param start: 起始节点
    :return: 最短距离字典
    """
    # 初始化
    dist = {i: float('inf') for i in range(vertices)}
    dist[start] = 0
    
    # 松弛所有边 V-1 次
    for _ in range(vertices - 1):
        for u, v, weight in graph:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
    
    # 检测负权环
    for u, v, weight in graph:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            return None  # 存在负权环
    
    return dist

# 测试
edges = [
    (0, 1, 4),
    (0, 2, 5),
    (1, 2, -3),
    (2, 3, 4)
]
result = bellman_ford(edges, 4, 0)
if result:
    print("最短距离:", result)
else:
    print("图中存在负权环")

class UnionFind:
    """并查集数据结构"""
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]
    
    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        
        # 按秩合并
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        return True

def kruskal(vertices, edges):
    """
    Kruskal 最小生成树算法
    :param vertices: 顶点数量
    :param edges: 边列表 [(u, v, weight), ...]
    :return: MST 的边列表和总权重
    """
    # 按权重排序
    edges.sort(key=lambda x: x[2])
    
    uf = UnionFind(vertices)
    mst = []
    total_weight = 0
    
    for u, v, weight in edges:
        if uf.union(u, v):  # 如果不形成环
            mst.append((u, v, weight))
            total_weight += weight
            
            # MST 完成
            if len(mst) == vertices - 1:
                break
    
    return mst, total_weight

# 测试
vertices = 4
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

mst, weight = kruskal(vertices, edges)
print("最小生成树的边:")
for u, v, w in mst:
    print(f"{u} - {v}: {w}")
print(f"总权重: {weight}")