DFS recursive, getting prec

Question

i need to get prec, while doing Depth First Search, if you don't know what prec means, it is an array, which contains vertices left vertex, it is hard to explain for me, but i think example will be more understandable. So let's say we have vertices 1 2 3 4 5 6 7 8; when finished DFS, we have, 1 2 3 4 7 5 8 6, so prec would be 1 1 2 3 4 4 5 5. Look at this photo:

If still it's not clear what it is, so 1 "came" from 1 vertex, then 2 vertex came from 1, then 3 vertex came from 2 and so on. Prec array contains those vertices from which other vertix came from, if i said it right, sorry for my bad lanquaqe. My question is, how to implement it into a program to get that 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

What do you want is an array of vertices prec, where prec[v] = u such that u is the parent of v in the implicit tree produced by the dfs algorithm. You just have to do:

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

Because v will be the parent of n for sure, since DFSUtil will be called for n just once given that we are checking if n is not visited.