找到所有的路径与DFS图 [英] Find all paths in a graph with DFS

问题描述

早上好！

我开发一个算法来找出无向，不加权图中所有的路径。我目前使用的是DFS algortihm与回溯，试图做到这一点。这是我目前的code：

I'm developing an algorithm to find all the paths in an undirected, not weighted graph. I'm currently using a DFS algortihm with backtracking to try and do that. Here is my current code:

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 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;

    dfs mapa = new dfs(startNode, numLinks);

    for(int i = 0; i<numLinks; i++){
        mapa.addLink(input.nextInt(), input.nextInt());
    }

    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(); 
        //System.out.println("Current Node:" + currentNode);
        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); 
        //System.out.println("visited:" + visited);

        for (Integer node : nodes) {
            //System.out.println("nodes:" + nodes);
            List<Integer> temp = new ArrayList<Integer>();
            temp.addAll(visited);
            temp.add(node);          
            findAllPaths(mapa, temp, paths, node);
        }

    }

    else {
        LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode);  
        System.out.println("currentNode:" + currentNode);
        //System.out.println("nodes:" + nodes);
        for (Integer node : nodes) {            
            if (visited.contains(node)) {
                continue;
            } 
            List<Integer> temp = new ArrayList<Integer>();
            temp.addAll(visited);
            System.out.println("visited:" + visited);
            temp.add(node);          
            findAllPaths(mapa, temp, paths, node);
        }
    }

} 

}

程序接收他输入整数。第一个是节点的数量，第二个是链接的数量和第三个是开始节点和结束记，这是相同的。所有这一切都在重新present节点之间的连接。

The program receives integers on his input. The first one is the number of nodes, the second one is the number of links and the third is the start node and end note, which are the same. All the integers that come after represent the connections between nodes.

的问题是，这种算法是找到所有访问单个节点一次的路径。我想是的算法找出所有访问每个连接只有一次的路径。 我如何能做到这一点任何想法？

The problem is, this algorithm is finding all the paths that visit a single node only once. What i want is the algorithm to find all the paths that visit each connection only once. Any idea on how i can do that?

推荐答案

您是在正确的轨道 - 回溯是一种巧妙的方法来解决它。

You are on the right track - backtracking is a neat way to solve it.

要获得所有路径的使用相同的边缘只有一次： 您使用的边缘后， findAllPaths（） - 从边集[删除的连接删除的 LinkedHashSet 这种边]的每个顶点的 - 并调用递归

To get all paths that "uses the same edge only once": after you use an edge in findAllPaths() - delete it from the set of edges [delete the connection from the LinkedHashSet of each vertex of this edge] - and invoke recursively.

在从递归返回 - 。不要忘了清洁环境，并重新添加该边两个顶点

After you return from the recursion - don't forget to "clean up the environment" and add this edge back to both vertices.

您将需要确保你没有碰到遍历集合，而修改它的麻烦。 [你不能做到这一点 - 这样做的结果是意想不到的 - 所以你可能会需要发送的 LinkedHashSet S的副本[没有相关的边缘 - 而不是原来的

You will need to make sure you don't run into troubles of iterating collection while modifying it. [You cannot do it - the result of doing so is unexpected] - so you will probably need to send a copy of the LinkedHashSets [without the relevant edge] - and not the original one.

这篇关于找到所有的路径与DFS图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！