图论matlab代码整理

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

1. Dijkstra算法求最短路径

function [dist, path] = dijkstra(G, startNode)
% DIJKSTRA Calculates shortest path using Dijkstra's algorithm
%   G: adjacency matrix of the graph
%   startNode: index of the starting node
%   dist: vector of shortest distances from the starting node
%   path: vector of previous nodes in the shortest path

n = size(G, 1);
dist = inf(1, n);
path = zeros(1, n);

dist(startNode) = 0;
visited = false(1, n);

for i = 1:n
    [~, currNode] = min(dist + visited * inf);
    if isinf(dist(currNode))
        break
    end
    visited(currNode) = true;
    for j = find(G(currNode, :))
        alt = dist(currNode) + G(currNode, j);
        if alt < dist(j)
            dist(j) = alt;
            path(j) = currNode;
        end
    end
end
end

2. Bellman-Ford算法求最短路径

function [dist, path] = bellmanFord(G, startNode)
% BELLMANFORD Calculates shortest path using Bellman-Ford algorithm
%   G: adjacency matrix of the graph
%   startNode: index of the starting node
%   dist: vector of shortest distances from the starting node
%   path: vector of previous nodes in the shortest path

n = size(G, 1);
dist = inf(1, n);
path = zeros(1, n);

dist(startNode) = 0;

for i = 1:n-1
    for j = 1:n
        for k = find(G(:, j))'
            alt = dist(k) + G(k, j);
            if alt < dist(j)
                dist(j) = alt;
                path(j) = k;
            end
        end
    end
end

for j = 1:n
    for k = find(G(:, j))'
        alt = dist(k) + G(k, j);
        if alt < dist(j)
            error('Negative-weight cycle detected')
        end
    end
end
end

3. Kruskal算法求最小生成树

function [T, cost] = kruskal(G)
% KRUSKAL Calculates minimum spanning tree using Kruskal's algorithm
%   G: adjacency matrix of the graph
%   T: adjacency matrix of the minimum spanning tree
%   cost: cost of the minimum spanning tree

n = size(G, 1);
[~, edges] = sort(G(:));
T = zeros(n);
cost = 0;

for i = 1:numel(edges)
    [u, v] = ind2sub([n n], edges(i));
    if u == v || T(u, v) ~= 0
        continue
    end
    T(u, v) = G(u, v);
    T(v, u) = G(v, u);
    [~, path] = dijkstra(T, u);
    if path(v) ~= 0
        T(u, v) = 0;
        T(v, u) = 0;
    else
        cost = cost + G(u, v);
    end
end
end

4. Prim算法求最小生成树

function [T, cost] = prim(G)
% PRIM Calculates minimum spanning tree using Prim's algorithm
%   G: adjacency matrix of the graph
%   T: adjacency matrix of the minimum spanning tree
%   cost: cost of the minimum spanning tree

n = size(G, 1);
T = zeros(n);
cost = 0;

visited = false(1, n);
visited(1) = true;

while ~all(visited)
    [u, v] = find(G);
    idx = visited(u) ~= visited(v);
    if isempty(idx)
        error('Disconnected graph')
    end
    [~, i] = min(G(idx));
    u = u(idx); v = v(idx);
    T(u(i), v(i)) = G(u(i), v(i));
    T(v(i), u(i)) = G(v(i), u(i));
    visited(v(i)) = true;
    cost = cost + G(u(i), v(i));
end
end

5. 深度优先搜索（DFS）

function dfs(G, startNode)
% DFS Performs depth-first search on a graph
%   G: adjacency matrix of the graph
%   startNode: index of the starting node

n = size(G, 1);
visited = false(1, n);

dfsRecursive(G, startNode, visited);
end

function dfsRecursive(G, currNode, visited)
visited(currNode) = true;
fprintf('%d ', currNode);

for j = find(G(currNode, :))
    if ~visited(j)
        dfsRecursive(G, j, visited);
    end
end
end

6. 广度优先搜索（BFS）

function bfs(G, startNode)
% BFS Performs breadth-first search on a graph
%   G: adjacency matrix of the graph
%   startNode: index of the starting node

n = size(G, 1);
visited = false(1, n);
queue = startNode;

while ~isempty(queue)
    currNode = queue(1);
    queue(1) = [];
    visited(currNode) = true;
    fprintf('%d ', currNode);

    for j = find(G(currNode, :))
        if ~visited(j)
            queue(end+1) = j;
            visited(j) = true;
        end
    end
end
end

这些代码只是示例，具体实现可能需要根据具体问题进行修改和优化。