0
グラフ内のパスを見つけるための検索アルゴリズムを開発しています。このアルゴリズムでは、各グラフ接続を一度だけ通過する無向グラフではなく、すべての経路を見つける必要があります。同じノードで開始し、終了する必要があります。現在、私のプログラムがやっていることは、各ノードを一度だけ通過するすべてのパスを見つけることです。私は、ノードではなく接続が必要です。DFSとjavaを使用した経路探索
import java.util.*;
public class dfs {
private static Map<Integer, LinkedHashSet<Integer>> map = new HashMap<Integer, LinkedHashSet<Integer>>();
private int startNode;
private int numLinks;
public dfs(int startNode, int numLinks) {
super();
this.startNode = startNode;
this.numLinks = numLinks;
}
public int getNumLinks(){
return 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 adj) {
LinkedHashSet<Integer> adjacente = map.get(adj);
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;
dfs mapa = new dfs(startNode, numLinks);
for(int i = 0; i<numLinks; i++){
int inicio = input.nextInt();
int fim = input.nextInt();
mapa.addLink(inicio, fim);
}
List<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
List<Integer> visited = new ArrayList<Integer>();
visited.add(startNode);
Integer currentNode = 0;
Iterator it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pairs = (Map.Entry)it.next();
currentNode = (Integer) pairs.getKey();
mapa.findAllPaths(mapa, visited, paths, currentNode);
}
}
private void findAllPaths(dfs mapa, List<Integer> visited,
List<ArrayList<Integer>> paths, Integer currentNode) {
if (currentNode.equals(startNode)) {
paths.add(new ArrayList<Integer>(visited));
LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode);
for (Integer node : nodes) {
List<Integer> temp = new ArrayList<Integer>();
temp.addAll(visited);
temp.add(node);
System.out.println("temp:" + temp);
findAllPaths(mapa, temp, paths, node);
}
}
else {
LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode);
System.out.println("currentNode:" + currentNode);
List<Integer> inseridos = new ArrayList<Integer>();
for (Integer node : nodes) {
if (visited.contains(node)) {
continue;
}
List<Integer> temp = new ArrayList<Integer>();
inseridos.add(currentNode);
temp.addAll(visited);
System.out.println("visited:" + visited);
temp.add(node);
findAllPaths(mapa, temp, paths, node);
}
}
}
}
プログラムは、彼の入力に整数を受け取ります
は、ここに私のコードです。最初の1つはノードの数であり、2つ目はリンクの数であり、3つ目は開始ノードと終了ノートであり、同じです。後に来るすべての整数は、ノード間の接続を表します。
例として、プログラムは「1 2 3 3 4 5 6」を受信します。1はノード数、2はリンク数、3は開始ノード、3はノード3からノードへの接続です
if (visited.contains(node)) {
continue;
}
プログラムが複数回、各ノードを経由していないことを行っている：4と5 6は今6
へのノード5からの接続ですが、私は次のコードは思います。私は、各ノードを一度通過するのではなく、各接続を一度だけ通過するように自分のプログラムを変換する助けが必要です。
どうすればいいですか？