我必须为学校作业实现一个搜索算法。现在,我在惟一的java实现方面遇到了问题。以下是我目前的代码(我一直在stackoverflow中找到的一些代码中进行dfs搜索,然后我必须添加验证以满足项目标准):
import java.util.*;
public class dfs<Grafo> {
public static void main(String[] args) {
class Grafo{
private Map<Integer, LinkedHashSet<Integer>> map = new HashMap();
public void addEdge(int source, int destiny) {
LinkedHashSet<Integer> adjacente = map.get(source);
if(adjacente==null) {
adjacente = new LinkedHashSet();
map.put(source, adjacente);
}
adjacente.add(destiny);
}
public void addLink(int source, int destiny) {
addEdge(source, destiny);
addEdge(destiny, source);
}
public LinkedList<Integer> adjacentNodes(int last) {
LinkedHashSet<Integer> adjacente = map.get(last);
if(adjacente==null) {
return new LinkedList();
}
return new LinkedList<Integer>(adjacente);
}
}
Scanner input = new Scanner(System.in);
int numVertices = input.nextInt();
int numLinks = input.nextInt();
int startNode = input.nextInt();
int endNode = startNode;
Grafo mapa = new Grafo();
for(int i = 0; i<numLinks; i++){
mapa.addLink(input.nextInt(), input.nextInt());
}
List<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
Integer currentNode = startNode;
List<Integer> visited = new ArrayList<Integer>();
visited.add(startNode);
new dfs().findAllPaths(mapa, visited, paths, currentNode);
for(ArrayList<Integer> path : paths){
for (Integer node : path) {
System.out.print(node);
System.out.print(" ");
}
System.out.println();
}
}
private void findAllPaths(Grafo mapa, List<Integer> visited,
List<ArrayList<Integer>> paths, Integer currentNode) {
if (currentNode.equals(startNode)) {
paths.add(new ArrayList(Arrays.asList(visited.toArray())));
return;
}
else {
LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode);
for (Integer node : nodes) {
if (visited.contains(node)) {
continue;
}
List<Integer> temp = new ArrayList<Integer>();
temp.addAll(visited);
temp.add(node);
findAllPaths(mapa, temp, paths, node);
}
}
}
}
我遇到的问题是,我只能提交一个java文件,所以我把所有东西都放在这个文件中。当我使用findAllPaths函数时,他没有识别"startNode"常量(eclipse说它不能解析为变量),他说"adjacentNodes"函数没有为Grafo类型定义。
我有办法解决这个问题吗?或者我必须重新思考我做这件事的方式吗?如果有,什么是实现这一点的好方法?
其他人似乎已经解决了您的一些编码问题,所以我只想说明如何使用单个文件约束。
假设您有三个类,Edge、Node和Graph,它们是在三个独立的文件中开发的。以下是如何组合它们:
// in file GraphSearchHomework.java
public class GraphSearchHomework {
public static class Edge {
// ... Edge code here ...
// You can reference Nodes and Graphs
// just as if this was in a separate file
}
public static class Node {
// ... Node code here ...
// You can reference Edges and Graphs
// just as if this was in a separate file
}
public static class Graph {
// ... Graph code here ...
// You can reference Edges and Nodes
// just as if this was in a separate file
}
public static void main(String args[]) {
// This main can instantiate Graphs, Nodes, Edges
// Keep this simple, though. Most code belongs outside of main.
}
}
你似乎在试图把它强行放在一个文件中时犯了一些错误。如果这对你有帮助,可以继续单独开发每个类,然后将它们组合起来。
我为您清除了错误和警告。
仍然运行不好,但你可以自己解决。。
看起来你不需要外部类dts。如果你让Grafo成为你的顶级课程,它会变得更干净。
如果将startNode设为类变量,则可以在主方法中实例化它,也可以在其他方法中访问它。
此外,当您实例化泛型类时,您应该指定如下的泛型类型:
new LinkedList<Integer>();
我现在还不打算交,但至少结构更干净了一点。。
import java.util.*;
public class Grafo {
private Map<Integer, LinkedHashSet<Integer>> map = new HashMap<Integer, LinkedHashSet<Integer>>();
private int startNode;
public Grafo(int startNode) {
super();
this.startNode = startNode;
}
public void addEdge(int source, int destiny) {
LinkedHashSet<Integer> adjacente = map.get(source);
if(adjacente==null) {
adjacente = new LinkedHashSet<Integer>();
map.put(source, adjacente);
}
adjacente.add(destiny);
}
public void addLink(int source, int destiny) {
addEdge(source, destiny);
addEdge(destiny, source);
}
public LinkedList<Integer> adjacentNodes(int last) {
LinkedHashSet<Integer> adjacente = map.get(last);
if(adjacente==null) {
return new LinkedList<Integer>();
}
return new LinkedList<Integer>(adjacente);
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int numVertices = input.nextInt();
int numLinks = input.nextInt();
int startNode = input.nextInt();
int endNode = startNode;
Grafo mapa = new Grafo(startNode);
for(int i = 0; i<numLinks; i++){
mapa.addLink(input.nextInt(), input.nextInt());
}
List<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
Integer currentNode = startNode;
List<Integer> visited = new ArrayList<Integer>();
visited.add(startNode);
mapa.findAllPaths(mapa, visited, paths, currentNode);
for(ArrayList<Integer> path : paths){
for (Integer node : path) {
System.out.print(node);
System.out.print(" ");
}
System.out.println();
}
}
private void findAllPaths(Grafo mapa, List<Integer> visited,
List<ArrayList<Integer>> paths, Integer currentNode) {
if (currentNode.equals(startNode)) {
paths.add(new ArrayList<Integer>(visited));
return;
}
else {
LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode);
for (Integer node : nodes) {
if (visited.contains(node)) {
continue;
}
List<Integer> temp = new ArrayList<Integer>();
temp.addAll(visited);
temp.add(node);
findAllPaths(mapa, temp, paths, node);
}
}
}
}
startNode
是main()
中的一个局部变量,因此不被findAllPaths()
识别[记住,可能会从一个非main方法调用它…]java具有静态绑定,因此它禁止这样做。
您可以将其作为参数添加到findAllPaths()
,也可以将startNode
作为类dfs
中的字段,然后findAllPaths()
就可以访问它。
与Grafo
的想法相同-您将其声明为方法内部类,您应该将其声明为此类的内部类-否则只有main()
会"知道"如何使用它。