Максимальная длина пути между двумя вершинами в DAG

Question

Учитывая направленный ациклический граф, G и две вершины u и v, мне нужно найти самый длинный ультрафиолетовый путь в G. DFS вызывает функцию исследовать, чтобы сохранить посещенные вершины в логическом массиве посещения [] (если вершина посещена, значениев массиве установлено значение true, в противном случае это false). Вершины u и v никогда не помечаются как посещенные. Переменная MAX хранит максимальный путь;при достижении вершины STOP в функции explore () значение MAX устанавливается равным max текущей длины пути и значения MAX. Код не работает правильно.

import java.util.Iterator;
import java.util.LinkedList;

public class DAG2 {
int vertex;
LinkedList<Integer> list[];

int START, STOP;
int length = 0;
int MAX = 0;

public DAG2(int vertex) {

    this.vertex = vertex;
    list = new LinkedList[vertex];
    for (int i = 0; i < vertex; i++) {
        list[i] = new LinkedList<>();
    }

}

public void addEdge(int source, int destination) {

    // add edge
    list[source].addFirst(destination);

}

void DFS(int u, int v) {

    boolean[] visited = new boolean[this.vertex];
    START = u;
    STOP = v;
    explore(v, visited);
}

private void explore(int v, boolean[] visited) {
    // TODO Auto-generated method stub

    visited[v] = true;
    visited[START] = false;
    visited[STOP] = false;

    Iterator<Integer> i = list[v].listIterator();

    while (i.hasNext()) {
        int n = i.next();
        length++;
        if (n == STOP) {
            MAX = Math.max(MAX, length);
            length = 0;
        }

        if (!visited[n])
            explore(n, visited);
    }
}

public static void main(String args[]) {
    DAG2 g = new DAG2(8);

    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(2, 5);
    g.addEdge(3, 6);
    g.addEdge(4, 7);
    g.addEdge(5, 7);
    g.addEdge(6, 5);
    g.addEdge(6, 7);
    // new
    g.addEdge(2, 3);
    g.addEdge(3, 5);
    g.addEdge(5, 4);

}
}

Answer 1

Первое, что я заметил в «посещаемом» массиве, это то, что если вы ищете более одного пути, вы можете посетить узел более одного раза (потому что к нему может привести более одной математики, например, 1 ->3 -> 4 и 1 -> 2 -> 3 -> 4 будут посещать 3).

Мой первый инстинкт поиска в глубину - использовать рекурсивный поиск. Я собрал один такой, который выглядит следующим образом:

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class DAG {
    private Map<Integer, List<Integer>> graph = new HashMap<>();

    public void addEdge(final int src, final int dst) {
        if (!graph.containsKey(src)) {
            graph.put(src, new LinkedList<Integer>());
        }
        graph.get(src).add(dst);
    }

    public List<Integer> findMaxPath(final int start, final int end) {
        if (start == end) {
            // The path is just this element, so return a list with just the
            // start (or end).
            final List<Integer> path = new LinkedList<>();
            path.add(start);
            return path;
        }

        if (!graph.containsKey(start)) {
            // There is no path forward.
            return null;
        }

        List<Integer> longestPath = null;

        for (Integer next : graph.get(start)) {
            final List<Integer> newPath = findMaxPath(next, end);
            if (null != newPath) {
                // Found a new path
                if ( (null == longestPath)
                  || (newPath.size() > longestPath.size()) )
                {
                    // It was longer than the previous longest,
                    // it is new longest.
                    longestPath = newPath;
                }
            }
        }

        if (null != longestPath) {
            // A path was found, include this node as the start of the path.
            longestPath.add(0, start);
        }
        return longestPath;
    }

    public static void main(final String[] args) {
        final DAG g = new DAG();

        g.addEdge(1, 2); 
        g.addEdge(1, 3); 
        g.addEdge(1, 6); 
        g.addEdge(2, 4); 
        g.addEdge(3, 5); 
        g.addEdge(6, 7); 
        g.addEdge(7, 4); 
        g.addEdge(2, 6);
        printPath(g.findMaxPath(1, 5));

        g.addEdge(4, 5);  // Make a longer path.
        printPath(g.findMaxPath(1, 5));
    }

    private static void printPath(final List<Integer> path) {
        System.out.println("Path:");
        if (null != path) {
            for (Integer p : path) {
                System.out.println(" " + p);
            }
        } else {
            System.out.println(" null");
        }
    }
}

Чтобы преобразовать его в нерекурсивный метод, вы можете использовать List в качестве стека. Где findMaxPath () вызывает себя, вместо этого вы должны нажать () текущий узел в стеке и использовать следующий, когда это будет сделано, pop () узел и продолжить. Поместите все это в цикл, и оно должно работать.