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

Question

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

关于 "visited" 数组，我注意到的第一件事是，如果您正在寻找不止一条路径，您可能会不止一次访问一个节点（因为不止一次数学可能导致它，例如 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用作Stack。在 findMaxPath() 调用自身的地方，您将 push() 堆栈上的当前节点并使用下一个节点，完成后 pop() 节点并继续。将所有这些放在一个循环中，它应该可以工作。

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

Maximum path length between two vertices in a DAG

depth-first-search

directed-acyclic-graphs