DAG中两个顶点之间的最大路径长度

Question

给定有向无环图，G和两个顶点u和v，我需要找到G中最长的uv路径。DFS调用exploring函数将访问的顶点存储在visit []布尔数组中（如果访问了顶点，则为数组设置为true，否则为false）。顶点u和v永远不会标记为已访问。变量MAX存储最大路径；当在explorer（）函数中达到STOP顶点时，将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）。