gpt4 book ai didi

java - 生成 BFS 图森林

转载 作者:行者123 更新时间:2023-12-01 16:02:20 24 4
gpt4 key购买 nike

我想生成 DAG(直接无环图)的 BFS 森林。这意味着我的 Tree 类需要是普通树而不是二叉树(换句话说,当我生成森林时,我无法提前知道节点将拥有的子节点数量)。大部分代码都写在下面并显示在下面,但是我缺少一行,但我一生都没有注意到!

public Tree BFS(V start)
{
reset();
LinkedList<GraphMatrixVertex<V>> list = new LinkedList<GraphMatrixVertex<V>>();
GraphMatrixVertex<V> vert = dict.get(start);
Tree root = new Tree(vert);
list.add(vert);
do
{
vert = list.getFirst();
Iterator<V> ni = neighbors(start);
while(ni.hasNext())
{
V v = ni.next();
GraphMatrixVertex<V> vtx = dict.get(v);
if(!vtx.isVisited())
{
list.add(vtx);
vtx.visit();
root.addChild(new Tree(vtx));
}
}
//code goes here
}
while(!list.isEmpty());

return root;
}

我的 Tree 类存储一个值参数、一个父引用和一个子列表。我的问题是引用下一个树节点。一旦我将所有未访问的邻居添加为当前节点的子节点,我如何到达下一个节点?

编辑:

所以它看起来像这样?

public void bfs(Tree parent)
{
Iterator<V> ni = neighbors((V) parent.value());
if(ni.hasNext())
{
while(ni.hasNext())
{
V next = ni.next();
GraphMatrixVertex<V> vert = dict.get(next);
if(!vert.isVisited())
parent.addChild(new Tree(next));
}
}
}

递归调用去哪里了?

最佳答案

如果我正确理解你的问题,你可以使用递归来解决这个问题。基本上,您有一个函数可以创建一层节点,然后为您想要创建/访问的每个子节点再次调用自身。

编辑:

好的,我稍微编辑了你的代码。首先,我删除了 if(hasNext) ,因为它与其中的 while 循环是多余的。对于邻居列表上的每个子节点,您创建一个新的树节点,然后运行其 bfs() 方法,传递当前的 Tree 对象。该函数返回一个列表,该列表应该是穿过树的最佳路径。我也不确定你获取相邻节点的方式,它看起来有点奇怪。我也没有测试过代码,所以其中可能存在拼写错误和其他内容,但希望它能让您了解如何进行搜索。哦,当您命中叶节点(您的目标?)时,它将需要设置其权重并返回一个仅包含其自身的新列表。

int weight; // this should be you node traversal cost

public LinkedList<Tree> bfs(Tree parent){

Iterator<V> ni = neighbors((V) parent.value());

LinkedList bestPath = null;
int bestScore = 0xFFFFFFFF;

while(ni.hasNext()){
V next = ni.next();
GraphMatrixVertex<V> vert = dict.get(next);
if(!vert.isVisited()){
Tree newNode = new Tree(next);
parent.addChild(newNode);
LinkedList path = newNode.bfs(this);
if(newNode.weight < bestScore){
bestScore = weight;
bestPath = path;
}
}
}
weight = bestScore + this.weight;
bestPath.addFirst(this);
return path;
}

编辑2:

public void bfs(Tree parent){

Iterator<V> ni = neighbors((V) parent.value());

while(ni.hasNext()){
V next = ni.next();
GraphMatrixVertex<V> vert = dict.get(next);
if(!vert.isVisited()){
Tree newNode = new Tree(next);
parent.addChild(newNode);
newNode.bfs(this);
}
}
}

关于java - 生成 BFS 图森林,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3509783/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com