我正在试着写一个使用Kahn算法的程序,有点像BFS。由于队列和列表中有确切的键被放入,有没有办法删除队列并使列表像队列一样执行,并且仍然返回值?我被告知要保留列表的首选项,而不是像队列那样删除键。不过,我不知道该怎么做。任何建议都是值得感谢的。这是我程序的一部分。
private static List<Job> topologicalSortBFS(final List<Job> jobs) //Kahn's
{
final List<Job> sorted = new ArrayList<>(jobs.size());
final Map<Job, Integer> inCount = new HashMap<>(jobs.size());
final Queue<Job> queue = new ArrayDeque<>();
for (final Job j : jobs)
{
/* Associate every node with the amount of nodes it requires. */
final int in = j.inbound.size();
inCount.put(j, in);
/* If the node requires nothing, then add to queue and sorted list. */
if (in == 0)
{
sorted.add(j);
queue.add(j);
}
}
while (!queue.isEmpty())
{
final Job current = queue.poll(); // poll = pop
for (final Job neighbor : current.outbound)
{
/* Remove an outgoing connection without modifying the node. */
final int updatedIncount = inCount.get(neighbor) - 1;
inCount.put(neighbor, updatedIncount);
/* If node is now considered a leaf, its requirements were met. */
if (updatedIncount == 0)
{
sorted.add(neighbor);
queue.add(neighbor);
}
}
}
return sorted;
}
发布于 2018-04-14 13:16:18
在给定的代码中,只有poll( )
方法不可用于List
对象。但是,poll( )
以FIFO
方式工作,从队列中返回和删除最上面的对象。或者,对于List
,您可以使用索引值为0的get(index)
方法获取第一个元素,然后将其删除。但您应该考虑使用LinkedList
,因为对于remove( )
操作,ArrayList
中的所有元素都将在每次删除时移位,这是一个代价高昂的操作。此外,由于LinkedList
实现了Queue
接口,因此它具有poll( )
方法。
备注:Queue最适合于给定的示例,我的答案只是根据您的问题使用列表的一种变通方法。
https://stackoverflow.com/questions/49827980
复制相似问题