我需要将Trajan的递归算法转换为Trajan的迭代算法。我有一个类Graph，它包含几个方法和字段，这是需要的基本结构
class Graph {
protected:
vector< vector<int> > adjList;
int n;
这就是递归代码的样子
void DFSforTarjan(int u, vector<bool>& visited,
set<int>& AP, vector<int>& disc, vector<int>& low, int& time, int parent) {
int children = 0;
visited[u] = true;
disc[u] = low[u] = ++time;
for (int v : this->getNeighborVertex(u)) {
if (!visited[v]) {
children++;
DFSforTarjan(v, visited, AP, disc, low, time, u);
low[u] = min(low[u], low[v]);
if (parent != -1 && low[v] >= disc[u])
AP.insert(u);
}
else if (v != parent)
low[u] = min(low[u], disc[v]);
}
if (parent == -1 && children > 1)
AP.insert(u);
}
这是我尝试迭代实现的代码，但它不能正常工作，请帮忙
void DFSforTarjan(int u, vector<bool>& visited,
set<int>& AP, vector<int>& disc, vector<int>& low, vector<int>& parent, vector<int>& children, int& time) {
stack<int> st;
st.push(u);
while (!st.empty()) {
u = st.top();
st.pop();
if (parent[u] != -1) {
children[parent[u]]++;
}
visited[u] = true;
disc[u] = low[u] = ++time;
for (int v : this->getNeighborVertex(u)) {
if (!visited[v]) {
st.push(v);
parent[v] = u;
visited[v] = true;
}
else if (v != parent[u]) {
low[u] = min(low[u], disc[v]);
}
}
if (parent[u] == -1 && children[u] > 1)
AP.insert(u);
if (parent[u] != -1 && low[u] >= disc[parent[u]])
AP.insert(parent[u]);
}
for (int v : this->getNeighborVertex(u)) {
if (v != parent[u] && visited[v]) {
low[u] = min(low[u], low[v]);
}
}
}
设计递归函数时，尽量减少堆栈内存的使用非常重要。因此，通过使递归函数成为类的方法来减少每次调用时使用的参数数量。
这是一个仅使用三个参数实现 Tarjan 的类的定义。
/// @brief Find articulation points in an undirected graph
/// An articulation point is a vertex whose removal
/// increases the number of connected components in the graph.
class cTarjan
{
public:
/// @brief Find articulation points with Tarjan's algorithm
/// @param gd undirected graph description ( directed will raise exception )
/// @return vector of articulation point names
std::vector<std::string> ArticulationPoints(sGraphData &gd);
private:
std::vector<bool> visited; // true if vertex index has been visited
std::vector<int> disc; // discovery times of visited vertices
std::vector<int> low; // earliest visited vertex (the vertex with minimum
// discovery time) that can be reached from subtree
// rooted with vertex
std::set<int> sAP; // set of articulation point vertex indices
/// @brief Recursive search graph for articulation points
/// @param gd graph description
/// @param time current time
/// @param parent vertex index to start search from
void APRecurse(
sGraphData &gd,
int &time, int parent);
};
这是实现
std::vector<std::string> cTarjan::ArticulationPoints(sGraphData &gd)
{
if (gd.g.isDirected())
throw std::runtime_error(
"Tarjan works only for undirected graphs");
visited.clear();
visited.resize(gd.g.vertexCount(), false);
disc.clear();
disc.resize(gd.g.vertexCount(), 0);
low.clear();
low.resize(gd.g.vertexCount(), 0);
sAP.clear();
std::vector<std::string> vAP;
int time = 0, parent = -1;
// Adding this loop so that the
// code works even if we are given
// disconnected graph
for (int u = 0; u < gd.g.vertexCount(); u++)
if (!visited[u])
{
gd.startName = gd.g.userName(u);
APRecurse(
gd,
time, parent);
}
for (int p : sAP)
vAP.push_back(gd.g.userName(p));
return vAP;
}
// find articulation points in an undirected graph
// A recursive function that find articulation
// points using DFS traversal
// adj[] --> Adjacency List representation of the graph
// u --> The vertex to be visited next
// visited[] --> keeps track of visited vertices
// disc[] --> Stores discovery times of visited vertices
// low[] -- >> earliest visited vertex (the vertex with minimum
// discovery time) that can be reached from subtree
// rooted with current vertex
// parent --> Stores the parent vertex in DFS tree
// sAP[] --> Stores articulation points
void cTarjan::APRecurse(
sGraphData &gd,
int &time, int parent)
{
int u = gd.g.find(gd.startName);
// Count of children in DFS Tree
int children = 0;
// Mark the current node as visited
visited[u] = true;
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
// Go through all vertices adjacent to this
for (auto v : gd.g.adjacentOut(u))
{
// If v is not visited yet, then make it a child of u
// in DFS tree and recur for it
if (!visited[v])
{
children++;
sGraphData gd2;
gd2 = gd;
gd2.startName = gd.g.userName(v);
APRecurse(
gd2, time, u);
// Check if the subtree rooted with v has
// a connection to one of the ancestors of u
low[u] = std::min(low[u], low[v]);
// If u is not root and low value of one of
// its child is more than discovery value of u.
if (parent != -1 && low[v] >= disc[u])
sAP.insert(u);
}
// Update low value of u for parent function calls.
else if (v != parent)
low[u] = std::min(low[u], disc[v]);
}
// If u is root of DFS tree and has two or more children.
if (parent == -1 && children > 1)
sAP.insert(u);
}