- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试实现 BFS 来查找学习某门类(class)之前所需的所有先决条件。我的public List<Node> computeAllPrereqs(String courseName)
方法是我的代码困惑的地方。有人可以看看我的方法并帮助我找到问题吗?我认为结束节点将是无,因为我图中的类(class)都不会导致任何结果。该图不是循环的。
这是我传递给构造函数的文本文件,第一列是类(class),后面的类(class)是其先决条件:
CS1 None
CS2 CS1
CS3 CS2
CS4 CS1
CS5 CS3 CS4
CS6 CS2 CS4
.
public class Graph {
private Map<String, Node> graph;
public Graph(String filename) throws FileNotFoundException {
// open the file for scanning
File file = new File(filename);
Scanner in = new Scanner(file);
// create the graph
graph = new HashMap<String, Node>();
// loop over and parse each line in the input file
while (in.hasNextLine()) {
// read and split the line into an array of strings
// where each string is separated by a space.
Node n1, n2;
String line = in.nextLine();
String[] fields = line.split(" ");
for(String name: fields){
if (!graph.containsKey(fields[0]))
{
n1 = new Node(name);
graph.put(name, n1);
}
else{
n2 = new Node(name);
graph.get(fields[0]).addNeighbor(n2);
}
}
}
in.close();
}
public List<Node> computeAllPrereqs(String courseName){
// assumes input check occurs previously
Node startNode;
startNode = graph.get(courseName);
// prime the dispenser (queue) with the starting node
List<Node> dispenser = new LinkedList<Node>();
dispenser.add(startNode);
// construct the predecessors data structure
Map<Node, Node> predecessors = new HashMap<Node,Node>();
// put the starting node in, and just assign itself as predecessor
predecessors.put(startNode, startNode);
// loop until either the finish node is found, or the
// dispenser is empty (no path)
while (!dispenser.isEmpty()) {
Node current = dispenser.remove(0);
if (current == new Node(null)) {
break;
}
// loop over all neighbors of current
for (Node nbr : current.getNeighbors()) {
// process unvisited neighbors
if(!predecessors.containsKey(nbr)) {
predecessors.put(nbr, current);
dispenser.add(nbr);
}
}
}
return constructPath(predecessors, startNode, null);
}
private List<Node> constructPath(Map<Node,Node> predecessors,
Node startNode, Node finishNode) {
// use predecessors to work backwards from finish to start,
// all the while dumping everything into a linked list
List<Node> path = new LinkedList<Node>();
if(predecessors.containsKey(finishNode)) {
Node currNode = finishNode;
while (currNode != startNode) {
path.add(0, currNode);
currNode = predecessors.get(currNode);
}
path.add(0, startNode);
}
return path;
}
}
这是我用来在图中创建节点和邻居的节点类:
public class Node {
/*
* Name associated with this node.
*/
private String name;
/*
* Neighbors of this node are stored as a list (adjacency list).
*/
private List<Node> neighbors;
public Node(String name) {
this.name = name;
this.neighbors = new LinkedList<Node>();
}
public String getName() {
return name;
}
public void addNeighbor(Node n) {
if(!neighbors.contains(n)) {
neighbors.add(n);
}
}
public List<Node> getNeighbors() {
return new LinkedList<Node>(neighbors);
}
@Override
public String toString() {
String result;
result = name + ": ";
for(Node nbr : neighbors) {
result = result + nbr.getName() + ", ";
}
// remove last comma and space, or just spaces in the case of no neighbors
return (result.substring(0, result.length()-2));
}
@Override
public boolean equals(Object other) {
boolean result = false;
if (other instanceof Node) {
Node n = (Node) other;
result = this.name.equals(n.name);
}
return result;
}
@Override
public int hashCode() {
return this.name.hashCode();
}
}
这是我的测试类:
public class Prerequisite {
/**
* Main method for the driver program.
*
* @param args the name of the file containing the course and
* prerequisite information
*
* @throws FileNotFoundException if input file not found
*/
public static void main(String[] args) throws FileNotFoundException {
// Check for correct number of arguments
if(args.length != 1) {
String us = "Usage: java Prerequisite <input file>";
System.out.println(us);
return;
}
// create a new graph and load the information
// Graph constructor from lecture notes should
// be modified to handle input specifications
// for this lab.
Graph graph = new Graph(args[0]);
// print out the graph information
System.out.println("Courses and Prerequisites");
System.out.println("=========================");
System.out.println(graph);
// ASSUMPTION: we assume there are no cycles in the graph
// Part I:
// compute how many (and which) courses must be taken before it is
// possible to take any particular course
System.out.println("How many courses must I take "
+ "before a given course?!?!?");
for(String name : graph.getAllCourseNames()) {
List<Node> allPrereqs = graph.computeAllPrereqs(name);
System.out.print(String.valueOf(allPrereqs.size()));
System.out.print(" courses must be taken before " + name + ": ");
for(Node el : allPrereqs) {
System.out.print(el.getName() + " ");
}
System.out.println();
}
}
当我运行此测试时,我的输出是:
0 courses must be taken before CS1:
0 courses must be taken before CS3:
0 courses must be taken before CS2:
0 courses must be taken before CS5:
0 courses must be taken before CS4:
0 courses must be taken before CS6:
应该是:
0 courses must be taken before CS1:
2 courses must be taken before CS3: CS1 CS2
1 courses must be taken before CS2: CS1
4 courses must be taken before CS5: CS1 CS3 CS2 CS4
1 courses must be taken before CS4: CS1
3 courses must be taken before CS6: CS1 CS2 CS4
我知道我发布了很多代码,但如果需要帮助修复我的错误,我不想在以后编辑更多代码。
最佳答案
请注意,通过深度优先搜索 (DFS) 可以更有效地确定先决条件,从而可以实现拓扑排序。
在图构建过程中,当链接邻居时,链接的是“相似节点”而不是现有图节点本身,因此生成的图实际上是未连接的。要解决该问题,请将图表的实际节点相互链接。
if (!graph.containsKey(fields[0]))
{
n1 = new Node(name);
graph.put(name, n1);
}
else{
if(graph.containsKey(name)) {
n2 = graph.get(name);
}
else {
n2 = new Node(name);
graph.put(name, n2);
}
graph.get(fields[0]).addNeighbor(n2);
}
上述代码片段的另一个好处是它将终端“None”节点添加到图表中。
无法构建单行路径,因为一门类(class)可能有多个先决条件。例如,CS6 依赖于 CS2 和 CS4。在 constructorPath 方法中,仅在遵循这些路径之一后就会触发终止条件。因此,考虑到程序的当前结构,您能实现的最好结果就是输出先决类(class)集而不是单行路径。
private List<Node> constructPath(Map<Node,Node> predecessors,
Node startNode, Node finishNode) {
/*
// use predecessors to work backwards from finish to start,
// all the while dumping everything into a linked list
List<Node> path = new LinkedList<Node>();
if(predecessors.containsKey(finishNode)) {
Node currNode = finishNode;
while (currNode != startNode) {
path.add(0, currNode);
currNode = predecessors.get(currNode);
}
path.add(0, startNode);
}
*/
Set<Node> prereqs = new HashSet<Node>(predecessors.keySet());
prereqs.remove(graph.get("None"));
return new ArrayList<Node>(prereqs);
}
采用这种方法,参数 startNode 和 finishNode 都不是必需的,并且前驱映射的创建是多余的。
最后,类(class)本身并不是先决条件,因此将自己指定为前修类(class)是不正确的。
// put the starting node in, and just assign itself as predecessor
// predecessors.put(startNode, startNode);
考虑到这些修改,这就是输出
0 courses must be taken before CS1:
1 courses must be taken before CS2: CS1
2 courses must be taken before CS3: CS2 CS1
1 courses must be taken before CS4: CS1
4 courses must be taken before CS5: CS4 CS2 CS3 CS1
3 courses must be taken before CS6: CS4 CS2 CS1
为了改进代码,可以使用 TreeSet ( http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html ) 代替 HashSet 以统一的顺序输出先决条件。然而,要使用 TreeSet,必须扩充 Node 类以实现 Comparable ( How to implement the Java comparable interface? )。
同样,如果输出先决条件集不令人满意,请考虑使用 DFS 来生成拓扑排序 ( http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htm )。
关于java - BFS 无法正常工作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29112286/
自从我 faced an issue由于背景图片对于不同分辨率的内容来说太短,我尝试将背景分成 3 部分并自动拉伸(stretch)中间部分以相应地填充顶部和底部图像之间的空间。不幸的是我没能在 CS
我从去年开始就在我的程序中运行这个函数(Linux 和 Windows)。 现在我需要实现一个新功能,我的新构建不再运行。 我还有其他使用 POST 的 CUrl 函数,结果是一样的:没问题,但我的
在评估函数应用方面,Haskell 是只支持普通降阶还是也支持应用降阶?我是否认为正常顺序是 Haskell 惰性的原因? 最佳答案 GHC 运行时不使用术语缩减策略,因为那会非常低效。事实上,GHC
怎么来的multi使用多处理池对多个“进程”上的数据进行分段和处理的函数比仅调用 map 慢(8 秒)。功能(6 秒)? from multiprocessing import Pool import
假设我正在渲染一个 3d GL_TRIANGLE。该对象需要 3 个顶点才能定义:A、B、C。我将此类数据放入缓冲区并通过 glVertexAttribPointer 将其绑定(bind)到着色器。
我有一个字体的三个文件,普通的,粗体的和浅色的。由于 font-weight:light 不存在,我该如何在 font-face 上设置 light 呢? 顺便问一下,font-weight:ligh
我是 C 的新手,我似乎无法弄清楚什么似乎是一个非常简单的指针问题。我的程序将行号添加到文件中。它逐行读入文件,然后在每行的开头添加一个行号。它在每个文件上都可以正常工作,如下所示: soccer@s
我有以下代码,我不确定为什么当它命中 Myclass 的析构函数时我会收到堆损坏检测错误。我相信我正在正确地释放内存?? #include #include using namespace std
有什么方法可以将“正常”数学符号解释为逆波兰符号 (RPN)..? 例如1) 2 + 3*4 - 1 = 234*+1-2) 5 (4-8) = 548- 你可以假设遵循 BODMAS 规则并且必须首
http://www.ergotopia.de/ergonomie-shop/ergonomische-kissen/orthopaedisches-sitzkissen的手机页面应该看起来像右边(检
我正在 Phonegap/Cordova 中构建一个应用程序。应用目前相当简单,但确实需要网络状态和地理定位插件才能工作。 到目前为止,我已经在 Android 上开发了该应用程序(目前它仅由一些基本
我一整天都在做这个,但没有运气 我设法在一行 TfidfVectorizer 中消除了问题 这是我的工作代码 from sklearn.feature_extraction.text import C
也许有人看到一个错误,问题是当我按btn2 (button 2)和btn3 (button 3)应用程序crashes时,但操作仍然有效,即video正在运行并且PDF打开,而button 1正常工作
我正在开发一个应用程序。它的第一页是登录屏幕。成功登录后,我想将用户带到选项卡式 Activity 。我怎样才能在安卓中做到这一点?谢谢 最佳答案 在 Android 中,启动 Activity 是通
我不确定我在这里做错了什么。 :normal! I### 当我对一个单词执行此命令时,我想要的最终结果是: ### word 但是我得到了这个: ###word 最佳答案 Vim 的 :normal是
我必须将 2 个静态矩阵发送到分配动态矩阵的函数,将矩阵 1 乘以矩阵 2,并返回新矩阵的地址。请注意,COMM 很常见。 我尝试删除 free_matrix 行,它工作正常。 void main()
我在我的一个项目中使用 Gnome libglib 并遇到了一个奇怪的错误。我可以输入 GList 的元素数量看起来仅限于 45 个。在第 45 个元素处,它给出了此错误 40 counter 41
我正在尝试获取“顶级”HWND 的尺寸。即,我想要 Firefox/Windows 资源管理器等的主 HWND 的当前尺寸。窗口。如果窗口最小化, GetWindowRect() 将不起作用。 Get
相同的标题:什么是索引 - 正常 - 全文 - 唯一? 最佳答案 普通索引用于通过仅包含行数据的切片或散列来加速操作。 全文索引向数据库的全文搜索 (FTS) 引擎指示它应该将数据存档在给定字段中,以
我正在使用 EnumParser来自 here它在 VC++ 中编译得很好,但是使用 gcc 我有这样的错误: ./Terminator.o: In function `EnumParser::Enu
我是一名优秀的程序员,十分优秀!