首页 > 代码库 > dfs手写栈模板
dfs手写栈模板
在竞赛中如果系统栈很小的话，过深的递归会让栈溢出，这个时候我们就要自己手写栈，将递归转化成手工栈。
方法其实也很简单。
基本思路上，我们就是用栈不断的pop,push。但是何时push，何时pop呢？
在《算法导论》上对深度优先遍历树的讲解中，在深度遍历中，会对每个节点进行染色，白色为没有被访问过；灰色为被访问过，但是该节点的所有子树还没有完成访问；黑色，节点被访问过，而且该节点的所有子树都被完全的访问。
所以，我们就通过颜色标记来进行判断了。
整体的框架如下：
memset(vis,0,sizeof(vis));stack S;S.push(root)while(!S.empty()){ int u = S.top(); if(vis[u] == 1)// if node is gray, then color black { vis[u] = 2; // do things after dfs children. S.pop(); } else if(vis[u] == 0)// if node is white, then color gray { vis[u] = 1; // do things before dfs children. for all children v S.push(v); }}
dfs手写栈模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。