有向图 两点间所有路径 及 所包含的环

 有向图:   

:  

找出 途中 从 A  到  F  一共有多少中走法,  包含的闭环 有哪些   

构思:   

遍历前  先准备一个 list 用来存放当前路径,

从A开始  先找到B  ,B找到D, D 到F,   此时  F为所找目标节点,  此时算是找到一条路径,     此时路径为    A ,B,D,F

接下来  从 F 返回上一层   D   再找D 的另一个节点  C   ,C有两个子节点, 随便选一个  B,  此时 当前路径中存在一个B,重复了, 所以此处是一个环,  然后返回上一级C   再从C到 E   E到F ,   此时路径为   A ,B,D,C,E,F 

再依次返回, 每上一层 都遍历找没有被访问过的子节点,    直到访问结束.

(如果看不明白的童鞋还是多跑几次代码 ,然后找规律吧.这个确实不太好解释哈)

其中用到递归

上代码:     

 

/**
 * @Annotion:   节点实体,一个实体对应的是一条线,链接两个节点
 * @ClassName: Node
 * @Author:
 * @Date: 2019/9/29  10:11
 * @Version: 1.0
 */
public class Node {
    /**上游节点*/
    private String source;
    /**下游节点*/
    private String target;

    public Node(String source, String target) {
        this.source = source;
        this.target = target;
    }

    public String getSource() {
        return source;
    }

    public void setSource(String source) {
        this.source = source;
    }

    public String getTarget() {
        return target;
    }

    public void setTarget(String target) {
        this.target = target;
    }
}

/**
 * @Annotion: 从  一个点  到另一个点所有路径走法 ,并输出环
 * @ClassName: TwoPointsPath
 * @Author: 
 * @Date: 2019/9/29  9:54
 * @Version: 1.0
 */
public class PointsPath {
    /**当前路径*/
    private static List<String> nowPath = new ArrayList<>();

    /**
     *
     * @param nodeList
     * @param source 起始节点
     * @param target 目标节点
     */
    public static void findAllPath(List<Node> nodeList,String source,String target){
        if(nowPath.contains(source)){
            System.out.println("这是一个环:"+nowPath);
            nowPath.remove(nowPath.size()-1);
            return;
        }
        for(int i = 0 ;i<nodeList.size();i++){
            Node node = nodeList.get(i);
            if(node.getSource().equals(source)){
                nowPath.add(node.getSource());
                if(node.getTarget().equals(target)){
                    nowPath.add(node.getTarget());
                    System.out.println("这是一条路径:"+nowPath);
                    /*因为添加了终点路径,所以要返回两次*/
                    nowPath.remove(nowPath.size()-1);
                    nowPath.remove(nowPath.size()-1);
                    /*已经找到路径,返回上层找其他路径*/
                    continue;
                }
                findAllPath(nodeList,node.getTarget(),target );
            }
        }
        /*如果找不到下个节点,返回上层*/
        if(nowPath.size()>0){
            nowPath.remove(nowPath.size()-1);
        }

    }

    /**
     * 测试
     */
    public static void main(String[] args){
        List<Node> list = new ArrayList<>();
        list.add(new Node("A", "B"));
        list.add(new Node("A", "C"));
        list.add(new Node("B", "D"));
        list.add(new Node("D", "F"));
        list.add(new Node("D", "C"));
        list.add(new Node("C", "B"));
        list.add(new Node("C", "E"));
        list.add(new Node("E", "F"));

        findAllPath(list,"A","F");
    }

}