我正在学习图形和DFS,并试图做一些类似于ANT如何解决依赖关系的事情 . 我对某些事感到困惑,我读到的所有文章似乎都假设每个人都知道这一点 .
我正在考虑使用Map> with key = file,以及value =密钥所依赖的文件集 .
DFS算法显示我必须更改节点的颜色(如果它已经被访问过),这意味着对于同一个文件节点的引用必须在密钥中的一个和Set <>中的那个之间相同吗?
因此,我在想,每次创建一个Node(包括邻居节点),我会将它添加到另一个Collection(可能是另一个Map?),然后每当一个新的Node添加到图形中时(作为键) ,搜索该集合并使用该引用代替?我在浪费太多空间吗?通常怎么做?还有其他更好的方法吗?
1 回答
在我学习期间,DFS算法实现如下:
将图形的所有节点放入堆栈(这是一种结构,您只能检索和删除第一个元素) .
检索第一个元素,将其设置为可见,这可以通过着色或通过设置属性来完成,我们将其称为isSeen,为true .
然后,您查看该节点的所有邻居,如果它们尚未被看到,则将它们放入堆栈中 .
一旦查看了所有邻居,就从堆栈中删除节点并检索堆栈的下一个元素并执行与第一个相同的操作 .
结果是,可以从起始节点到达的所有节点将具有设置为可见的属性 .
希望这有帮助 .