数据结构之图论详解-EW帮帮网

图论（Graph Theory）是数学中的一个重要分支，也是计算机科学中非常核心的内容。图是一种非线性的数据结构，广泛应用于各种问题中，比如社交网络、路径查找、资源调度、网络流量等。图的基本概念、常见算法以及应用都是图论研究的关键内容。

本文将系统地介绍图的基本概念、表示方法、常见算法（如深度优先搜索、广度优先搜索、最短路径、最小生成树等），并通过代码示例加以说明。

1. 图的基本概念

图 ( G ) 由一组节点（或称顶点）和一组边组成。边连接两个顶点。图可以用以下元素来定义：

V：顶点集合（Vertex Set），图中所有顶点的集合。
E：边集合（Edge Set），图中所有边的集合。
有向图（Directed Graph, Digraph）：边有方向，表示从一个顶点到另一个顶点的单向关系。
无向图（Undirected Graph）：边没有方向，表示顶点之间的双向关系。
加权图（Weighted Graph）：每条边都有一个权重，通常表示边的代价或长度。
无权图（Unweighted Graph）：边没有权重。

2. 图的表示方法

图的表示方法有多种，常见的有以下几种：

2.1 邻接矩阵（Adjacency Matrix）

邻接矩阵是一个二维数组（矩阵），其中的每个元素 ( A[i][j] ) 表示从顶点 ( i ) 到顶点 ( j ) 是否有边（如果有边，则值为1，否则为0）。对于加权图，矩阵中的元素值可以表示边的权重。

优点：

查找边的存在与否非常高效，时间复杂度是 ( O(1) )。
适用于稠密图（边比较多的图）。

缺点：

空间复杂度较高，对于 ( V ) 个顶点的图，需要 ( O(V^2) ) 的空间。
不适用于稀疏图（边比较少的图）。

2.2 邻接表（Adjacency List）

邻接表是为每个顶点维护一个链表或列表，存储与该顶点相连的所有其他顶点。对于加权图，链表的每个元素通常包括目标顶点和权重。

优点：

空间复杂度较低，适用于稀疏图。
对于大多数图算法，邻接表的存储效率较好。

缺点：

查找边的存在与否效率较低，最坏情况下时间复杂度是 ( O(V) )。

3. 常见图算法

3.1 深度优先搜索（DFS）

深度优先搜索（DFS）是一种用于遍历图的算法，它沿着一条路径尽可能深入图中的每一个节点，直到不能继续深入为止，然后回溯到上一节点，继续进行搜索。

DFS的实现：

使用递归或者栈来实现。
从某个顶点开始，遍历所有未访问的相邻节点，直到没有未访问的节点为止。

function dfs(graph, node, visited)
    % graph: 邻接表表示的图
    % node: 当前节点
    % visited: 记录已访问节点的布尔数组
    
    % 标记当前节点为已访问
    visited(node) = true;
    fprintf('%d ', node);
    
    % 遍历所有相邻节点
    for i = 1:length(graph{node})
        neighbor = graph{node}(i);
        if ~visited(neighbor)
            dfs(graph, neighbor, visited);
        end
    end
end

3.2 广度优先搜索（BFS）

广度优先搜索（BFS）是一种逐层遍历图的算法。它首先访问起始节点，然后访问与起始节点距离为1的节点，再访问与起始节点距离为2的节点，依此类推。

BFS的实现：

使用队列来实现。
从起始节点开始，将其所有相邻节点加入队列，并按顺序访问队列中的节点。

function bfs(graph, start)
    % graph: 邻接表表示的图
    % start: 起始节点
    
    visited = false(1, length(graph)); % 记录已访问节点
    queue = []; % 队列
    queue = [queue, start]; % 将起始节点加入队列
    visited(start) = true; % 标记起始节点为已访问
    
    while ~isempty(queue)
        node = queue(1); % 获取队列中的第一个节点
        queue = queue(2:end); % 从队列中移除该节点
        fprintf('%d ', node);
        
        % 遍历所有相邻节点
        for i = 1:length(graph{node})
            neighbor = graph{node}(i);
            if ~visited(neighbor)
                visited(neighbor) = true;
                queue = [queue, neighbor]; % 将相邻节点加入队列
            end
        end
    end
end

3.3 最短路径算法

最短路径算法用于在图中查找从起始节点到目标节点的最短路径。常见的算法有Dijkstra算法和Bellman-Ford算法。

Dijkstra算法（适用于无负权图）：
Dijkstra算法是一种贪心算法，能够找到从起始节点到其他节点的最短路径。

function [dist, prev] = dijkstra(graph, start)
    % graph: 加权图的邻接矩阵
    % start: 起始节点
    n = size(graph, 1);  % 图中顶点的数量
    dist = inf(1, n);    % 初始化距离
    dist(start) = 0;     % 起始节点的距离为0
    prev = NaN(1, n);    % 前驱节点
    
    unvisited = 1:n;     % 所有节点尚未访问
    
    while ~isempty(unvisited)
        [~, u] = min(dist(unvisited));  % 选择未访问节点中距离起点最近的节点
        u = unvisited(u);  % 获取实际的节点编号
        unvisited = setdiff(unvisited, u);  % 从未访问节点集中移除u
        
        for v = 1:n
            if graph(u, v) > 0  % 判断是否有边(u, v)
                alt = dist(u) + graph(u, v);  % 计算到达v的新的路径长度
                if alt < dist(v)
                    dist(v) = alt;  % 更新最短路径
                    prev(v) = u;    % 更新前驱节点
                end
            end
        end
    end
end

3.4 最小生成树（MST）

最小生成树问题是指在加权无向图中，找到一棵包含图中所有顶点的树，使得树的边的总权重最小。常见的算法有Prim算法和Kruskal算法。

Prim算法（贪心算法）：
Prim算法从任意一个顶点开始，逐步扩展生成树，直到包含所有顶点。

function mst = prim(graph)
    n = size(graph, 1);  % 图中顶点的数量
    mst = zeros(n);      % 初始化最小生成树
    key = inf(1, n);     % 保存各顶点到生成树的最小边权
    key(1) = 0;          % 选择第一个节点作为起点
    parent = NaN(1, n);  % 记录各顶点的父节点
    
    for count = 1:n
        [~, u] = min(key);  % 找到未访问节点中权重最小的节点
        key(u) = inf;       % 标记节点u已加入生成树
        
        for v = 1:n
            if graph(u, v) > 0 && graph(u, v) < key(v)
                key(v) = graph(u, v);  % 更新权重
                parent(v) = u;         % 更新父节点
            end
        end
    end
    
    % 输出生成树的边和权重
    for i = 2:n
        mst(i) = parent(i);
    end
end

4. 总结

图论是计算机科学中一个重要的领域，涉及到许多经典算法，广泛应用于路径寻找、网络流、调度问题等。通过本文的介绍，我们对图的基本概念、表示方法以及常见的图算法（如DFS、BFS、最短路径、最小生成树等）有了一个初步了解。在实际应用中，我们可以根据问题

的具体要求选择不同的图算法进行求解。

数据结构之图论详解