专注细节
努力进步

图的两种遍历算法

图的两种遍历算法

1,深度遍历

1) 访问节点v,并标记为已访问 2)查找节点v的第一个邻接节点w; 3)若w存在,则继续执行,不存在则算法结束 4)若w尚未被访问,则递归访问节点w 5)若w标记为已访问,则查找v的w邻接节点的下一个节点,并赋给w,赚到步骤3

2,广度优先遍历

1)访问初始节点v并标记节点v为已访问 2)节点v进队列 3)当队列为非NULL时继续执行,否则算法结束 4)出队列得到对头节点u 5)查找节点u的第一个临界点w 6)如节点u的第一个临界点w不存在,则转到步骤3,否则循环下列步骤 6.1)若节点w尚未被访问,则访问节点w并标记为已访问,入队列 6.2)查找节点u的w邻接节点的下一个邻接节点w,转到步骤(6)

代码见图的两种遍历方法实现

分享到:更多 ()