图论matlab代码整理

以下是一些常见的图论算法在MATLAB中的实现：

## 最短路径算法
### Dijkstra算法

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

n = size(A, 1);
dist = Inf(1, n);
dist(s) = 0;
path = zeros(1, n);

visited = zeros(1, n);
for i = 1:n
    [~, u] = min(dist.*~visited);
    visited(u) = 1;
    for v = 1:n
        if A(u, v) > 0 && dist(u) + A(u, v) < dist(v)
            dist(v) = dist(u) + A(u, v);
            path(v) = u;
        end
    end
end

if t ~= 0
    p = t;
    while p ~= s
        path(p) = path(path(p));
        p = path(p);
    end
    path = path(path~=0);
end

### Floyd-Warshall算法

function D = floyd_warshall(A)
% A: 图的邻接矩阵
% D: 任意两点间的最短距离

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

## 最小生成树算法
### Prim算法

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

n = size(A, 1);
T = zeros(n-1, 2);
TCost = 0;

visited = zeros(1, n);
visited(1) = 1;
for k = 2:n
    minCost = Inf;
    for i = 1:n
        if visited(i) == 1
            for j = 1:n
                if visited(j) == 0 && A(i, j) > 0 && A(i, j) < minCost
                    minCost = A(i, j);
                    u = i;
                    v = j;
                end
            end
        end
    end
    T(k-1, :) = [u, v];
    TCost = TCost + minCost;
    visited(v) = 1;
end

### Kruskal算法

function [T, TCost] = kruskal(A)
% A: 图的邻接矩阵
% T: 最小生成树的边集
% TCost: 最小生成树的权重和

n = size(A, 1);
T = zeros(n-1, 2);
TCost = 0;

edges = [];
for i = 1:n
    for j = i+1:n
        if A(i, j) > 0
            edges = [edges; [i, j, A(i, j)]];
        end
    end
end
edges = sortrows(edges, 3);

parent = 1:n;
for i = 1:size(edges, 1)
    u = edges(i, 1);
    v = edges(i, 2);
    w = edges(i, 3);
    pu = find(parent, u);
    pv = find(parent, v);
    if pu ~= pv
        TCost = TCost + w;
        parent(pu) = pv;
        T(i, :) = [u, v];
    end
end

## 最大流算法
### Ford-Fulkerson算法

function maxflow = ford_fulkerson(C, s, t)
% C: 图的容量矩阵
% s: 源点
% t: 汇点
% maxflow: 最大流

n = size(C, 1);
F = zeros(n, n);

while true
    [P, f] = find_path(C, F, s, t);
    if f == 0
        break;
    end
    for i = 1:length(P)-1
        u = P(i);
        v = P(i+1);
        F(u, v) = F(u, v) + f;
        F(v, u) = F(v, u) - f;
    end
end

maxflow = sum(F(s, :));

### Edmonds-Karp算法

function maxflow = edmonds_karp(C, s, t)
% C: 图的容量矩阵
% s: 源点
% t: 汇点
% maxflow: 最大流

n = size(C, 1);
F = zeros(n, n);
P = zeros(1, n);

while true
    [f, P] = bfs(C, F, s, t, P);
    if f == 0
        break;
    end
    for i = 1:length(P)-1
        u = P(i);
        v = P(i+1);
        F(u, v) = F(u, v) + f;
        F(v, u) = F(v, u) - f;
    end
end

maxflow = sum(F(s, :));

## 图的连通性算法
### 深度优先搜索

function visited = dfs(A, s)
% A: 图的邻接矩阵
% s: 起点
% visited: 节点访问顺序

n = size(A, 1);
visited = zeros(1, n);

stack = s;
while ~isempty(stack)
    u = stack(end);
    stack(end) = [];
    if visited(u) == 0
        visited(u) = 1;
        neighbors = find(A(u, :) > 0);
        stack = [stack, neighbors];
    end
end

### 广度优先搜索

function visited = bfs(A, s)
% A: 图的邻接矩阵
% s: 起点
% visited: 节点访问顺序

n = size(A, 1);
visited = zeros(1, n);

queue = s;
while ~isempty(queue)
    u = queue(1);
    queue(1) = [];
    if visited(u) == 0
        visited(u) = 1;
        neighbors = find(A(u, :) > 0);
        queue = [queue, neighbors];
    end
end

### 连通性判断

function [flag, visited] = is_connected(A)
% A: 图的邻接矩阵
% flag: 是否连通
% visited: 节点访问顺序

n = size(A, 1);
visited = zeros(1, n);

dfs(A, 1);
if sum(visited) == n
    flag = true;
else
    flag = false;
end