如何通过替换循环最小化图的顶点?

Question

如何通过移除电路来最小化有向图的顶点数?这里有什么算法可以被改编吗?

已经有一个关于删除图中的循环的问题，但我特别想问的是通过删除图中的循环来最小化顶点的数量

Answer 1

假设您的问题的解决方案是简单地将循环转换为单个节点，当然，您可以轻松做到这一点。

当你执行广度优先搜索(BSF)或深度优先搜索(DFS)时，你会发现循环(即，如果你标记了你进入的路径，一旦你到达一个已经标记的节点，你就找到了一个循环)。因此，你可以很容易地通过存储你访问的每个节点的前身来找到循环，也就是说，如果你在节点u，你去节点v，你可以存储p[v] = u，所以如果你在v的邻接表中发现一些节点w已经访问过，你可以一个父一个父地走回去，直到你找到w，你有来自该循环的所有节点。

我不能保证这个算法的完整性，所以如果你可以自由地预处理你的图，你可以在它上面运行dfs，直到它没有改变，否则运行一定的n次，你发现是有效的。

void FindCycles(vector<Node> nodes){
int p[nodes.size()];
bool mark[nodes.size()]; //set all to false
stack<int> s;
s.push(nodes[0].id);
while(s.size()){
int u = s.pop();
mark[u] = true;
for(int v : nodes[u].adjs){
p[v] = u;
if(mark[v]) {
//found a cycle, call some method to reduce the graph
cout<<v<<" belongs to the cycle"<<endl;
while(u != v){
cout<<u<<" belongs to the cycle"<<endl;
u = p[u];
}
break;
}
else{
s.push(v);
}
}
}
}