图论matlab代码整理

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

1. Dijkstra 算法

function [dist, path] = dijkstra(A, s, t)
% A: 邻接矩阵
% s: 起点
% t: 终点
% dist: 最短距离
% path: 最短路径

n = size(A, 1);
d = inf(1, n); % 初始化距离
d(s) = 0; % 起点到自己的距离为 0
p = 1:n; % 未访问的点集合
path = cell(1, n); % 记录路径

while ~isempty(p)
    [~, u] = min(d(p));
    u = p(u);
    p(p == u) = []; % 从未访问的点集合中移除 u
    
    if u == t % 如果到达终点，则直接返回
        dist = d(t);
        path{s} = s;
        for i = 2:length(path)
            path{i} = [path{i-1}, path{i}];
        end
        path = path{t};
        return;
    end
    
    for v = find(A(u,:))
        alt = d(u) + A(u,v);
        if alt < d(v)
            d(v) = alt;
            path{v} = [path{u}, v];
        end
    end
end

dist = [];
path = [];

2. 最小生成树 (Prim 算法)

function [T, cost] = prim(A)
% A: 邻接矩阵
% T: 最小生成树
% cost: 最小生成树的权重之和

n = size(A, 1);
T = false(n);
cost = 0;
d = inf(1, n);
d(1) = 0;
p = 1:n;
while ~isempty(p)
    [~, u] = min(d(p));
    u = p(u);
    p(p == u) = [];
    if d(u) == inf % 如果存在无法到达的节点，则直接返回
        T = [];
        cost = inf;
        return;
    end
    if u ~= 1
        T(u, d(u)) = true;
        T(d(u), u) = true;
        cost = cost + A(u, d(u));
    end
    for v = p
        if A(u,v) < d(v)
            d(v) = A(u,v);
            d(v) = u;
        end
    end
end

3. 最短路径 (Floyd 算法)

function D = floyd(A)
% A: 邻接矩阵
% D: 最短路径矩阵

n = size(A, 1);
D = A;
for k = 1:n
    for i = 1:n
        for j = 1:n
            D(i,j) = min(D(i,j), D(i,k)+D(k,j));
        end
    end
end

4. 拓扑排序

function order = topsort(A)
% A: 邻接矩阵
% order: 拓扑排序结果

n = size(A, 1);
indegree = sum(A, 1);
order = [];
while true
    nodes = find(indegree == 0);
    if isempty(nodes)
        break;
    end
    order = [order, nodes];
    indegree(nodes) = inf;
    for u = nodes
        for v = find(A(u,:))
            indegree(v) = indegree(v) - 1;
        end
    end
end
if length(order) < n
    order = [];
end

5. 最大流 (Ford-Fulkerson 算法)

function [f, G] = maxflow(A, s, t)
% A: 邻接矩阵
% s: 源点
% t: 汇点
% f: 最大流量
% G: 剩余网络

n = size(A, 1);
G = A;
f = 0;
while true
    [P, c] = findpath(G, s, t); % 寻找增广路径
    if isempty(P)
        break;
    end
    f = f + c;
    for i = 1:length(P)-1
        u = P(i);
        v = P(i+1);
        G(u,v) = G(u,v) - c;
        G(v,u) = G(v,u) + c;
    end
end

function [P, c] = findpath(G, s, t) % 寻找增广路径
    n = size(G, 1);
    P = [];
    c = inf;
    visited = false(1, n);
    visited(s) = true;
    stack = s;
    while ~isempty(stack)
        u = stack(end);
        stack(end) = [];
        for v = find(G(u,:))
            if ~visited(v) && G(u,v) > 0
                visited(v) = true;
                P = [P, v];
                c = min(c, G(u,v));
                if v == t
                    return;
                end
                stack = [stack, v];
            end
        end
    end
    P = [];
    c = 0;
end

end