使用DFS和java的路径查找

我正在开发一种搜索算法来查找图中的路径。在这个算法中，我需要找到一个无向图的所有路径，而不是加权图，它们只能通过一次图形连接。它必须在同一个节点中开始和结束。目前，我的程序正在做的是找到通过每个节点只有一次的所有路径。我需要连接而不是节点。使用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 3 4 5 6”1是节点的数量，2是链接的数量，3是起始节点，3 4是从节点3到节点的连接图4和5图6是从节点5-6。

的连接现在，我认为以下代码：

if (visited.contains(node)) { 
continue; 
}

正在通过各节点不会超过一次该程序。我需要帮助转换我的程序，让每个连接只经过一次，而不是通过每个节点一次。

关于我如何做到这一点的任何想法？

来源

2012-03-21 Cláudio Ribeiro

我假设你的意思是Edge而不是Connection。这样，你想要找到包含所有边的所有循环（在相同节点中开始和结束的路径）。

通过每个单一边的循环被称为欧拉路径。你可以看到一个解决方案here。

来源

2012-03-22 00:15:09 Mig

使用DFS和java的路径查找

回答

相关问题