图论matlab代码整理

以下是一些常见的图论算法的 MATLAB 代码：

## 最短路径算法

### Dijkstra算法

function [dist, prev] = dijkstra(A, start)
    % A：邻接矩阵
    % start：起点
    
    n = length(A);    % 节点数量
    dist = Inf(1,n);  % 距离初始化为无穷大
    vis = false(1,n); % 标记节点是否被访问
    
    dist(start) = 0;  % 起点到自己的距离为0
    
    for i = 1:n
        % 选择距离最小的节点
        [d, u] = min(dist(~vis));
        if isempty(u)
            break; % 所有节点已被访问
        end
        u = find(dist == d, 1);
        vis(u) = true;  % 标记该节点已被访问
        for v = 1:n
            if A(u,v) > 0 && ~vis(v) % 如果存在边且未被访问过
                alt = dist(u) + A(u,v); % 计算新的距离
                if alt < dist(v)        % 如果更小则更新
                    dist(v) = alt;
                    prev(v) = u;
                end
            end
        end
    end
end

### Bellman-Ford算法

function [dist, prev] = bellman_ford(A, start)
    % A：邻接矩阵
    % start：起点
    
    n = length(A);    % 节点数量
    dist = Inf(1,n);  % 距离初始化为无穷大
    prev = zeros(1,n);% 记录前驱节点的数组
    
    dist(start) = 0;  % 起点到自己的距离为0
    
    for i = 1:n-1      % 最多迭代n-1次
        for u = 1:n    % 遍历所有节点
            for v = 1:n
                if A(u,v) > 0 % 如果存在边
                    alt = dist(u) + A(u,v); % 计算新的距离
                    if alt < dist(v)       % 如果更小则更新
                        dist(v) = alt;
                        prev(v) = u;
                    end
                end
            end
        end
    end
    
    % 检查是否存在负环
    for u = 1:n
        for v = 1:n
            if A(u,v) > 0
                if dist(u) + A(u,v) < dist(v)
                    error('Graph contains negative cycle');
                end
            end
        end
    end
end

## 最小生成树算法

### Prim算法

function [T, cost] = prim(A)
    % A：邻接矩阵
    
    n = length(A);         % 节点数量
    T = zeros(n,n);        % 存储最小生成树的邻接矩阵
    visited = false(1,n);  % 标记节点是否已被访问
    
    visited(1) = true;     % 从任意节点开始都可以
    while sum(visited) < n % 只要还有节点未被访问
        % 找到距离已访问节点最近的边
        min_dist = Inf;
        for u = find(visited)
            [d, v] = min(A(u,~visited));
            if d < min_dist
                min_dist = d;
                u_min = u;
                v_min = find(~visited, v);
            end
        end
        % 将该边添加到最小生成树中
        visited(v_min) = true;
        T(u_min,v_min) = min_dist;
        T(v_min,u_min) = min_dist;
    end
    
    cost = sum(sum(T)); % 计算最小生成树的总权值
end

### Kruskal算法

function [T, cost] = kruskal(A)
    % A：邻接矩阵
    
    n = length(A);         % 节点数量
    T = zeros(n,n);        % 存储最小生成树的邻接矩阵
    P = 1:n;               % 并查集初始化
    rank = zeros(1,n);     % 并查集初始化
    E = [];                % 存储所有边的权值和起点、终点
    for u = 1:n-1
        for v = u+1:n
            if A(u,v) > 0
                E(end+1,:) = [A(u,v) u v];
            end
        end
    end
    E = sortrows(E);       % 将边按权值从小到大排序
    
    for i = 1:size(E,1)
        u = E(i,2); v = E(i,3); w = E(i,1);
        if find_set(u,P) ~= find_set(v,P)
            T(u,v) = w;
            T(v,u) = w;
            [P,rank] = union_set(u,v,P,rank);
        end
    end
    
    cost = sum(sum(T)); % 计算最小生成树的总权值
end

function [P,rank] = union_set(u,v,P,rank)
    % 并查集合并操作
    ru = find_set(u,P); rv = find_set(v,P);
    if rank(ru) > rank(rv)
        P(rv) = ru;
    elseif rank(ru) < rank(rv)
        P(ru) = rv;
    else
        P(rv) = ru;
        rank(ru) = rank(ru) + 1;
    end
end

function r = find_set(u,P)
    % 并查集查找操作
    while P(u) ~= u
        u = P(u);
    end
    r = u;
end

## 最大流算法

### Ford-Fulkerson算法

function [f, Gf] = ford_fulkerson(G, s, t)
    % G：邻接矩阵
    % s：源点
    % t：汇点
    
    n = size(G,1);  % 节点数量
    Gf = G;         % 冗余图初值等于原图
    f = 0;          % 最大流初值为0
    
    while true
        % 使用BFS查找增广路径
        [pred, visited] = bfs(Gf, s, t);
        if ~visited(t)
            break; % 没有增广路径，算法结束
        end
        % 计算增广路径上的最小剩余容量
        min_cap = Inf;
        v = t;
        while v ~= s
            u = pred(v);
            min_cap = min(min_cap, Gf(u,v));
            v = u;
        end
        % 更新冗余图
        v = t;
        while v ~= s
            u = pred(v);
            Gf(u,v) = Gf(u,v) - min_cap;
            Gf(v,u) = Gf(v,u) + min_cap;
            v = u;
        end
        % 更新最大流
        f = f + min_cap;
    end
    
    % 辅助函数
    function [pred, visited] = bfs(G, s, t)
        % BFS查找增广路径
        pred = zeros(1,n);
        visited = false(1,n);
        queue = zeros(1,n);
        head = 1;
        tail = 1;
        queue(tail) = s;
        visited(s) = true;
        while head <= tail
            u = queue(head);
            head = head + 1;
            for v = 1:n
                if G(u,v) > 0 && ~visited(v)
                    pred(v) = u;
                    visited(v) = true;
                    if v == t
                        return;
                    end
                    tail = tail + 1;
                    queue(tail) = v;
                end
            end
        end
    end
end

### Edmonds-Karp算法

function [f, Gf] = edmonds_karp(G, s, t)
    % G：邻接矩阵
    % s：源点
    % t：汇点
    
    n = size(G,1);  % 节点数量
    Gf = G;         % 冗余图初值等于原图
    f = 0;          % 最大流初值为0
    
    while true
        % 使用BFS查找增广路径
        [pred, visited] = bfs(Gf, s, t);
        if ~visited(t)
            break; % 没有增广路径，算法结束
        end
        % 计算增广路径上的最小剩余容量
        min_cap = Inf;
        v = t;
        while v ~= s
            u = pred(v);
            min_cap = min(min_cap, Gf(u,v));
            v = u;
        end
        % 更新冗余图
        v = t;
        while v ~= s
            u = pred(v);
            Gf(u,v) = Gf(u,v) - min_cap;
            Gf(v,u) = Gf(v,u) + min_cap;
            v = u;
        end
        % 更新最大流
        f = f + min_cap;
    end
    
    % 辅助函数
    function [pred, visited] = bfs(G, s, t)
        % BFS查找增广路径
        pred = zeros(1,n);
        visited = false(1,n);
        queue = zeros(1,n);
        head = 1;
        tail = 1;
        queue(tail) = s;
        visited(s) = true;
        while head <= tail
            u = queue(head);
            head = head + 1;
            for v = 1:n
                if G(u,v) > 0 && ~visited(v)
                    pred(v) = u;
                    visited(v) = true;
                    if v == t
                        return;
                    end
                    tail = tail + 1;
                    queue(tail) = v;
                end
            end
        end
    end
end

## 拓扑排序算法

### Kahn算法

function order = kahn(A)
    % A：邻接矩阵
    
    n = length(A);          % 节点数量
    indegree = sum(A,1);    % 计算所有节点的入度
    S = find(indegree == 0);% 初始化入度为0的节点集合
    order = [];             % 存储排序结果
    
    while ~isempty(S)
        u = S(1);
        S(1) = [];
        order(end+1) = u;
        for v = find(A(u,:))
            indegree(v) = indegree(v) - 1;
            if indegree(v) == 0
                S(end+1) = v;
            end
        end
    end
    
    if length(order) < n
        error('Graph contains a cycle');
    end
end

### DFS算法

function order = dfs(A)
    % A：邻接矩阵
    
    n = length(A);          % 节点数量
    visited = false(1,n);   % 初始化所有节点为未访问状态
    order = [];             % 存储排序结果
    
    for u = 1:n
        if ~visited(u)
            dfs_visit(u);
        end
    end
    
    % 辅助函数
    function dfs_visit(u)
        visited(u) = true;
        for v = find(A(u,:))
            if ~visited(v)
                dfs_visit(v);
            end
        end
        order = [u order];
    end
end