如何将简单的图转换为树？

Question

我有一个简单的图（无向、未加权且没有多边）我应该将其转换为树。显然，在转换过程中，一些边缘可能会被删除，一些边缘将被添加。但移除的边和添加的边的总和应该最小化。

输入：

第一行：顶点数、边数（例如：n、m）

m 下一行：边列表 (ui ,vi)

输入示例：

4 0

输出：

第一行：要删除的边数（例如：p），要添加的边数（例如：q）

p 下一行：要删除的边列表（ui，vi）

q 下一行：要添加的边列表（ui，vi）

输出示例：

0 3

1 2

2 3

3 4

我使用了prim的算法来进行此转换，尽管我已尽力改进以下代码，但我无法得到正确的结果（可能是因为我无法最小化删除和添加的边的总和）。您能否提供一些建议或帮助来纠正此代码？

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

 const int MAXN = 2005;
 vector<pair<int, int>> adjacency[MAXN];
 bool isVisited[MAXN];
 int n, m;

 int prim() {
 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 int mst = 0;
 pq.push({0, 1});

 while (!pq.empty()) {
    int u = pq.top().second;
    int w = pq.top().first;
    pq.pop();

    if (isVisited[u]) continue;
    isVisited[u] = true;
    mst += w;

    for (auto v : adjacency[u]) {
        if (!isVisited[v.first]) {
            pq.push({v.second, v.first});
        }
    }
 }

 return mst;
 }

 int main() {
 cin >> n >> m;

 for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adjacency[u].push_back({v, 1});
    adjacency[v].push_back({u, 1});
 }

 int mst = prim();
 cout << m - (n - 1) - mst << " " << n - 1 - mst << endl;

 for (int i = 1; i <= n; i++) {
    if (!isVisited[i]) {
        cout << i << " ";
    }
 }
 cout << endl;

 for (int i = 1; i <= n; i++) {
    if (isVisited[i]) {
        for (auto v : adjacency[i]) {
            if (!isVisited[v.first]) {
                cout << i << " " << v.first << endl;
            }
        }
    }
 }

 return 0;
 }

Answer 1

从任意顶点运行 BFS。用G的所有顶点和BFS遍历过的所有边组成一棵树。如果 G 已连接，那么您就完成了。如果没有，请从您正在形成的树的任何顶点添加一条边到任何未连接的顶点，然后从那里重复。