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

为了让我们的算法更有普适性,我们将非连通图也考虑在内。其实,要想遍历到类似于图中5,6节点这种孤岛节点,只需要依次按编号遍历顺序所有节点,如果某节点没有访问(book数组标记值为0),则从该节点开始深度优先搜索或广度优先搜索;等一次深搜或广搜完毕后,继续依次按照编号顺序遍历节点,选择从一个没访问过的结点开始再次深搜或广搜。。。如此知道把所有节点都遍历完。
1.图抽象数据类型的声明,除了构造函数和析构函数之外,提供3个对外接口,分别实现递归DFS,BFS和非递归DFS(用STL栈实现)
2.图的构造函数和析构函数实现
3.图的递归DFS调用接口及其实现函数
4.图的BFS调用接口及其实现函数
5.图的非递归DFS及其实现函数
6.主函数测试(注意,每次遍历后要把标记数组初始化为0)
数学是符号的艺术,音乐是上界的语言。