图论matlab代码整理

以下是一些基本的图论算法的 MATLAB 代码：

### 深度优先搜索 (DFS)

function DFS(G, i, visited)
% G: 图
% i: 当前节点
% visited: 标记已访问过的节点

visited(i) = true;
fprintf('%d ', i);

% 递归遍历未访问的邻居节点
for j = 1:length(G(i,:))
    if G(i,j) == 1 && visited(j) == false
        DFS(G, j, visited);
    end
end
end

### 广度优先搜索 (BFS)

function BFS(G, i)
% G: 图
% i: 起始节点

queue = [];
visited = false(size(G, 1), 1);

queue = [queue i];
visited(i) = true;

while ~isempty(queue)
    node = queue(1);
    fprintf('%d ', node);
    queue(1) = [];
    
    % 遍历邻居节点
    for j = 1:length(G(node,:))
        if G(node,j) == 1 && visited(j) == false
            visited(j) = true;
            queue = [queue j];
        end
    end
end
end

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

function Dijkstra(G, source)
% G: 图
% source: 起始节点

n = size(G, 1);
dist = inf(n, 1);
dist(source) = 0;
visited = false(n, 1);

for i = 1:n-1
    % 找到距离最小的节点
    [mindist, u] = min(dist);
    
    visited(u) = true;
    
    % 更新邻居节点的距离
    for v = 1:n
        if G(u,v) ~= 0 && visited(v) == false
            alt = dist(u) + G(u,v);
            if alt < dist(v)
                dist(v) = alt;
            end
        end
    end
end

fprintf('最短路径：\n');
for i = 1:n
    fprintf('%d -> %d: %d\n', source, i, dist(i));
end
end

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

function Prim(G, source)
% G: 图
% source: 起始节点

n = size(G, 1);
dist = inf(n, 1);
dist(source) = 0;
visited = false(n, 1);
parent = zeros(n, 1);

for i = 1:n-1
    % 找到距离最小的节点
    [mindist, u] = min(dist);
    
    visited(u) = true;
    
    % 更新邻居节点的距离
    for v = 1:n
        if G(u,v) ~= 0 && visited(v) == false
            if G(u,v) < dist(v)
                dist(v) = G(u,v);
                parent(v) = u;
            end
        end
    end
end

fprintf('最小生成树：\n');
for i = 1:n
    if i ~= source
        fprintf('%d -> %d: %d\n', parent(i), i, G(parent(i),i));
    end
end
end