Impresión de tiempos previos y posteriores a la visita en DFS de un gráfico

La primera búsqueda en profundidad (DFS) marca todos los vértices de un gráfico como visitados. Entonces, para hacer que DFS sea útil, también se puede almacenar información adicional. Por ejemplo, el orden en que se visitan los vértices mientras se ejecuta DFS. 

Los números previos a la visita y posteriores a la visita son la información adicional que se puede almacenar mientras se ejecuta un DFS en un gráfico y que resulta ser realmente útil. El número previo a la visita indica el momento en que el Node ingresa a la pila de recursividad y el número posterior a la visita indica el momento en que el Node sale de la pila recursiva de DFS.

Ejemplo: 

Los números escritos entre paréntesis indican [Número previo a la visita, Número posterior a la visita].

Los números Pre y Post se utilizan ampliamente en algoritmos gráficos . Por ejemplo, se pueden usar para averiguar si un Node en particular se encuentra en el subárbol de otro Node
Para averiguar si u se encuentra en el subárbol de v o no, simplemente comparamos el número anterior y posterior de u y v. Si pre[u] > pre[v] y post[u] < post[v] entonces u miente en el subárbol de v, de lo contrario no. Puede ver el ejemplo anterior para obtener más aclaraciones. 
 

Los números previos a la visita y posteriores a la visita se pueden encontrar mediante DFS simple. Tomaremos dos arrays, una para almacenar números previos y otra para números posteriores, y tomaremos una variable que realizará un seguimiento del tiempo. La implementación del mismo se presenta a continuación: 

C++

#include <bits/stdc++.h>
using namespace std;
 
// Variable to keep track of time
int Time = 1;
 
// Function to perform DFS starting from node u
void dfs(int u, vector<vector<int>> aList,
                       vector<int> &pre,
                       vector<int> &post,
                       vector<int> &vis)
{
     
    // Storing the pre number whenever
    // the node comes into recursion stack
    pre[u] = Time;
 
    // Increment time
    Time++;
    vis[u] = 1;
     
    for(int v : aList[u])
    {
        if (vis[v] == 0)
            dfs(v, aList, pre, post, vis);
    }
 
    // Storing the post number whenever
    // the node goes out of recursion stack
    post[u] = Time;
    Time++;
}
 
// Driver Code   
int main()
{
     
    // Number of nodes in graph
    int n = 6;
 
    // Adjacency list
    vector<vector<int>> aList(n + 1);
     
    vector<int> pre(n + 1);
    vector<int> post(n + 1);
 
    // Visited array
    vector<int> vis(n + 1);
 
    // Edges
    aList[1].push_back(2);
    aList[2].push_back(1);
    aList[2].push_back(4);
    aList[4].push_back(2);
    aList[1].push_back(3);
    aList[3].push_back(1);
    aList[3].push_back(4);
    aList[4].push_back(3);
    aList[3].push_back(5);
    aList[5].push_back(3);
    aList[5].push_back(6);
    aList[6].push_back(5);
 
    // DFS starting at Node 1
    dfs(1, aList, pre, post, vis);
 
    // Number of nodes in graph
    for(int i = 1; i <= n; i++)
        cout << "Node " << i << " Pre number "
             << pre[i] << " Post number "
             << post[i] << endl;
 
    return 0;
}
 
// This code is contributed by divyesh072019

Java

import java.util.*;
public class GFG {
 
    // Variable to keep track of time
    static int time = 1;
 
    // Function to perform DFS starting from node u
    static void dfs(int u, ArrayList<ArrayList<Integer> > aList,
                    int pre[], int post[], int vis[])
    {
 
        // Storing the pre number whenever
        // the node comes into recursion stack
        pre[u] = time;
 
        // Increment time
        time++;
        vis[u] = 1;
        for (int v : aList.get(u)) {
            if (vis[v] == 0)
                dfs(v, aList, pre, post, vis);
        }
 
        // Storing the post number whenever
        // the node goes out of recursion stack
        post[u] = time;
        time++;
    }
 
    // Driver code
    public static void main(String args[])
    {
 
        // Number of nodes in graph
        int n = 6;
 
        // Adjacency list
        ArrayList<ArrayList<Integer> > aList
            = new ArrayList<ArrayList<Integer> >(n + 1);
        for (int i = 1; i <= n; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            aList.add(list);
        }
        aList.add(new ArrayList<Integer>());
        int pre[] = new int[n + 1];
        int post[] = new int[n + 1];
 
        // Visited array
        int vis[] = new int[n + 1];
 
        // Edges
        aList.get(1).add(2);
        aList.get(2).add(1);
        aList.get(2).add(4);
        aList.get(4).add(2);
        aList.get(1).add(3);
        aList.get(3).add(1);
        aList.get(3).add(4);
        aList.get(4).add(3);
        aList.get(3).add(5);
        aList.get(5).add(3);
        aList.get(5).add(6);
        aList.get(6).add(5);
 
        // DFS starting at Node 1
        dfs(1, aList, pre, post, vis);
 
        // Number of nodes in graph
        for (int i = 1; i <= n; i++)
            System.out.println("Node " + i + " Pre number "
                               + pre[i] + " Post number " + post[i]);
    }
}

Python3

# Variable to keep track of time
time = 1
 
# Function to perform DFS starting
# from node u
def dfs(u, aList, pre, post, vis):
     
    global time
     
    # Storing the pre number whenever
    # the node comes into recursion stack
    pre[u] = time
 
    # Increment time
    time += 1
     
    vis[u] = 1
     
    for v in aList[u]:
        if (vis[v] == 0):
            dfs(v, aList, pre, post, vis)
             
    # Storing the post number whenever
    # the node goes out of recursion stack
    post[u] = time
    time += 1
 
# Driver code
if __name__=='__main__':
     
    # Number of nodes in graph
    n = 6
 
    # Adjacency list
    aList = [[] for i in range(n + 1)]
     
    pre = [0 for i in range(n + 1)]
    post = [0 for i in range(n + 1)]
 
    # Visited array
    vis = [0 for i in range(n + 1)]
     
    # Edges
    aList[1].append(2)
    aList[2].append(1)
    aList[2].append(4)
    aList[4].append(2)
    aList[1].append(3)
    aList[3].append(1)
    aList[3].append(4)
    aList[4].append(3)
    aList[3].append(5)
    aList[5].append(3)
    aList[5].append(6)
    aList[6].append(5)
 
    # DFS starting at Node 1
    dfs(1, aList, pre, post, vis)
 
    # Number of nodes in graph
    for i in range(1, n + 1):
        print("Node " + str(i) +
              " Pre number " + str(pre[i]) +
              " Post number " + str(post[i]))
 
# This code is contributed by rutvik_56

C#

using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
  
// Variable to keep track of time
static int time = 1;
 
// Function to perform DFS starting from node u
static void dfs(int u, ArrayList aList,
                int []pre, int []post,
                int []vis)
{
     
    // Storing the pre number whenever
    // the node comes into recursion stack
    pre[u] = time;
 
    // Increment time
    time++;
    vis[u] = 1;
     
    foreach(int v in (ArrayList)aList[u])
    {
        if (vis[v] == 0)
            dfs(v, aList, pre, post, vis);
    }
 
    // Storing the post number whenever
    // the node goes out of recursion stack
    post[u] = time;
    time++;
}
 
// Driver code
public static void Main(string []args)
{
     
    // Number of nodes in graph
    int n = 6;
 
    // Adjacency list
    ArrayList aList = new ArrayList(n + 1);
     
    for(int i = 1; i <= n; i++)
    {
        ArrayList list = new ArrayList();
        aList.Add(list);
    }
    aList.Add(new ArrayList());
    int []pre = new int[n + 1];
    int []post = new int[n + 1];
 
    // Visited array
    int []vis = new int[n + 1];
 
    // Edges
    ((ArrayList)aList[1]).Add(2);
    ((ArrayList)aList[2]).Add(1);
    ((ArrayList)aList[2]).Add(4);
    ((ArrayList)aList[4]).Add(2);
    ((ArrayList)aList[1]).Add(3);
    ((ArrayList)aList[3]).Add(1);
    ((ArrayList)aList[3]).Add(4);
    ((ArrayList)aList[4]).Add(3);
    ((ArrayList)aList[3]).Add(5);
    ((ArrayList)aList[5]).Add(3);
    ((ArrayList)aList[5]).Add(6);
    ((ArrayList)aList[6]).Add(5);
 
    // DFS starting at Node 1
    dfs(1, aList, pre, post, vis);
 
    // Number of nodes in graph
    for(int i = 1; i <= n; i++)
        Console.WriteLine("Node " + i +
                          " Pre number " + pre[i] +
                          " Post number " + post[i]);
}
}
 
// This code is contributed by pratham76

Javascript

<script>
    // Variable to keep track of time
    let time = 1;
 
    // Function to perform DFS starting
    // from node u
    function dfs(u, aList, pre, post, vis)
    {
     
        // Storing the pre number whenever
        // the node comes into recursion stack
        pre[u] = time;
 
        // Increment time
        time += 1;
 
        vis[u] = 1;
 
        for(let v = 0; v < aList[u].length; v++)
        {
            if (vis[aList[u][v]] == 0)
                dfs(aList[u][v], aList, pre, post, vis);
        }
 
        // Storing the post number whenever
        // the node goes out of recursion stack
        post[u] = time;
        time += 1;
   }
    
  // Number of nodes in graph
  let n = 6;
 
  // Adjacency list
  let aList = [];
  for(let i = 0; i < (n + 1); i++)
  {
      aList.push([]);
  }
 
  let pre = new Array(n+1);
  let post = new Array(n+1);
  pre.fill(0);
  post.fill(0);
 
  // Visited array
  let vis = new Array(n+1);
  vis.fill(0);
 
  // Edges
  aList[1].push(2);
  aList[2].push(1);
  aList[2].push(4);
  aList[4].push(2);
  aList[1].push(3);
  aList[3].push(1);
  aList[3].push(4);
  aList[4].push(3);
  aList[3].push(5);
  aList[5].push(3);
  aList[5].push(6);
  aList[6].push(5);
 
  // DFS starting at Node 1
  dfs(1, aList, pre, post, vis);
 
  // Number of nodes in graph
  for(let i = 1; i < n + 1; i++)
  {
    document.write("Node " + i +
          " Pre number " + pre[i] +
          " Post number " + post[i] + "</br>")
  }
  
 // This code is contributed by suresh07.
</script>
Producción: 

Node 1 Pre number 1 Post number 12
Node 2 Pre number 2 Post number 11
Node 3 Pre number 4 Post number 9
Node 4 Pre number 3 Post number 10
Node 5 Pre number 5 Post number 8
Node 6 Pre number 6 Post number 7

 

Publicación traducida automáticamente

Artículo escrito por Amol_Pratap y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *