有向有环图两点间路径问题

缺乏、安全感 2022-06-03 00:20 245阅读 0赞

# 有向有环图两点间路径问题 #

本文主要介绍有向有环图两点间的路径问题。先简要的看一下什么是有向有环图。

![Center][]

那么如何利用类似深度优先遍历的方式对1到7之间的路径进行查询呢，下面说一下思路。

1、首先需要把有向有环图经过破环，形成有向无环图。

2、利用深度优先遍历实现对有向无环图所有路径进行查找。

好，下面看一下具体的实现。

首先是一个辅助类

package com.xueyou.graph;
    
    public class node {
        private int source;
        private int target;
    
        public int getSource() {
            return source;
        }
    
        public void setSource(int source) {
            this.source = source;
        }
    
        public int getTarget() {
            return target;
        }
    
        public void setTarget(int target) {
            this.target = target;
        }
    
        public node() {
        }
    
        public node(int source, int target) {
            this.source = source;
            this.target = target;
        }
    }

然后是具体的递归实现

package com.xueyou.graph;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class demo {
        public static void main(String[] args) {
            List<node> nodeList = new ArrayList<>();
            node node = new node(1, 2);
            node node2 = new node(1, 6);
            node node3 = new node(2, 4);
            node node4 = new node(2, 5);
            node node7 = new node(4, 3);
            node node1 = new node(1, 4);
            node node8 = new node(5, 7);
            node node9 = new node(6, 7);
            node node6 = new node(3, 7);
            node node5 = new node(3, 2);
            nodeList.add(node);
            nodeList.add(node1);
            nodeList.add(node2);
            nodeList.add(node3);
            nodeList.add(node4);
            nodeList.add(node5);
            nodeList.add(node6);
            nodeList.add(node7);
            nodeList.add(node8);
            nodeList.add(node9);
            List<Integer> ints = new ArrayList<>();
            findpath(nodeList, 1, 7, ints);
        }
    
        public static void findpath(List<node> nodeList, int source, int target, List<Integer> path) {
            System.out.println(path);
            if (path.indexOf(source) > -1) {
                return;
            }
            path = cleanMutilPath(path);
            for (int i = 0; i < nodeList.size(); i++) {
                node node = nodeList.get(i);
                if (node.getSource() == source) {
                    //如果相等则找到路径
                    if (node.getTarget() == target) {
                        path.add(node.getSource());
                        path.add(node.getTarget());
                        List<Integer> tmpList = new ArrayList<>();
                        tmpList = cleanMutilPath(path);
                        System.out.println("find path origin:" + path);
                        System.out.println("find path clean:" + tmpList);
                        path.clear();
                        return;
                    }
                    path.add(node.getSource());
                    findpath(nodeList, node.getTarget(), target, path);
                }
            }
        }
    
        public static List<Integer> cleanMutilPath(List<Integer> path) {
            List<Integer> tmp = new ArrayList<>();
            for (Integer integer : path) {
                if (tmp.indexOf(integer) < 0) {
                    tmp.add(integer);
                }
            }
            return tmp;
        }
    }

下面是运行结果：

![Center 1][]

[Center]: /images/20220603/7b0ee52147f343ce860cdea921b10320.png
[Center 1]: /images/20220603/231f62aeb9654efa98b898067d914f82.png