Skip to content
TheChatArchiveThe Chat Archive
Claudeclaude-3-7-sonnet-20250219· AnthropicHugging Face LMArena Human Preference 140K

用MATLAB帮我写一个寻找拓扑图中最小权重圈基的算法

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Geminigemini-2.5-flash’s answer.
  1. User

    用MATLAB帮我写一个寻找拓扑图中最小权重圈基的算法

  2. Claude Assistant

    以下是用MATLAB实现寻找拓扑图中最小权重圈基的算法:

    function [cycleBase, totalWeight] = minWeightCycleBase(adjacencyMatrix, weights)
        % 输入:
        % adjacencyMatrix - 图的邻接矩阵
        % weights - 边的权重矩阵
        % 输出:
        % cycleBase - 最小权重圈基
        % totalWeight - 圈基的总权重
        
        n = size(adjacencyMatrix, 1); % 节点数
        
        % 构建边列表
        edges = [];
        for i = 1:n
            for j = i+1:n
                if adjacencyMatrix(i,j) == 1
                    edges = [edges; i j weights(i,j)];
                end
            end
        end
        
        % 按权重排序边
        [~, idx] = sort(edges(:,3));
        sortedEdges = edges(idx,:);
        
        % 初始化并查集
        parent = 1:n;
        rank = zeros(1,n);
        
        % 初始化最小生成树
        mst = [];
        
        % Kruskal算法构建最小生成树
        for i = 1:size(sortedEdges,1)
            u = sortedEdges(i,1);
            v = sortedEdges(i,2);
            
            rootU = find_root(parent, u);
            rootV = find_root(parent, v);
            
            if rootU ~= rootV
                mst = [mst; u v sortedEdges(i,3)];
                parent = union_sets(parent, rank, rootU, rootV);
            end
        end
        
        % 构建最小生成树的邻接表
        mstAdj = cell(1,n);
        for i = 1:size(mst,1)
            u = mst(i,1);
            v = mst(i,2);
            mstAdj{u} = [mstAdj{u}; v];
            mstAdj{v} = [mstAdj{v}; u];
        end
        
        % 找出不在最小生成树中的边
        nonTreeEdges = [];
        for i = 1:n
            for j = i+1:n
                if adjacencyMatrix(i,j) == 1
                    isTreeEdge = false;
                    for k = 1:size(mst,1)
                        if (mst(k,1) == i && mst(k,2) == j) || (mst(k,1) == j && mst(k,2) == i)
                            isTreeEdge = true;
                            break;
                        end
                    end
                    if ~isTreeEdge
                        nonTreeEdges = [nonTreeEdges; i j weights(i,j)];
                    end
                end
            end
        end
        
        % 为每条非树边找到基本圈
        cycleBase = cell(1, size(nonTreeEdges,1));
        totalWeight = 0;
        
        for i = 1:size(nonTreeEdges,1)
            u = nonTreeEdges(i,1);
            v = nonTreeEdges(i,2);
            w = nonTreeEdges(i,3);
            
            % 在MST中找到u到v的路径
            path = find_path(mstAdj, u, v, [], []);
            
            % 构建基本圈
            cycle = [path; u v w];
            cycleBase{i} = cycle;
            
            % 计算圈的权重
            cycleWeight = w;
            for j = 1:size(path,1)
                cycleWeight = cycleWeight + weights(path(j,1), path(j,2));
            end
            
            totalWeight = totalWeight + cycleWeight;
        end
    end
    
    function root = find_root(parent, x)
        if parent(x) ~= x
            parent(x) = find_root(parent, parent(x));
        end
        root = parent(x);
    end
    
    function parent = union_sets(parent, rank, x, y)
        rootX = find_root(parent, x);
        rootY = find_root(parent, y);
        
        if rootX == rootY
            return;
        end
        
        if rank(rootX) < rank(rootY)
            parent(rootX) = rootY;
        else
            parent(rootY) = rootX;
            if rank(rootX) == rank(rootY)
                rank(rootX) = rank(rootX) + 1;
            end
        end
    end
    
    function path = find_path(mstAdj, start, target, current_path, visited)
        if isempty(current_path)
            current_path = start;
            visited = zeros(1, length(mstAdj));
            visited(start) = 1;
        end
        
        if current_path(end) == target
            path = [];
            for i = 1:length(current_path)-1
                path = [path; current_path(i) current_path(i+1)];
            end
            return;
        end
        
        node = current_path(end);
        for i = 1:length(mstAdj{node})
            next = mstAdj{node}(i);
            if ~visited(next)
                visited(next) = 1;
                result = find_path(mstAdj, start, target, [current_path next], visited);
                if ~isempty(result)
                    path = result;
                    return;
                end
                visited(next) = 0;
            end
        end
        
        path = [];
    end
    

    需要我解释或分解这段代码吗?

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.