温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C++的DFS和BFS怎么实现

发布时间:2021-11-30 16:00:47 来源:亿速云 阅读:175 作者:iii 栏目:编程语言

这篇文章主要讲解了“C++的DFS和BFS怎么实现”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C++的DFS和BFS怎么实现”吧!

DFS和BFS

对于非线性的结构,遍历都会首先成为一个问题。和二叉树的遍历一样,图也有深度优先搜索(DFS)和广度优先搜索(BFS)两种。不同的是,图中每个顶点没有了祖先和子孙的关系,因此,前序、中序、后序不再有意义了。仿照二叉树的遍历,很容易就能完成DFS和BFS,只是要注意图中可能有回路,因此,必须对访问过的顶点做标记。

最基本的有向带权网

#ifndef Graph_H   #define Graph_H    #include    #include    using namespace std;   #include "Graphmem.h"    template <class name, class dist, class mem>   class Network   {   public:   Network() {}   Network(dist maxdist) { data.NoEdge = maxdist; }   ~Network() {}   bool insertV(name v) { return data.insertV(v); }   bool insertE(name v1, name v2, dist cost) { return data.insertE(v1, v2, cost); }   name& getV(int n) { return data.getV(n); }   int nextV(int m, int n = -1) { return data.nextV(m, n); }   int vNum() { return data.vNum; }   int eNum() { return data.eNum; }   protected:   bool* visited;   static void print(name v) { cout << v; }   private:   mem data;   };   #endif

你可以看到,这是在以mem方式储存的data上面加了一层外壳。在图这里,逻辑上分有向、无向,带权、不带权;储存结构上有邻接矩阵和邻接表。也就是说分开来有8个类。为了***限度的复用代码,继承关系就非常复杂了。但是,多重继承是件很讨厌的事,什么覆盖啊,还有什么虚拟继承,我可不想花大量篇幅讲语言特性。于是,我将储存方式作为第三个模板参数,这样一来就省得涉及虚拟继承了,只是这样一来这个Network的实例化就很麻烦了,不过这可以通过typedef或者外壳类来解决,我就不写了。反正只是为了让大家明白,真正要用的时候,***是写专门的类,比如无向无权邻接矩阵图,不要搞的继承关系乱七八糟。

DFS和BFS的实现

public:   void DFS(void(*visit)(name v) = print)   {   visited = new bool[vNum()];   for (int i = 0; i < vNum(); i++) visited[i] = false;   DFS(0, visit);   delete []visited;   }   protected:   void DFS(int i, void(*visit)(name v) = print)   {   visit(getV(i)); visited[i] = true;   for (int n = nextV(i); n != -1; n = nextV(i, n))   if (!visited[n]) DFS(n, visit);   }   public:   void BFS(int i = 0, void(*visit)(name v) = print)//n没有越界检查   {   visited = new bool[vNum()]; queue<int> a; int n;   for (n = 0; n < vNum(); n++) visited[n] = false;   visited[i] = true;   while (i != -1)//这个判断可能是无用的   {   visit(getV(i));   for (n = nextV(i); n != -1; n = nextV(i, n))   if (!visited[n]) { a.push(n); visited[n] = true; }   if (a.empty()) break;   i = a.front(); a.pop();   }   delete []visited;   }

DFS和BFS函数很难写得像树的遍历方法那么通用,这在后面就会看到,虽然我们使用了DFS和BFS的思想,但是上面的函数却不能直接使用。因为树的信息主要在节点上,而图的边上还有信息。

测试程序

#include    using namespace std;   #include "Graph.h"   int main()   {   Network<char, int, LinkedList<char, int> > a;   a.insertV('A'); a.insertV('B');   a.insertV('C'); a.insertV('D');   a.insertE('A', 'B', 1); a.insertE('A', 'C', 2);   a.insertE('B', 'D', 3);   cout << "DFS: "; a.DFS(); cout << endl;   cout << "BFS: "; a.BFS(); cout << endl;   return 0;   }

感谢各位的阅读,以上就是“C++的DFS和BFS怎么实现”的内容了,经过本文的学习后,相信大家对C++的DFS和BFS怎么实现这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI