C++最小生成树的暴力

我想要用dfs实现这样一个代码：

输入：

第一行包含两个整数N, M，表示该图共有N 个结点和 M 条无向边 接下来 M 行每行包含三个整数Xi，Yi，Zi;，表示有一条长度为 Zi的无向边连接节点Xi，Yi

输出格式：

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

for一遍，在每一轮for中：

从i开始，遍历整个图，然后求出当前这一路径的值，用一个变量记录，然后一轮一轮的找到最小值

如何实现呢

以下答案由GPT-4.0Plus大模型与博主A努力中.......共同编写：
最小生成树是图论中的一个基本问题。给定一个加权的连通图,找到一个生成树,使其权重之和最小。
暴力算法思路是:枚举图中的所有可能的生成树,选择其中权重最小的一棵作为最小生成树。该算法时间复杂度高,只适用于规模较小的图。
C++代码实现如下:

c++
#include <bits/stdc++.h>
using namespace std;

// 图的邻接矩阵表示 
int G[100][100];    
int n;                // 图中节点数

// 枚举所有可能的生成树 
void dfs(int u, int weight, bitset<100> visit, int& minWeight) 
{
    // 递归终止条件:已经访问过n个节点,此时已找到一棵生成树 
    if (visit.count() == n) {   
        // 更新最小权重 
        minWeight = min(minWeight, weight); 
        return;
    }
    
    for (int v = 0; v < n; v++) {
        // 若边(u, v)存在且v未被访问过
        if (G[u][v] != 0 && !visit[v]) {  
            // 标记v为已访问,并递归访问其相邻节点
            visit[v] = 1;
            dfs(v, weight + G[u][v], visit, minWeight);
            // 回溯,撤销标记
            visit[v] = 0;
        }
    } 
}

int main() {
    // 读入图信息
    cin >> n;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++)
            cin >> G[i][j];
            
    int minWeight = INT_MAX;   // 最小权重初始化为最大值
    bitset<100> visit;       // 访问标记数组
    
    // 从节点0开始递归访问 
    visit[0] = 1;
    dfs(0, 0, visit, minWeight);
    
    cout << "最小生成树权重为:" << minWeight << endl;
}

该算法会从图中节点0开始,递归枚举所有以0为起点的生成树,并更新最小权重,最终得到最小生成树的权重。
时间复杂度为O(n×2^n),空间复杂度为O(n)。仅当图规模较小时可使用,图大时会超时。