关于数据结构题目理解的一点疑问

蓝色魅影 · 发表于 2020-4-20 17:15

本帖最后由蓝色魅影于 2020-4-20 18:27 编辑

原题：基于深度优先搜索，判断一个无向图是否为一棵树
我的疑问是：如果只是判断一个无向图是否为二叉树，那么判断无向图边数是否为顶点数减一就行了。那我完全可以直接通过算邻接矩阵中1的个数除以2然后和顶点个数n-1进行比较，完全没必要用到深度优先搜索吧，是我的理解有问题吗？有大佬能解答下吗

庸人误我 · 发表于 2020-4-20 17:39

没毛病，一道题有多种解法。

职业僚机 · 发表于 2020-4-20 17:40

如果有环的话这种办法就不可行了

蓝色魅影 · 发表于 2020-4-20 17:43

职业僚机发表于 2020-4-20 17:40
如果有环的话这种办法就不可行了

有环也可以吧，有环的话边数就无法满足n-1，所以就不是树啊。。

帐号		自动登录	找回密码
密码			注册[Register]

[已解决] 关于数据结构题目理解的一点疑问