判断题
若从v0开始对有向图g进行深度遍历序列唯一,则可唯一确定该图。( )【北京邮电大学2006二、6(1分)】
【正确答案】
错误
【答案解析】解析:对一个逻辑图进行深度/广度优先遍历,其遍历序列一般是不唯一的,因为没确定存储结构。即使给出存储结构,若没说明邻接点的排列规则,遍历序列也不唯一。因为第一邻接点的确定以及下一邻接点的确定并没说明。本题的错误在于没说明进入dfs的次数。例如,若vx和v0没路径,vx可能是孤立顶点,也可能有弧指向遍历序列上某顶点,从v0开始的深度遍历序列都是相同的,但不能唯一确定该图。