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

分手后的思念是犯贱 2021-07-24 17:13 378阅读 0赞

有向图:

:  ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xmeTYwOTIyNTI1OA_size_16_color_FFFFFF_t_70][]

找出 途中 从 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");
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xmeTYwOTIyNTI1OA_size_16_color_FFFFFF_t_70]: /images/20210724/5693f280c7f940c39802a5ea7958202e.png