文献求助 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

文献求助

文献求助# Biology - 生物学

c*e2016-04-25 07:04

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.

r*e2016-04-25 07:04

2 楼

http://www.ncbi.nlm.nih.gov/pubmed/24341493
Bioanalysis. 2014 Jan;6(1):33-42. doi: 10.4155/bio.13.280.
An ultrasensitive method for the quantitation of active and inactive GLP-1
in human plasma via immunoaffinity LC-MS/MS.
请e-mail到[email protected]/* */
谢谢。

q*x2016-04-25 07:04

3 楼

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.

i*a2016-04-25 07:04

4 楼

https://www.sendspace.com/file/7jqy46

c*e2016-04-25 07:04

5 楼

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*l2016-04-25 07:04

6 楼

这个问题很奇怪呀
都用stack了，显然是pop的顺序啊
要是push就用queue了吧

each node is pushed into the stack, or the order each node is popped from
the stack.

【在 c**********e 的大作中提到】

r*t2016-04-25 07:04

7 楼

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*x2016-04-25 07:04

8 楼

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*t2016-04-25 07:04

9 楼

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*e2016-04-25 07:04

10 楼

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*x2016-04-25 07:04

11 楼

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.