图论基础概念与算法实现

# 1. 图论基础概念介绍

- 1.1 图论概述与基本术语解释
- 1.2 图的分类与表示方法
- 1.3 图的常见应用领域

# 2. 图的遍历算法

图的遍历算法是解决图相关问题的基础，其中深度优先搜索算法（DFS）和广度优先搜索算法（BFS）是两种常用的算法。下面将分别介绍它们的原理与实现。

# 3. 最短路径算法

在图论中，最短路径算法是一类用于计算图中两个节点之间最短路径的算法。最短路径算法在网络路由、交通规划等领域有着重要的应用。本章将介绍两种经典的最短路径算法：Dijkstra算法和Floyd-Warshall算法，并比较它们的优缺点。

#### 3.1 Dijkstra算法原理与实现

Dijkstra算法是一种用来找到图中一个节点到其他所有节点的最短路径的算法。它采用贪心策略，逐步扩展当前节点的最短路径，直到找到目标节点的最短路径。

# Python实现Dijkstra算法
def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    visited = set()
    while len(visited) < len(graph):
        node = min((set(distances.keys()) - visited), key=distances.get)
        visited.add(node)
        for neighbor, weight in graph[node].items():
            if distances[neighbor] > distances[node] + weight:
                distances[neighbor] = distances[node] + weight
    return distances

# 示例图的邻接表表示
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}
}

start_node = 'A'
print(dijkstra(graph, start_node))

**代码总结**：以上代码实现了Dijkstra算法，找到了从节点'A'到其他节点的最短路径。算法的时间复杂度为O(V^2)，其中V为节点数。

**结果说明**：输出为一个字典，表示从起始节点到其他节点的最短距离。在示例图中，从节点'A'到各个节点的最短距离为{'A': 0, 'B': 1, 'C': 3, 'D': 4}。

#### 3.2 Floyd-Warshall算法原理与实现

Floyd-Warshall算法是一种动态规划算法，用于计算图中所有节点之间的最短路径。相比于Dijkstra算法，Floyd-Warshall算法能处理带负权边的图。

# Python实现Floyd-Warshall算法
def floyd_warshall(graph):
    dist = graph.copy()
    nodes = list(graph.keys())
    for k in nodes:
        for i in nodes:
            for j in nodes:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

# 示例图的邻接矩阵表示
graph = {
    'A': {'A': 0, 'B': 1, 'C': 4, 'D': float('inf')},
    'B': {'A': 1, 'B': 0, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'C': 0, 'D': 1},
    'D': {'A': float('inf'), 'B': 5, 'C': 1, 'D': 0}
}

print(floyd_warshall(graph))

**代码总结**：以上代码实现了Floyd-Warshall算法，计算了示例图中所有节点之间的最短路径。算法的时间复杂度为O(V^3)，其中V为节点数。

**结果说明**：输出为一个邻接矩阵，表示任意两个节点之间的最短路径长度。在示例图中，最短路径矩阵为：

{
    'A': {'A': 0, 'B': 1, 'C': 3, 'D': 4},
    'B': {'A': 1, 'B': 0, 'C': 2, 'D': 4},
    'C': {'A': 3, 'B': 2, 'C': 0, 'D': 1},
    'D': {'A': 4, 'B': 4, 'C': 1, 'D': 0}
}

# 4. 最小生成树算法

在图论中，最小生成树（Minimum Spanning Tree）是一棵包含图中所有顶点的树，且所有边的权值之和最小。最小生成树算法常用于网络设计、电路布线、资源规划等领域。接下来，我们将介绍两种经典的最小生成树算法及其实现。

#### 4.1 Prim算法原理与实现

Prim算法是一种贪心算法，通过不断扩展生成树的节点集合，直至包含所有顶点，生成最小生成树。算法步骤如下：

1. 选择任意一个起始节点作为生成树的根节点。
2. 将与当前生成树集合相连的边中权值最小的边加入生成树。
3. 重复以上步骤，直到所有顶点都被包含在生成树中。

def prim(graph):
    n = len(graph)
    parent = [-1] * n  # 父节点列表，-1表示未连接
    key