在图中查找桥梁而无需递归 [英] Finding bridges in graph without recursion

问题描述

我有这段代码可以在连通图中找到桥梁：

I have this code to find bridges in a connected graph:

void dfs (int v, int p = -1) {
    used[v] = true;
    tin[v] = fup[v] = timer++;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (to == p)  continue;
        if (used[to])
            fup[v] = min (fup[v], tin[to]);
        else {
            dfs (to, v);
            fup[v] = min (fup[v], fup[to]);
            if (fup[to] > tin[v])
                printf("%d %d", v, to);
        }
    }
}

如何在不使用的情况下重写递归？我知道，有可能这样做，我应该使用堆栈，但是必须在递归调用dfs（）之后执行此行，而我不能使用堆栈来实现：

How to rewrite it without using recursion? I know, it's possible to do it and I should use stack, but this line must be executed after recursive call of dfs() and I can't achieve with a stack:

fup[v] = min(fup[v], fup[to])

那么，如何迭代地重写我的算法？

So, how to rewrite my algorithm iteratively?

推荐答案

您想制作一个堆栈框架结构

You want to make a "stack frame" structure

struct Frame {
    Frame(int v, int p, int i, Label label);
    int v;
    int p;
    int i;
};

// constructor here

c $ c> stack< Frame> 。在所有这些字段之间，可以模拟调用堆栈（使用 unested代码给出总体思路）。

and, as you say, a stack<Frame>. Between all of these fields, it's possible to simulate the call stack (untested code to give the general idea).

void dfs(int v, int p = -1) {
  stack<Frame> st;
  st.push(Frame(v, p, 0));
  do {
    Frame fr(st.top());
    st.pop();
    v = fr.v;
    p = fr.p;
    int i(fr.i);
    if (i > 0) {
      int to(g[v][i - 1]);
      fup[v] = min(fup[v], fup[to]);
      if (fup[to] > tin[v]) { printf("%d %d", v, to); }
      if (i == g[v].size()) { continue; }
    } else if (i == 0) {
      used[v] = true;
      tin[v] = fup[v] = timer++;
    }
    int to(g[v][i]);
    if (to == p) { continue; }
    if (used[to]) {
       fup[v] = min(fup[v], tin[to]);
    } else {
       st.push(Frame(to, v, 0));
    }
    st.push(Frame(v, p, i + 1));
  } while (!st.empty());
}

这篇关于在图中查找桥梁而无需递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！