我们怎样才能找到初始节点，以应用的算法？ [英] How can we find the initial node in order to apply the algorithm?

问题描述

考虑以下图G，并认为在该算法的DFS在G的执行中，图的边缘被表征为树边缘（吨），后边缘（b）中，前边缘（f）和横边（ c）于下图。对于图中的每个节点找到发现时间和节点的完成时间。 换句话说，对于图中的每个节点U中，找到值D [v]的和f [v]的相关联的算法的DFS与此节点

Consider the following graph G and consider that at an execution of the algorithm DFS at G, the edges of the graph are characterized as tree edges(t), back edges(b) , forward edges(f) and cross edges(c) as at the following graph. For each node of the graph find the discovery time and the finishing time of the node. In other words, for each node v of the graph, find the values d[v] and f[v] that associates the algorithm DFS with this node.

请注意，是值只有一个可能的分配D [V]和f [V]。

Notice that there is only one possible assignment of the values d[v] and f[v].

你能不能给我一个提示，我们如何才能找到初始节点，以开始应用深度优先搜索算法？

Could you give me a hint how we can find the initial node in order to start applying the Depth first search algorithm?

推荐答案

看着节点 A - 这可能DFS做节点 A ？它可能会有两种结果为 B 或电子。我们看到，它选择了 B ，因为 A-＆GT; b 是一棵树边， A-＆GT; e 是一个前缘（检查树/前缘的定义）。在 B 唯一的选择是访问 F 。在 F DFS可能会有两种结果为 A ，电子或先按g 。我们可以假设，它试图访问 A （ F-＆gt;在标记为后缘，所以一切都是正确的到现在为止），比它访问电子，比试图访问 B 。但是，现在我们有优势 F-＆GT的一个问题克。它被标记为一个交叉的边缘，这意味着DFS已经访问了先按g 之前。否则，这一优势将被标记为树边。所以，我们知道， A 未在初始节点。我们需要尝试其他选择。那么 C ？同样，所有的边缘走出来的 C 被标记为横，而不是树，那么 C 不是初始节点

Look at node a - what could DFS do in node a? It could go either to b or e. We see that it chose b, because a->b is a tree edge and a->e is a forward edge (check the definition of tree/forward edge). In b the only choice was to visit f. In f DFS could go either to a, e or g. We can assume that it tried to visit a (f->a is marked as back edge, so everything is correct until now), than it visited e and than tried to visit b. However, we now have a problem with edge f->g. It is marked as a cross edge, which means that DFS had already visited g before. Otherwise, this edge would have been marked as a tree edge. So, we know that a was not the initial node. We need to try other options. What about c? Again, all of edges coming out of c are marked as cross, not tree, so c was not the initial node.

什么 D ？如果DFS开始在 D ，它可以去从 D 到先按g ，这就是所发生的事情，因为 D-＆GT克标记为树边。有没有节点从先按g 去，因此backtraced到 D ，并参观了 ^ h 。从 ^ h 它试图访问先按g ，但它已经浏览过，所以 H-＆GT克标记为十字 - 正确的。大，所以 D 是本次DFS执行初始节点。访问包含 D 连接组件后，先按g 和 ^ h ，DFS可以重新开始或者从 A 或 C ，但我们已经知道，它并没有从<$ C开始$因为这些交叉的边缘了C> C 。因此，它从开始 A 和参观后 B ， F 和电子从开始ç。

What about d? If DFS started in d, it could go from d to g and that's what happened because d->g is marked as tree edge. There were no nodes to go from g so it backtraced to d and visited h. From h it tried to visit g but it has already visited earlier, so h->g is marked as cross - correct. Great, so d was the initial node for this DFS execution. After visiting a connected component which contains d, g and h, DFS could start again either from a or c but we already know that it has not started from c because of those cross edges. So it started from a and after visiting b, f and e it started from c.

这篇关于我们怎样才能找到初始节点，以应用的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！