天天看点

图的DFS和BFS(邻接表)

  图的储存方式有邻接矩阵和邻接表储存两种。由于邻接表的实现需要用到抽象数据结构里的链表,故稍微麻烦一些。C++自带的STL可以方便的实现List,使算法的实现变得简单起来

图的DFS和BFS(邻接表)

  为了让我们的算法更有普适性,我们将非连通图也考虑在内。其实,要想遍历到类似于图中5,6节点这种孤岛节点,只需要依次按编号遍历顺序所有节点,如果某节点没有访问(book数组标记值为0),则从该节点开始深度优先搜索或广度优先搜索;等一次深搜或广搜完毕后,继续依次按照编号顺序遍历节点,选择从一个没访问过的结点开始再次深搜或广搜。。。如此知道把所有节点都遍历完。

1.图抽象数据类型的声明,除了构造函数和析构函数之外,提供3个对外接口,分别实现递归DFS,BFS和非递归DFS(用STL栈实现)

2.图的构造函数和析构函数实现

3.图的递归DFS调用接口及其实现函数

4.图的BFS调用接口及其实现函数

5.图的非递归DFS及其实现函数

6.主函数测试(注意,每次遍历后要把标记数组初始化为0)

数学是符号的艺术,音乐是上界的语言。