Mosty na połączonym wykresie
Mam zadanie programistyczne (nie zadanie domowe), w którym muszę znaleźć mosty na wykresie. Sam pracowałem nad tym trochę, ale nie mogłem wymyślić nic satysfakcjonującego. Więc googlałem go, znalazłem coś, ale nie jestem w stanie zrozumieć algorytmu, tak jak jest przedstawiony. Czy ktoś mógłby spojrzeć na ten kod i dać mi wyjaśnienie?
public Bridge(Graph G) {
low = new int[G.V()];
pre = new int[G.V()];
for (int v = 0; v < G.V(); v++) low[v] = -1;
for (int v = 0; v < G.V(); v++) pre[v] = -1;
for (int v = 0; v < G.V(); v++)
if (pre[v] == -1)
dfs(G, v, v);
}
public int components() { return bridges + 1; }
private void dfs(Graph G, int u, int v) {
pre[v] = cnt++;
low[v] = pre[v];
for (int w : G.adj(v)) {
if (pre[w] == -1) {
dfs(G, v, w);
low[v] = Math.min(low[v], low[w]);
if (low[w] == pre[w]) {
StdOut.println(v + "-" + w + " is a bridge");
bridges++;
}
}
// update low number - ignore reverse of edge leading to v
else if (w != u)
low[v] = Math.min(low[v], pre[w]);
}
}