java - DFS递归，更精确

在进行深度优先搜索时，我需要获取精确度，如果您不知道精确度的含义，它是一个数组，其中包含顶点的顶点，这对我来说很难解释，但是我认为示例会更容易理解。假设我们有顶点1 2 3 4 5 6 7 8;完成DFS后，我们得到的是1 2 3 4 7 5 8 6，因此prec将会是1 1 2 3 4 4 55。看这张照片：

如果仍然不清楚它是什么，那么从1个顶点“出现” 1个，然后从1个顶点得到2个顶点，然后从2个顶点得到3个顶点，依此类推。 Prec数组包含其他顶点所来自的那些顶点，如果我说的没错，对我不好的lanquaqe表示歉意。
我的问题是，如何将其实现到程序中以实现精确度？

// Java program to print DFS traversal from a given given graph
import java.io.*;
import java.util.*;

// This class represents a directed graph using adjacency list
// representation
class Graph
{
private int V; // No. of vertices

// Array of lists for Adjacency List Representation
private LinkedList<Integer> adj[];

// Constructor
Graph(int v)
{
    V = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i)
        adj[i] = new LinkedList();
}

//Function to add an edge into the graph
void addEdge(int v, int w)
{
    adj[v].add(w); // Add w to v's list.
}

// A function used by DFS
void DFSUtil(int v,boolean visited[])
{
    // Mark the current node as visited and print it
    visited[v] = true;
    System.out.print(v+" ");

    // Recur for all the vertices adjacent to this vertex
    Iterator<Integer> i = adj[v].listIterator();
    while (i.hasNext())
    {
        int n = i.next();
        if (!visited[n])
            DFSUtil(n,visited);
    }
}

// The function to do DFS traversal. It uses recursive DFSUtil()
void DFS()
{
    // Mark all the vertices as not visited(set as
    // false by default in java)
    boolean visited[] = new boolean[V];

    // Call the recursive helper function to print DFS traversal
    // starting from all vertices one by one
    for (int i=0; i<V; ++i)
        if (visited[i] == false)
            DFSUtil(i, visited);
}

public static void main(String args[])
{
    Graph g = new Graph(9);

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



    System.out.println("Following is Depth First Traversal");

    g.DFS();
}
}
// This code is contributed by Aakash Hasija

最佳答案

您想要的是一个顶点prec数组，其中prec [v] = u，使得u是dfs算法产生的隐式树中v的父级。您只需要做：

if (!visited[n]){
        prec[n] = v;
        DFSUtil(n,visited);
}

因为v肯定是n的父代，所以由于仅检查一次n是否未访问n，DFDFil将被调用一次。

关于java - DFS递归，更精确，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59277322/