c**********e
发帖数: 2007 | 1 In the following graph, with starting point 0, what is the order of DFS
traversal?
0
/ \
1 2
/
3
We use a stack for DFS visit. The problem is, is the visit order the order each node is pushed into the stack, or the order each node is popped from the stack. |
q****x
发帖数: 7404 | 2 dfs is post-order.
each node is pushed into the stack, or the order each node is popped from
the stack.
【在 c**********e 的大作中提到】
: In the following graph, with starting point 0, what is the order of DFS
: traversal?
: 0
: / \
: 1 2
: /
: 3
: We use a stack for DFS visit. The problem is, is the visit order the order each node is pushed into the stack, or the order each node is popped from the stack.
|
c**********e
发帖数: 2007 | 3 Are you sure? A professor says the answer is 0213 or 0132.
【在 q****x 的大作中提到】
: dfs is post-order.
:
: each node is pushed into the stack, or the order each node is popped from
: the stack.
|
P**l
发帖数: 3722 | 4 这个问题很奇怪呀
都用stack了，显然是pop的顺序啊
要是push就用queue了吧
each node is pushed into the stack, or the order each node is popped from
the stack.
【在 c**********e 的大作中提到】
: In the following graph, with starting point 0, what is the order of DFS
: traversal?
: 0
: / \
: 1 2
: /
: 3
: We use a stack for DFS visit. The problem is, is the visit order the order each node is pushed into the stack, or the order each node is popped from the stack.
|
r****t
发帖数: 10904 | 5 Seriously? I thought only pre-order visits nodes in the same order as dfs,
although all three traversal can be implemented using dfs.
【在 q****x 的大作中提到】
: dfs is post-order.
:
: each node is pushed into the stack, or the order each node is popped from
: the stack.
|
q****x
发帖数: 7404 | 6 look at clrs graph dfs algorithm. it's post-order. parent node is colored
after children nodes.
【在 r****t 的大作中提到】
: Seriously? I thought only pre-order visits nodes in the same order as dfs,
: although all three traversal can be implemented using dfs.
|
r****t
发帖数: 10904 | 7 Fig 22.4?
grey = discovered
black = finished
If visiting is defined as finished, then yes it is post-order;
if visiting is defined as discovered, then it is pre-order.
【在 q****x 的大作中提到】
: look at clrs graph dfs algorithm. it's post-order. parent node is colored
: after children nodes.
|
c**********e
发帖数: 2007 | 8 Did you intend to post an attachment?
【在 r****t 的大作中提到】
: Fig 22.4?
: grey = discovered
: black = finished
: If visiting is defined as finished, then yes it is post-order;
: if visiting is defined as discovered, then it is pre-order.
|
q****x
发帖数: 7404 | 9 every type of traversal needs to discover root b/4 children.
【在 r****t 的大作中提到】
: Fig 22.4?
: grey = discovered
: black = finished
: If visiting is defined as finished, then yes it is post-order;
: if visiting is defined as discovered, then it is pre-order.
|
