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?

You haven't added a language tag to your question. You code is in C (it uses `size_t`). Are you only interested in answers in C or also in other languages? — Erwin Bolwidt, Apr 20 '14 at 09:11
@ErwinBolwidt `g[v].size()` this is not C, C++ perhaps. Generally a question that is tagged algorithm can be answered in a pseudo-code as well. — amit, Apr 20 '14 at 09:17
[size_t is C and C++](http://stackoverflow.com/questions/2550774/what-is-size-t-in-c) but there's nothing else in there that suggests C++. I asked my comment to the OP, as people are answering in Java and it's not clear how useful that is to the OP. — Erwin Bolwidt, Apr 20 '14 at 09:22

score 5 · Accepted Answer · answered Apr 20 '14 at 13:36

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

score 3 · Answer 2 · answered May 06 '20 at 21:12

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

This works, thank you. Any sources which explain how the stacking works in more detail? I searched for "bridges in a graph without recursion" but this question is all I can find. — Mayur, Jan 10 '21 at 07:18
@Mayur, you are welcome https://cp-algorithms.com/graph/bridge-searching.html — Evgeny, Jan 11 '21 at 04:42
Thank you. Yes, I'm aware of the bridge finding algorithm. I was looking for an explanation of the stacking behaviour. Did you come up with that yourself? — Mayur, Jan 11 '21 at 05:27

Finding bridges in graph without recursion

2 Answers2

Linked