时间戳

首页 > 解决方案 > 正确实施以在图中找到桥

java - 正确实施以在图中找到桥

问题描述

我有以下实现来在图中找到切边/桥：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class TarjanCutEdge {

    public static void main(String[] args) {
        Graph g = new Graph(8);
        g.addEdge(0,1);
        g.addEdge(1,2);
        g.addEdge(2,0);
        g.addEdge(2,3);
        g.addEdge(3,4);
        g.addEdge(4,5);
        g.addEdge(5,6);
        g.addEdge(6,4);
        g.addEdge(6,7);
        g.addEdge(4,7);
        List<Pair<Integer,Integer>> result = new LinkedList<>();
        getCutEdges(g,result);
        System.out.println(result);
    }

    private static void getCutEdges(Graph g, List<Pair<Integer, Integer>> result) {

        int[] disc = new int[g.getNumVertices()];
        int[] low = new int[g.getNumVertices()];
        int[] parent = new int[g.getNumVertices()];
        Arrays.fill(disc,-1);
        Arrays.fill(low,-1);
        Arrays.fill(parent,-1);

        for(int i=0;i<g.getNumVertices();i++){
            if(disc[i] == -1) // unvisited
                dfs(i,g,disc,low,parent,result,0);
        }
    }

    private static void dfs(int u, Graph g, int[] disc, int[] low, int[] parent,
                            List<Pair<Integer, Integer>> result,int time) {
        disc[u] = low[u] = time;
        time++;
        for(int v : g.getVertices(u)){
            if(disc[v] == -1){
                parent[v] = u;
                dfs(v,g,disc,low,parent,result,time);
                low[u] = Math.min(low[u],low[v]);
                if(low[v] > low[u]){ // no back edge present
                    result.add(new Pair<>(u,v));
                }
            }else if(v != parent[u]){ // ignore child to parent edge
                low[u] = Math.min(low[u],disc[v]);
            }
        }
    } 
}

该实现适用于大多数测试用例，除了一个。一个测试用例有 1000 个节点和约 56k 条边。我正在尝试解决这个问题 - https://leetcode.com/problems/critical-connections-in-a-network/

如何验证是错误的代码还是测试用例？

如果您已经知道 Tarjan 算法，请查看代码。

标签： javagraphdepth-first-searchtarjans-algorithm

解决方案

这是一个编码错误，对于要成为桥的边缘，我们必须检查邻居的低位以发现当前节点（因为我们必须检查当前节点 'u' 的邻居 'v' 是否有任何向后边缘'u' 的祖先，就好像存在向后那样，如果删除了 'u'-'v' 之间的边，则图形仍将连接）：

if(low[v] > disc[u]){ // no back edge present
   result.add(new Pair<>(u,v));
}

推荐阅读