我必須在java中爲學校項目實現搜索算法。在這個算法中,我需要在一個無向圖中找到一條路徑,它只經過一次鏈接並結束於開始節點。我試圖使用帶回溯的DFS來解決這個問題,但是我在執行它時遇到了麻煩。這裏是我的代碼:在java中使用java查找路徑算法
import java.util.*;
public class Graph {
private Map<Integer, LinkedHashSet<Integer>> map =
new HashMap<Integer, LinkedHashSet<Integer>>();
private int startNode;
private int numLinks;
public Graph(int startNode, int numLinks) {
super();
this.startNode = startNode;
this.numLinks = numLinks;
}
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);
System.out.println("adjacentes:" + adjacente);
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;
Graph mapa = new Graph(startNode, numLinks);
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(Graph 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);
}
}
}
}
該計劃應該在他的投入,其中第一個是節點的數量接收整數,第二個是鏈接的數量,三是開始節點(至極是也是末端節點),後面的所有整數代表節點之間的鏈接。
目標是最後用整數打印單行。這些整數表示我訪問每個節點完成路徑的順序。目前正在測試中,它只打印一個整數,表示第一個節點。
我想我的問題是填充圖表,填充相鄰的列表。有人能幫助我嗎?
請更具體的問題,你有什麼問題。什麼不按預期工作,你期望什麼等? – Thomas 2012-03-20 17:07:28
我的目標是最後用整數打印單行。這些整數表示我訪問每個節點完成路徑的順序。目前正在測試,它只打印一個單一的integeer,這代表第一個節點。 – 2012-03-20 17:13:04
@CláudioRibeiro:這難道不是NP-hard旅行推銷員問題嗎?要求回到起始城市(這不會改變問題的複雜性)?你需要找到最短路徑還是任何方式?最多有多少個節點? – TacticalCoder 2012-03-20 17:21:59