简单实现有向无环图思路

今天药忘吃喽~ 2022-02-01 05:25 317阅读 0赞

给一部分带有from和to的节点组织成一个有向无环图，给from与to路径找到他们之前的连线轨迹。实现思路：遍历所有的节点，该节点如果不包含from或者to的内容且周围只有一个节点这样的节点从我们总的节点中删除，最终找到的就是我们想要的节点路线。代码demo如下

import java.lang.reflect.Array;
    import java.util.*;
    
    public class CirDemo {
        public static void main(String[] args) {
            List<Map<String,Integer>> datalist=new ArrayList<>();
            Integer from=-1;
            Integer to=-3;
            List<Map<String, Integer>> list = getInitDat();
            Set<Integer> set = new HashSet<>();
            for (Map<String,Integer> map :list){
                set.add(map.get("from"));
                set.add(map.get("to"));
            }
    
            getFinalData(from,to,set,list);
    
            getFromToData(-3,list,datalist);
    
            System.out.println(list.size());
    
        }
    
        public static void getFinalData(Integer from, Integer to, Set<Integer> set, List<Map<String,Integer>> list){
            Set<Integer> removeSetData = new HashSet<Integer>();
            List<Map<String,Integer>> removeListData=new ArrayList<>();
            for (Integer key :set){
                int count=0;
                for (Map<String,Integer> map :list){
                    Integer f = map.get("from");
                    Integer t = map.get("to");
                    if (key==from || key==to){
                        break;
                    }else{
                        if (f==key || t== key){
                            count++;
                            if (count==1){
                                removeListData.add(map);
                            }else if (count==2){
                                removeListData.remove(removeListData.size()-1);
                            }
                        }
                    }
                }
                if (count==1 && key !=from && key !=to){
                    removeSetData.add(key);
                }
            }
            if (removeSetData.size()==0 && removeListData.size()==0){
                return ;
            }else{
                set.removeAll(removeSetData);
                list.removeAll(removeListData);
                getFinalData(from,to,set,list);
            }
        }
    
        public static void getFromToData(Integer from,List<Map<String,Integer>> list,List<Map<String,Integer>> datalist){
            if (list.size()==0){
                return;
            }
            List<Map<String,Integer>> removeList=new ArrayList<>();
            for (Map<String,Integer> dataMap :list){
                Integer f = dataMap.get("from");
                Integer t = dataMap.get("to");
                if (f==from){
                    Map<String,Integer> mp = new HashMap<>();
                    mp.put("from",from);
                    mp.put("to",dataMap.get("to"));
                    datalist.add(mp);
                    from=dataMap.get("to");
                    removeList.add(dataMap);
                    break;
                }
                if (t==from){
                    Map<String,Integer> mp = new HashMap<>();
                    mp.put("from",from);
                    mp.put("to",dataMap.get("from"));
                    datalist.add(mp);
                    from=dataMap.get("from");
                    removeList.add(dataMap);
                    break;
                }
            }
            list.removeAll(removeList);
            getFromToData(from,list,datalist);
        }
    
        public static List<Map<String, Integer>> getInitDat(){
            List<Map<String, Integer>> list = new ArrayList<>();
            Map<String, Integer> map = new HashMap<>();
            map.put("from",-7);
            map.put("to",-6);
            Map<String, Integer> map1 = new HashMap<>();
            map1.put("from",-4);
            map1.put("to",-6);
            Map<String, Integer> map2 = new HashMap<>();
            map2.put("from",-5);
            map2.put("to",-6);
            Map<String, Integer> map3 = new HashMap<>();
            map3.put("from",-5);
            map3.put("to",-3);
            Map<String, Integer> map4 = new HashMap<>();
            map4.put("from",-4);
            map4.put("to",-2);
            Map<String, Integer> map5 = new HashMap<>();
            map5.put("from",-4);
            map5.put("to",-1);
            Map<String, Integer> map6 = new HashMap<>();
            map6.put("from",-1);
            map6.put("to",-9);
            Map<String, Integer> map7 = new HashMap<>();
            map7.put("from",-1);
            map7.put("to",-8);
            Map<String, Integer> map8 = new HashMap<>();
            map8.put("from",-8);
            map8.put("to",-10);
            list.add(map);
            list.add(map1);
            list.add(map2);
            list.add(map3);
            list.add(map4);
            list.add(map5);
            list.add(map6);
            list.add(map7);
            list.add(map8);
            return list;
        };
    }