我正在尝试写一个算法,它可以找到在一个有向不连通图中,从起始顶点开始连接所有节点所需添加的最小边数
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
class Graph {
vector<vector<int>> vertices;
public:
Graph(int num_ver) {
vertices.resize(num_ver);
}
void addEdge(int ver1, int ver2) {
vertices[ver1].push_back(ver2);
}
vector<int>& getNeighbors(int ver) {
return vertices[ver];
}
int getVertices() {
return vertices.size();
}
};
void dfs(Graph& graph, int vertex, vector<bool>& visited) {
visited[vertex] = true;
vector<int>& neighbors = graph.getNeighbors(vertex);
for (int i = 0; i < neighbors.size(); i++) {
int n = neighbors[i];
if (!visited[n]) {
dfs(graph, n, visited);
}
}
}
int findMinEdges(Graph& graph) {
int num_vertices = graph.getVertices();
vector<bool> visited(num_vertices, false);
int edges = 0;
for (int i = 0; i < num_vertices; i++) {
if (!visited[i]) {
dfs(graph, i, visited);
edges++;
}
}
return (edges - 1);
}
int main() {
ifstream f("input.txt");
int vertices, edges, start;
f >> vertices >> edges >> start;
//cout << vertices << edges << start;'
Graph g(vertices + 1);
int v1, v2;
for (int i = 0; i < edges; i ++) {
f >> v1 >> v2;
g.addEdge(v1, v2);
}
f.close();
int min_edges = findMinEdges(g);
cout << "Minimum number of edges to make the graph connected: " << min_edges << endl;
ofstream o("output.txt");
o << min_edges;
o.close();
return 0;
}
代码使用一个简单的图形数据结构和dfs算法来尝试完成这一点。我试过在较小的输入上运行代码,它工作正常,但当输入大小增加时,它返回错误的答案。我已经尝试使用其他算法,即。图拉真的算法,但即使是对我来说也不起作用。
输入文件示例:
6 5 5
1 2
2 3
3 1
4 5
5 6
前3个数字表示总顶点,总边,起始顶点和下一行表示边(第一个数字是v1,第二个数字是v2)。
代码可以很好地处理这个问题,但不能处理较大的输入。我似乎不明白问题出在哪里!
https://file.io/bHnJHoqSE3ji包含输入文本文件。算法给出的输出是356,预期输出是263。
2条答案
按热度按时间nle07wnf1#
首先,你的邻接列表似乎是基于1的,而访问数组是基于0的,有时候你会把邻接列表当作基于0的。
其次,我注意到你根本没有使用变量start。但是,如果图表看起来像这样:
2 <- 1
如果起始节点是2,则答案是1。如果起始节点为1,则答案为0。如果你没有在代码中使用start,你的算法就不可能是正确的。
cngwdvgl2#
正如@TYeung指出的,您错过了使用开始顶点。如果你从指定的顶点开始,你会得到更好的结果:
但是,是否获得最小边数取决于输入顶点的顺序。
考虑这个图
| DFS启动|未访问的|边缘|
| - -----|- -----|- -----|
| 0|二三|0|
| 2| 3|一个|
| 3|- ----|2|
现在以不同的顺序输入折点
| DFS启动|未访问的|边缘|
| - -----|- -----|- -----|
| 0|二三|0|
| 3|- ----|一个|