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