图论matlab代码整理

下面是一些基本的图论算法的 MATLAB 代码实现，包括：

1. 图的表示方式：邻接矩阵和邻接表
2. 图的遍历：深度优先搜索和广度优先搜索
3. 最短路径算法：Dijkstra算法和Floyd算法
4. 最小生成树算法：Prim算法和Kruskal算法

图的表示方式：

邻接矩阵：

% 用邻接矩阵表示图
% G为邻接矩阵，n为节点数
G = zeros(n);
G(i,j) = 1; % i,j之间有一条边

邻接表：

% 用邻接表表示图
% G为邻接表，n为节点数
G = cell(1,n);
G{i} = [j1,j2,...]; % i的邻居节点为j1,j2,...

图的遍历：

深度优先搜索：

% 深度优先搜索
% G为邻接表，n为节点数，start为起点
visited = false(1,n);
dfs(G,start,visited);

function dfs(G,i,visited)
    visited(i) = true;
    neighbors = G{i};
    for j=1:length(neighbors)
        if ~visited(neighbors(j))
            dfs(G,neighbors(j),visited);
        end
    end
end

广度优先搜索：

% 广度优先搜索
% G为邻接表，n为节点数，start为起点
visited = false(1,n);
queue = start;
visited(start) = true;
while ~isempty(queue)
    i = queue(1);
    queue(1) = [];
    neighbors = G{i};
    for j=1:length(neighbors)
        if ~visited(neighbors(j))
            visited(neighbors(j)) = true;
            queue(end+1) = neighbors(j);
        end
    end
end

最短路径算法：

Dijkstra算法：

% Dijkstra算法
% G为邻接矩阵，n为节点数，start为起点
dist = inf(1,n);
dist(start) = 0;
visited = false(1,n);
for i=1:n
    % 找到距离起点最近的节点
    [~,j] = min(dist(~visited));
    visited(j) = true;
    neighbors = find(G(j,:));
    for k=1:length(neighbors)
        if ~visited(neighbors(k)) && dist(j)+G(j,neighbors(k))<dist(neighbors(k))
            dist(neighbors(k)) = dist(j)+G(j,neighbors(k));
        end
    end
end

Floyd算法：

% Floyd算法
% G为邻接矩阵，n为节点数
dist = G;
for k=1:n
    for i=1:n
        for j=1:n
            if dist(i,k)+dist(k,j)<dist(i,j)
                dist(i,j) = dist(i,k)+dist(k,j);
            end
        end
    end
end

最小生成树算法：

Prim算法：

% Prim算法
% G为邻接矩阵，n为节点数
visited = false(1,n);
visited(1) = true;
dist = G(1,:);
parent = zeros(1,n);
for i=2:n
    [~,j] = min(dist(~visited));
    visited(j) = true;
    parent(j) = find(G(:,j)==dist(j));
    neighbors = find(G(j,:));
    for k=1:length(neighbors)
        if ~visited(neighbors(k)) && G(j,neighbors(k))<dist(neighbors(k))
            dist(neighbors(k)) = G(j,neighbors(k));
            parent(neighbors(k)) = j;
        end
    end
end

Kruskal算法：

% Kruskal算法
% edges为边的列表，每条边为[u,v,w]，表示u和v之间有一条权重为w的边
% n为节点数
edges = sortrows(edges,3);
parent = 1:n;
rank = zeros(1,n);
mst = [];
for i=1:size(edges,1)
    u = edges(i,1);
    v = edges(i,2);
    w = edges(i,3);
    p1 = find(parent(u));
    p2 = find(parent(v));
    if p1~=p2
        mst(end+1,:) = edges(i,:);
        if rank(p1)>rank(p2)
            parent(p2) = p1;
        else
            parent(p1) = p2;
            if rank(p1)==rank(p2)
                rank(p2) = rank(p2)+1;
            end
        end
    end
end