图的遍历,深度和广度优先遍历

图的遍历,从图中某一顶点出发遍历图中其余的顶点,且使每一个顶点仅被访问一次。图的遍历算法是求解图的连通性问题,拓扑排序和求关键路径等算法的基础。(了解)

通常图的遍历路径有两种。深度优先搜索和广度优先搜索。他们对无向图和有向图都适用。

深度优先遍历类似树的先序遍历。

广度优先遍历类似树的层次遍历 。

不过这个题目要注意下了,字母排在前面的先遍历,

深度A->B->D->G->E->C->F->H,广度A->B->C->H->D->E->F->G 。过程用文字描述即可。

要始终注意一点,如果题目没给先遍历排在前面的字母这一条件,答案不唯一,但是给了,一定唯一。(作为考试的话一般都会给)

赞赏

微信赞赏支付宝赞赏

发表评论