P105. 图的深拷贝

https://algocasts.io/episodes/XZWvPNG7

为什么在这题一定要先验证一个元素是否在map里,才把它加进node.neighbors呢?
能不能解释一下这样做的必要性?
谢谢

@Yifu_Chen

map 里存储的对应关系是原图的 node 和复制的 node,如果某个 node 不在 map 中,说明这个 node 还没处理过,也即还未对这个 node 进行复制,自然是拿不出拷贝的 node 加到拷贝图里的。所以要先递归去处理这个未处理过的 node。

你可以再看一下视频中的讲解部分,对这一点是有反复讲到的。

1赞

老师,想请教一个测试的时候触发的问题。

我参考你的代码的时候发现无向图节点类没有定义 hashCodeequals 方法,因为 IDEA 会提示 Critical,所以我就用它自动补上了。

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof UndirectedGraphNode)) {
            return false;
        }
        UndirectedGraphNode that = (UndirectedGraphNode) o;
        return val == that.val && neighbors.equals(that.neighbors);
    }

    @Override
    public int hashCode() {
        return Objects.hash(val, neighbors);
    }

结果发现这样是会导致 StackOverflow 的(反复调用 hashCode 方法),应该怎样解决呢?

我也不确定是不是递归定义数据结构的问题,因为之前写树相关的问题(也加上了 hashCodeequals 方法)的时候就没有出现。


这个问题我以前在实际项目中也遇到过:虽然那次没有写递归方法,但也是用了递归定义的类解决类似人物关系模型的问题,那次是利用 Lombok 注解代替 hashCodeequals 方法,也是同样的结果(当时不确定怎样解决、我就绕过了…= =)。

@yipwinghong

同学,你为一个无向图这么实现 hashCode 是会死循环的。。。导致问题的关键并不在于是否递归定义数据结构,而在于这个数据结构是不是有环的。 树也好,无环链表也好, Objects.hash 中会不断递归调用成员变量的 hashCode 函数,但它们总是会有结束的时候。树是到达叶子节点,而链表是到达 null,因此调用可以停下。但这个题目中是一个无向图,你这么做就会在节点之间无限地调用 hashCode。

这个题目中,hashCode 和 equals 用默认的就可以。

好的,我明白了,谢谢~