用matlab写一个kruskal算法

以下是使用MATLAB实现Kruskal算法的示例代码：

function [MST, totalCost] = kruskal_algorithm(adjMatrix)
% KRUSKAL_ALGORITHM: Implements Kruskal's algorithm to find the minimum
% spanning tree of a given undirected graph
% 
% INPUTS:
% adjMatrix - n x n adjacency matrix of the graph
% 
% OUTPUTS:
% MST - adjacency matrix of the minimum spanning tree
% totalCost - total cost of the minimum spanning tree
% 
% Example usage:
% adjMatrix = [0 3 0 0 6; 3 0 1 0 0; 0 1 0 2 0; 0 0 2 0 4; 6 0 0 4 0];
% [MST, totalCost] = kruskal_algorithm(adjMatrix);

[n, ~] = size(adjMatrix);

% Create a list of edges with their weights
edges = [];
for i = 1:n
    for j = i:n
        if adjMatrix(i,j) > 0
            edges = [edges; i j adjMatrix(i,j)];
        end
    end
end

% Sort edges by their weights in ascending order
edges = sortrows(edges, 3);

% Initialize the minimum spanning tree
MST = zeros(n);
numEdges = 0;
totalCost = 0;

% Loop through each edge in the sorted list
for i = 1:size(edges,1)
    % Check if adding the current edge creates a cycle in MST
    if ~createsCycle(MST, edges(i,1), edges(i,2))
        % Add the current edge to MST
        MST(edges(i,1), edges(i,2)) = edges(i,3);
        MST(edges(i,2), edges(i,1)) = edges(i,3);
        numEdges = numEdges + 1;
        totalCost = totalCost + edges(i,3);
    end
    % Stop looping if all edges have been processed
    if numEdges == n-1
        break
    end
end

end

function cycle = createsCycle(MST, u, v)
% Check if adding an edge between u and v creates a cycle in MST

% Mark all vertices as unvisited
visited = zeros(size(MST,1),1);

% Traverse the graph from vertex u
stack = u;
visited(u) = 1;
while ~isempty(stack)
    current = stack(end);
    stack(end) = [];
    neighbors = find(MST(current,:)>0);
    for i = 1:length(neighbors)
        if ~visited(neighbors(i))
            visited(neighbors(i)) = 1;
            stack = [stack neighbors(i)];
        end
    end
end

% Check if vertex v was visited
if visited(v)
    cycle = true;
else
    cycle = false;
end

end

在上面的代码中，我们首先将图的边按权重升序排序，然后在循环中逐个添加边，同时检查添加边是否会在最小生成树中创建环。如果添加边不会创建环，则将其添加到最小生成树中。我们使用一个辅助函数`createsCycle`来检查是否添加了边会创建环。

下面是一个使用示例：

% Create an example adjacency matrix
adjMatrix = [0 3 0 0 6; 3 0 1 0 0; 0 1 0 2 0; 0 0 2 0 4; 6 0 0 4 0];

% Run Kruskal's algorithm to find the minimum spanning tree
[MST, totalCost] = kruskal_algorithm(adjMatrix);

% Display the results
disp('Minimum spanning tree:');
disp(MST);
disp(['Total cost: ' num2str(totalCost)]);