DFS递归，获取prec

Question

我需要得到prec，在做深度优先搜索的时候，如果你不知道prec是什么意思，它是一个数组，其中包含顶点左顶点，这对我来说很难解释，但我认为例子会更容易理解。假设我们有顶点 1 2 3 4 5 6 7 8；当完成 DFS 时，我们有 1 2 3 4 7 5 8 6，所以 prec 将是 1 1 2 3 4 4 5 5。看看这张照片：

如果仍然不清楚它是什么，那么 1 "came" 来自 1 个顶点，然后 2 个顶点来自 1，然后 3 个顶点来自 2，依此类推。 Prec 数组包含其他顶点来自的那些顶点，如果我说得对，对不起我的错误 lanquaqe。我的问题是，如何将它实现到一个程序中以获得那个 prec？

// 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

Answer 1

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

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

因为 v 肯定是 n 的父级，因为如果我们正在检查 n 是否未被访问，DFSUtil 只会为 n 调用一次。

DFS递归，获取prec

DFS recursive, getting prec

java

graph-theory

depth-first-search