初学者图论教程

图论是计算机科学和数学中的一个重要分支，它研究图结构及其应用。在本教程中，我们将从基础概念开始，逐步深入到一些常见的图论算法。

图的基本概念

• 图（Graph）：由顶点（Vertex）和边（Edge）组成的集合。
• 无向图（Undirected Graph）：边没有方向的图。
• 有向图（Directed Graph）：边有方向的图。
• 顶点度（Degree of Vertex）：与一个顶点相连的边的数量。

图的表示方法

• 邻接矩阵（Adjacency Matrix）
• 邻接表（Adjacency List）

常见的图论算法

• 深度优先搜索（DFS）
• 广度优先搜索（BFS）
• 最短路径算法（Dijkstra算法、Floyd算法）
• 最小生成树（Prim算法、Kruskal算法）

深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索树或图的算法。它沿着一个分支一直走到尽头，然后回溯，再沿着另一条分支继续。

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            # 处理当前顶点
            for neighbor in graph[vertex]:
                stack.append(neighbor)

最短路径算法（Dijkstra算法）

Dijkstra算法用于找到图中两点之间的最短路径。

def dijkstra(graph, start, end):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    previous_vertices = {vertex: None for vertex in graph}

    vertices = graph.copy()

    while vertices:
        current_vertex = min(vertices, key=lambda vertex: distances[vertex])
        vertices.pop(current_vertex)

        for neighbor, weight in graph[current_vertex].items():
            alternative_route = distances[current_vertex] + weight

            if alternative_route < distances[neighbor]:
                distances[neighbor] = alternative_route
                previous_vertices[neighbor] = current_vertex

    path, current_vertex = [], end

    while previous_vertices[current_vertex] is not None:
        path.insert(0, current_vertex)
        current_vertex = previous_vertices[current_vertex]

    if path:
        path.insert(0, current_vertex)

    return path

扩展阅读

想要深入了解图论，可以参考以下本站教程：

• 图论基础

Graph Theory