y*******g
发帖数: 6599 | 1 att
CLRS上用grey 表示第一次发现node, black表示finish
在递归的时候很明确，但用stack的话怎么区分 grey/black? |
s****j
发帖数: 67 | 2 第一次发现应该是push的时候，第一次处理是pop，但处理不代表该节点finish了
感觉可以通过stack的size来判断
【在 y*******g 的大作中提到】
: att
: CLRS上用grey 表示第一次发现node, black表示finish
: 在递归的时候很明确，但用stack的话怎么区分 grey/black?
|
s****j
发帖数: 67 | 3 如果当前stack的size小于某个node push进stack时候的size，那么表示这个node
finish了
correct me if im wrong |
y*******g
发帖数: 6599 | 4 给个code?
哪什么时候pop啊？
一般的写法是
while(!stack.empty()) {
Node current = stack.top();
stack.pop();
//push all edge
}
但pop之后就没法在访问了吧
【在 s****j 的大作中提到】
: 第一次发现应该是push的时候，第一次处理是pop，但处理不代表该节点finish了
: 感觉可以通过stack的size来判断
|
s****j
发帖数: 67 | 5 粗略想法：
再开一个stack
while (!stack.empty()) {
Node current=stack.top();
stack.pop();
//color current to grey
current->pos=stack.size(); // anyway, record current stack size
stack2.push(current);
//push all edge
while (!stack2.empty() && stack2.top()->pos==stack.size()) {
Node t=stack2.top();
//color t to black
stack2.pop();
}
}
【在 y*******g 的大作中提到】
: 给个code?
: 哪什么时候pop啊？
: 一般的写法是
: while(!stack.empty()) {
: Node current = stack.top();
: stack.pop();
: //push all edge
: }
: 但pop之后就没法在访问了吧
|
c******o
发帖数: 534 | 6 不明白，用stack进行DFS为什么要color node？
color node用来做什么？ |
y*******g
发帖数: 6599 | 7 判断edge的种类啊，tree/back/forward or crossing/
不color怎么做到？
【在 c******o 的大作中提到】
: 不明白，用stack进行DFS为什么要color node？
: color node用来做什么？
|
y*******g
发帖数: 6599 | 8 怎么push?是进第一个还是第二个stack? 感觉要不停的开stack，，也就是递归了
【在 s****j 的大作中提到】
: 粗略想法：
: 再开一个stack
: while (!stack.empty()) {
: Node current=stack.top();
: stack.pop();
: //color current to grey
: current->pos=stack.size(); // anyway, record current stack size
: stack2.push(current);
: //push all edge
: while (!stack2.empty() && stack2.top()->pos==stack.size()) {
|
s****j
发帖数: 67 | 9 我觉得code已经写得比较清楚了。。。
就两个stack
一个是原stack，里面是待扩展的node
一个只记录处理过的node，用于color black
【在 y*******g 的大作中提到】
: 怎么push?是进第一个还是第二个stack? 感觉要不停的开stack，，也就是递归了
|
y*******g
发帖数: 6599 | 10 好像明白了一些，我写完整了再看看
多谢
【在 s****j 的大作中提到】
: 我觉得code已经写得比较清楚了。。。
: 就两个stack
: 一个是原stack，里面是待扩展的node
: 一个只记录处理过的node，用于color black
|
|
|
B*******1
发帖数: 2454 | 11 为什么一定要用stack，不用递归呢？
【在 y*******g 的大作中提到】
: 判断edge的种类啊，tree/back/forward or crossing/
: 不color怎么做到？
|
y*******g
发帖数: 6599 | 12 递归太深会overflow啊
【在 B*******1 的大作中提到】
: 为什么一定要用stack，不用递归呢？
|
B*******1
发帖数: 2454 | |
y*******g
发帖数: 6599 | 14 面试可以直接要求不许递归
【在 B*******1 的大作中提到】
: 一般面试不会这么深吧？
|
c****p
发帖数: 6474 | 15 edge种类可以通过discover time和finish time确定吧。
【在 y*******g 的大作中提到】
: 判断edge的种类啊，tree/back/forward or crossing/
: 不color怎么做到？
|
B*******1
发帖数: 2454 | 16 但是存颜色跟存这个time其实问题是一样的吧。
【在 c****p 的大作中提到】
: edge种类可以通过discover time和finish time确定吧。
|
c****p
发帖数: 6474 | 17 嗯。。。也对。。
【在 B*******1 的大作中提到】
: 但是存颜色跟存这个time其实问题是一样的吧。
|
e***l
发帖数: 710 | 18 直接用一个额外的数组（或者node对象的一个分量）记录颜色，颜色标记的顺序应该和
递归的方法相同：
所有node标白色;
root标灰色并入栈;
while(栈非空){
取得栈顶元素,//必为灰色
找到它第一个白色的邻接node,将其标灰并入栈, //注1
如果没有找到白色邻接node，将栈顶元素标黑并出栈。//所有邻接node已发现
}
注1：可以对每个node记录“已经访问到了第几个邻接node”,避免每次从头搜索 |
