Проверьте, является ли Graph циклическим с DFS; Ввод метода isCyclic: список <Type>источников и список <Type>пунктов назначения - PullRequest
0 голосов
/ 08 марта 2019

Поэтому мне нужна помощь в создании метода DFS, который принимает два аргумента (srcData и dstData), и метода isCyclic, который использует DFS для проверки цикличности графа. Вот мой текущий код для DFS:

public LinkedList<Type> DFS(Type srcData, Type dstData) throws IllegalArgumentException {
    if(!this.getSources().contains(srcData) || !this.getDestinations().contains(dstData))
        throw new IllegalArgumentException();
    Vertex start = vertices.get(srcData);
    Vertex goal = vertices.get(dstData);
    start.visited = true;

    LinkedList<Vertex> stack = new LinkedList<Vertex>();
    LinkedList<Type> result = new LinkedList<Type>();
    stack.offer(start);
    Vertex end = null;
    while(stack.size() != 0)  {
        Vertex v = stack.removeLast();
        if(v.getElement().equals(dstData)) {
            end = v;
        }
        if(!v.visited) {
            v.visited = true;

            for(Edge e : v.getEdge()) {
                Vertex neighbor = e.getOtherVertex();
                if(!neighbor.visited) {
                    neighbor.cameFrom = v;
                    stack.addLast(neighbor);
                }
            }
        }
    }
    while(end != null) {
        result.addFirst(end.getElement());
        end = end.cameFrom;
    }
    return result;
}

И тогда мой код для isCyclic ниже:

public static <Type> boolean isCyclic(List<Type> sources, List<Type> destinations) throws IllegalArgumentException {
    if(sources.size() != destinations.size())
        throw new IllegalArgumentException();

    Graph<Type> gra = new Graph<Type>();
    for(int i = 0; i < sources.size(); i++) {
        gra.addEdge(sources.get(i), destinations.get(i));
    }

    for(Type t: sources) {
        if(gra.DFS_2(t, t))
            return true;
    }

    return false;
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...