Un gráfico acíclico dirigido (DAG) es un gráfico que no contiene un ciclo y tiene bordes dirigidos. Nos dan un DAG, necesitamos clonarlo, es decir, crear otro gráfico que tenga una copia de sus vértices y aristas que los conectan.
Ejemplos:
Input : 0 - - - > 1 - - - -> 4 | / \ ^ | / \ | | / \ | | / \ | | / \ | | / \ | v v v | 2 - - - - - - - - -> 3 Output : Printing the output of the cloned graph gives: 0-1 1-2 2-3 3-4 1-3 1-4 0-2
Para clonar un DAG sin almacenar el propio gráfico dentro de un hash (o diccionario en Python). Para clonar, básicamente hacemos un recorrido primero en profundidad de los Nodes, tomando el valor del Node original e inicializando nuevos Nodes vecinos con el mismo valor, haciendo recursivamente, hasta que el gráfico original se atraviesa por completo. A continuación se muestra el enfoque recursivo para clonar un DAG (en Python). Hacemos uso de listas dinámicas en Python, la operación de agregar a esta lista ocurre en tiempo constante, por lo tanto, la inicialización rápida y eficiente del gráfico.
Implementación:
C++14
// C++ program to clone a directed acyclic graph.
#include <bits/stdc++.h>
using namespace std;
// Class to create a new graph node
class Node
{
public:
int key;
vector<Node *> adj;
// key is the value of the node
// adj will be holding a dynamic
// list of all Node type neighboring
// nodes
Node(int key)
{
this->key = key;
}
};
// Function to print a graph,
// depth-wise, recursively
void printGraph(Node *startNode,
vector<bool> &visited)
{
// Visit only those nodes who have any
// neighboring nodes to be traversed
if (!startNode->adj.empty())
{
// Loop through the neighboring nodes
// of this node. If source node not already
// visited, print edge from source to
// neighboring nodes. After visiting all
// neighbors of source node, mark its visited
// flag to true
for(auto i : startNode->adj)
{
if (!visited[startNode->key])
{
cout << "edge " << startNode
<< "-" << i
<< ":" << startNode->key
<< "-" << i->key
<< endl;
if (!visited[i->key])
{
printGraph(i, visited);
visited[i->key] = true;
}
}
}
}
}
// Function to clone a graph. To do this, we
// start reading the original graph depth-wise,
// recursively. If we encounter an unvisited
// node in original graph, we initialize a
// new instance of Node for cloned graph with
// key of original node
Node *cloneGraph(Node *oldSource,
Node *newSource,
vector<bool> &visited)
{
Node *clone = NULL;
if (!visited[oldSource->key] &&
!oldSource->adj.empty())
{
for(auto old : oldSource->adj)
{
// Below check is for backtracking, so new
// nodes don't get initialized everytime
if (clone == NULL ||
(clone != NULL &&
clone->key != old->key))
clone = new Node(old->key);
newSource->adj.push_back(clone);
cloneGraph(old, clone, visited);
// Once, all neighbors for that particular node
// are created in cloned graph, code backtracks
// and exits from that node, mark the node as
// visited in original graph, and traverse the
// next unvisited
visited[old->key] = true;
}
}
return newSource;
}
// Driver Code
int main()
{
Node *n0 = new Node(0);
Node *n1 = new Node(1);
Node *n2 = new Node(2);
Node *n3 = new Node(3);
Node *n4 = new Node(4);
n0->adj.push_back(n1);
n0->adj.push_back(n2);
n1->adj.push_back(n2);
n1->adj.push_back(n3);
n1->adj.push_back(n4);
n2->adj.push_back(n3);
n3->adj.push_back(n4);
// Flag to check if a node is already visited.
// Stops indefinite looping during recursion
vector<bool> visited(5, false);
cout << "Graph Before Cloning:-\n";
printGraph(n0, visited);
visited = { false, false, false, false, false };
cout << "\nGraph Before Starts:-\n";
Node *clonedGraphHead = cloneGraph(
n0, new Node(n0->key), visited);
cout << "Cloning Process Completes.\n";
visited = { false, false, false, false, false };
cout << "\nGraph After Cloning:-\n";
printGraph(clonedGraphHead, visited);
return 0;
}
// This code is contributed by sanjeev2552
Java
// Java program to clone a directed acyclic graph.
import java.util.*;
class GFG{
// Class to create a new graph node
static class Node
{
int key;
ArrayList<Node> adj = new ArrayList<Node>();
// key is the value of the node
// adj will be holding a dynamic
// list of all Node type neighboring
// nodes
Node(int key)
{
this.key = key;
}
}
// Function to print a graph,
// depth-wise, recursively
static void printGraph(Node startNode,
boolean[] visited)
{
// Visit only those nodes who have any
// neighboring nodes to be traversed
if (!startNode.adj.isEmpty())
{
// Loop through the neighboring nodes
// of this node. If source node not already
// visited, print edge from source to
// neighboring nodes. After visiting all
// neighbors of source node, mark its visited
// flag to true
for(Node i : startNode.adj)
{
if (!visited[startNode.key])
{
System.out.println("edge " + startNode +
"-" + i + ":" + startNode.key +
"-" + i.key);
if (!visited[i.key])
{
printGraph(i, visited);
visited[i.key] = true;
}
}
}
}
}
// Function to clone a graph. To do this, we
// start reading the original graph depth-wise,
// recursively. If we encounter an unvisited
// node in original graph, we initialize a
// new instance of Node for cloned graph with
// key of original node
static Node cloneGraph(Node oldSource,
Node newSource,
boolean[] visited)
{
Node clone = null;
if (!visited[oldSource.key] &&
!oldSource.adj.isEmpty())
{
for(Node old : oldSource.adj)
{
// Below check is for backtracking, so new
// nodes don't get initialized everytime
if (clone == null ||
(clone != null &&
clone.key != old.key))
clone = new Node(old.key);
newSource.adj.add(clone);
cloneGraph(old, clone, visited);
// Once, all neighbors for that particular node
// are created in cloned graph, code backtracks
// and exits from that node, mark the node as
// visited in original graph, and traverse the
// next unvisited
visited[old.key] = true;
}
}
return newSource;
}
// Driver Code
public static void main(String[] args)
{
Node n0 = new Node(0);
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
n0.adj.add(n1);
n0.adj.add(n2);
n1.adj.add(n2);
n1.adj.add(n3);
n1.adj.add(n4);
n2.adj.add(n3);
n3.adj.add(n4);
// Flag to check if a node is already visited.
// Stops indefinite looping during recursion
boolean visited[] = new boolean[5];
System.out.println("Graph Before Cloning:-");
printGraph(n0, visited);
Arrays.fill(visited, false);
System.out.println("\nCloning Process Starts");
Node clonedGraphHead = cloneGraph(
n0, new Node(n0.key), visited);
System.out.println("Cloning Process Completes.");
Arrays.fill(visited, false);
System.out.println("\nGraph After Cloning:-");
printGraph(clonedGraphHead, visited);
}
}
// This code is contributed by adityapande88
Python3
# Python program to clone a directed acyclic graph.
# Class to create a new graph node
class Node():
# key is the value of the node
# adj will be holding a dynamic
# list of all Node type neighboring
# nodes
def __init__(self, key = None, adj = None):
self.key = key
self.adj = adj
# Function to print a graph, depth-wise, recursively
def printGraph(startNode, visited):
# Visit only those nodes who have any
# neighboring nodes to be traversed
if startNode.adj is not None:
# Loop through the neighboring nodes
# of this node. If source node not already
# visited, print edge from source to
# neighboring nodes. After visiting all
# neighbors of source node, mark its visited
# flag to true
for i in startNode.adj:
if visited[startNode.key] == False :
print("edge %s-%s:%s-%s"%(hex(id(startNode)), hex(id(i)), startNode.key, i.key))
if visited[i.key] == False:
printGraph(i, visited)
visited[i.key] = True
# Function to clone a graph. To do this, we start
# reading the original graph depth-wise, recursively
# If we encounter an unvisited node in original graph,
# we initialize a new instance of Node for
# cloned graph with key of original node
def cloneGraph(oldSource, newSource, visited):
clone = None
if visited[oldSource.key] is False and oldSource.adj is not None:
for old in oldSource.adj:
# Below check is for backtracking, so new
# nodes don't get initialized everytime
if clone is None or(clone is not None and clone.key != old.key):
clone = Node(old.key, [])
newSource.adj.append(clone)
cloneGraph(old, clone, visited)
# Once, all neighbors for that particular node
# are created in cloned graph, code backtracks
# and exits from that node, mark the node as
# visited in original graph, and traverse the
# next unvisited
visited[old.key] = True
return newSource
# Creating DAG to be cloned
# In Python, we can do as many assignments of
# variables in one single line by using commas
n0, n1, n2 = Node(0, []), Node(1, []), Node(2, [])
n3, n4 = Node(3, []), Node(4)
n0.adj.append(n1)
n0.adj.append(n2)
n1.adj.append(n2)
n1.adj.append(n3)
n1.adj.append(n4)
n2.adj.append(n3)
n3.adj.append(n4)
# flag to check if a node is already visited.
# Stops indefinite looping during recursion
visited = [False]* (5)
print("Graph Before Cloning:-")
printGraph(n0, visited)
visited = [False]* (5)
print("\nCloning Process Starts")
clonedGraphHead = cloneGraph(n0, Node(n0.key, []), visited)
print("Cloning Process Completes.")
visited = [False]*(5)
print("\nGraph After Cloning:-")
printGraph(clonedGraphHead, visited)
Producción
Graph Before Cloning:- edge 0x1017e70-0x1017ea0:0-1 edge 0x1017ea0-0x1017ed0:1-2 edge 0x1017ed0-0x1017f00:2-3 edge 0x1017f00-0x1017f30:3-4 edge 0x1017ea0-0x1017f00:1-3 edge 0x1017ea0-0x1017f30:1-4 edge 0x1017e70-0x1017ed0:0-2 Graph Before Starts:- Cloning Process Completes. Graph After Cloning:- edge 0x1019020-0x1019050:0-1 edge 0x1019050-0x10190a0:1-2 edge 0x10190a0-0x10190f0:2-3 edge 0x10190f0-0x1019140:3-4 edge 0x1019050-0x1019190:1-3 edge 0x1019050-0x10191e0:1-4 edge 0x1019020-0x1019240:0-2
La creación del DAG agregando bordes adyacentes al vértice ocurre en tiempo O(1). La clonación del gráfico requiere un tiempo O(E+V).
Este artículo es una contribución de Raveena . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Artículo relacionado: Clonar un gráfico no dirigido
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA