Finding bridges in graph without recursion

Question

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);
        }
    }
}

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?

Answer 1

Sorry for the late reply.

Change code of previous answer and now it works fine. Tested in contest task to find all bridges in connected Graph. Hope it will help you.

// Copyright 2020 Kondratenko Evgeny
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>


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


void DFS(int n,
        const std::vector<std::vector<int>> &G,
        const std::vector<std::vector<int>> &weights) {
    std::vector<bool> used(n + 1, false);
    std::vector<int> ret(n + 1);  // the same as tup
    std::vector<int> enter(n + 1);  // the same as tin
    std::stack<Frame> s;
    s.push(Frame(1, -1, 0));
    int time = 1;
    while (!s.empty()) {
        Frame f = s.top();
        s.pop();
        int v = f.v;
        int p = f.p;
        int i = f.i;
        if (i == 0) {
            enter[v] = ret[v] = time++;
            used[v] = true;
        }
        // First part works befor DFS call
        if (i < G[v].size()) {
            int to = G[v][i];
            s.push(Frame(v, p, i + 1));
            if (to != p) {
                if (used[to]) {
                    ret[v] = std::min(ret[v], enter[to]);
                } else {
                    s.push(Frame(to, v, 0));
                }
            }
        }
        /*
            Generally here is virtual DFS recursive call, which we are simulate now
        */
        // Second part after DFS call
        if (i > 0 && i <= G[v].size()) {
            int to = G[v][i - 1];
            if (to != p) {
                ret[v] = std::min(ret[v], ret[to]);
                if (ret[to] > enter[v]) {
                    std::cout << "bridge between: " << v << " and " << to;
                    std::cout << ", with weight: " << weights[v][i - 1] << std::endl;
                }
            }
        }
    }
}


int main() {
    int n, m;  // n - number of vertex, m - number of edges
    std::cin >> n >> m;
    std::vector<std::vector<int>> G(n + 1, std::vector<int>());  // your Graph
    std::vector<std::vector<int>> weights(n + 1, std::vector<int>());
    for (int i = 0; i < m; ++i) {  // read edges with weigths
        int u, v, w;
        std::cin >> u >> v >> w;
        G[u].push_back(v);
        G[v].push_back(u);
        weights[u].push_back(w);
        weights[v].push_back(w);
    }
    DFS(n, G, weights);
    return 0;
}

Answer 2

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

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());
}