Ya se ha discutido la clonación de una LinkedList y un Binary Tree con punteros aleatorios. La idea detrás de la clonación de un gráfico es bastante similar.
La idea es hacer un recorrido BFS del gráfico y, mientras visita un Node, hacer un Node clonado (una copia del Node original). Si se encuentra un Node que ya se visitó, entonces ya tiene un Node de clonación.
¿Cómo realizar un seguimiento de los Nodes visitados/clonados? Se requiere un HashMap/Map para mantener todos los Nodes que ya se han creado. Almacenes de claves : Referencia/Dirección del Node original Almacenes de valores : Referencia/Dirección del Node clonado Se ha realizado una copia de todos los Nodes del gráfico,
¿Cómo conectar Nodes clon? Mientras visita los vértices vecinos de un Node, obtiene el Node clonado correspondiente para usted, llamemos a ese cloneNodeU , ahora visite todos los Nodes vecinos para usted y para cada vecino busque el Node clonado correspondiente (si no se encuentra, cree uno) y luego presione en el vector vecino del Node cloneNodeU .
¿Cómo verificar si el gráfico clonado es correcto? Realice un recorrido BFS antes y después de la clonación del gráfico. En BFS transversal muestra el valor de un Node junto con su dirección/referencia. Compare el orden en que se muestran los Nodes, si los valores son iguales pero la dirección/referencia es diferente para ambos recorridos, entonces el gráfico clonado es correcto.
Implementación:
C++
// A C++ program to Clone an Undirected Graph
#include<bits/stdc++.h>
using namespace std;
struct GraphNode
{
int val;
//A neighbour vector which contains addresses to
//all the neighbours of a GraphNode
vector<GraphNode*> neighbours;
};
// A function which clones a Graph and
// returns the address to the cloned
// src node
GraphNode *cloneGraph(GraphNode *src)
{
//A Map to keep track of all the
//nodes which have already been created
map<GraphNode*, GraphNode*> m;
queue<GraphNode*> q;
// Enqueue src node
q.push(src);
GraphNode *node;
// Make a clone Node
node = new GraphNode();
node->val = src->val;
// Put the clone node into the Map
m[src] = node;
while (!q.empty())
{
//Get the front node from the queue
//and then visit all its neighbours
GraphNode *u = q.front();
q.pop();
vector<GraphNode *> v = u->neighbours;
int n = v.size();
for (int i = 0; i < n; i++)
{
// Check if this node has already been created
if (m[v[i]] == NULL)
{
// If not then create a new Node and
// put into the HashMap
node = new GraphNode();
node->val = v[i]->val;
m[v[i]] = node;
q.push(v[i]);
}
// add these neighbours to the cloned graph node
m[u]->neighbours.push_back(m[v[i]]);
}
}
// Return the address of cloned src Node
return m[src];
}
// Build the desired graph
GraphNode *buildGraph()
{
/*
Note : All the edges are Undirected
Given Graph:
1--2
| |
4--3
*/
GraphNode *node1 = new GraphNode();
node1->val = 1;
GraphNode *node2 = new GraphNode();
node2->val = 2;
GraphNode *node3 = new GraphNode();
node3->val = 3;
GraphNode *node4 = new GraphNode();
node4->val = 4;
vector<GraphNode *> v;
v.push_back(node2);
v.push_back(node4);
node1->neighbours = v;
v.clear();
v.push_back(node1);
v.push_back(node3);
node2->neighbours = v;
v.clear();
v.push_back(node2);
v.push_back(node4);
node3->neighbours = v;
v.clear();
v.push_back(node3);
v.push_back(node1);
node4->neighbours = v;
return node1;
}
// A simple bfs traversal of a graph to
// check for proper cloning of the graph
void bfs(GraphNode *src)
{
map<GraphNode*, bool> visit;
queue<GraphNode*> q;
q.push(src);
visit[src] = true;
while (!q.empty())
{
GraphNode *u = q.front();
cout << "Value of Node " << u->val << "\n";
cout << "Address of Node " <<u << "\n";
q.pop();
vector<GraphNode *> v = u->neighbours;
int n = v.size();
for (int i = 0; i < n; i++)
{
if (!visit[v[i]])
{
visit[v[i]] = true;
q.push(v[i]);
}
}
}
cout << endl;
}
// Driver program to test above function
int main()
{
GraphNode *src = buildGraph();
cout << "BFS Traversal before cloning\n";
bfs(src);
GraphNode *newsrc = cloneGraph(src);
cout << "BFS Traversal after cloning\n";
bfs(newsrc);
return 0;
}
Java
// Java program to Clone an Undirected Graph
import java.util.*;
// GraphNode class represents each
// Node of the Graph
class GraphNode
{
int val;
// A neighbour Vector which contains references to
// all the neighbours of a GraphNode
Vector<GraphNode> neighbours;
public GraphNode(int val)
{
this.val = val;
neighbours = new Vector<GraphNode>();
}
}
class Graph
{
// A method which clones the graph and
// returns the reference of new cloned source node
public GraphNode cloneGraph(GraphNode source)
{
Queue<GraphNode> q = new LinkedList<GraphNode>();
q.add(source);
// An HashMap to keep track of all the
// nodes which have already been created
HashMap<GraphNode,GraphNode> hm =
new HashMap<GraphNode,GraphNode>();
//Put the node into the HashMap
hm.put(source,new GraphNode(source.val));
while (!q.isEmpty())
{
// Get the front node from the queue
// and then visit all its neighbours
GraphNode u = q.poll();
// Get corresponding Cloned Graph Node
GraphNode cloneNodeU = hm.get(u);
if (u.neighbours != null)
{
Vector<GraphNode> v = u.neighbours;
for (GraphNode graphNode : v)
{
// Get the corresponding cloned node
// If the node is not cloned then we will
// simply get a null
GraphNode cloneNodeG = hm.get(graphNode);
// Check if this node has already been created
if (cloneNodeG == null)
{
q.add(graphNode);
// If not then create a new Node and
// put into the HashMap
cloneNodeG = new GraphNode(graphNode.val);
hm.put(graphNode,cloneNodeG);
}
// add the 'cloneNodeG' to neighbour
// vector of the cloneNodeG
cloneNodeU.neighbours.add(cloneNodeG);
}
}
}
// Return the reference of cloned source Node
return hm.get(source);
}
// Build the desired graph
public GraphNode buildGraph()
{
/*
Note : All the edges are Undirected
Given Graph:
1--2
| |
4--3
*/
GraphNode node1 = new GraphNode(1);
GraphNode node2 = new GraphNode(2);
GraphNode node3 = new GraphNode(3);
GraphNode node4 = new GraphNode(4);
Vector<GraphNode> v = new Vector<GraphNode>();
v.add(node2);
v.add(node4);
node1.neighbours = v;
v = new Vector<GraphNode>();
v.add(node1);
v.add(node3);
node2.neighbours = v;
v = new Vector<GraphNode>();
v.add(node2);
v.add(node4);
node3.neighbours = v;
v = new Vector<GraphNode>();
v.add(node3);
v.add(node1);
node4.neighbours = v;
return node1;
}
// BFS traversal of a graph to
// check if the cloned graph is correct
public void bfs(GraphNode source)
{
Queue<GraphNode> q = new LinkedList<GraphNode>();
q.add(source);
HashMap<GraphNode,Boolean> visit =
new HashMap<GraphNode,Boolean>();
visit.put(source,true);
while (!q.isEmpty())
{
GraphNode u = q.poll();
System.out.println("Value of Node " + u.val);
System.out.println("Address of Node " + u);
if (u.neighbours != null)
{
Vector<GraphNode> v = u.neighbours;
for (GraphNode g : v)
{
if (visit.get(g) == null)
{
q.add(g);
visit.put(g,true);
}
}
}
}
System.out.println();
}
}
// Driver code
class Main
{
public static void main(String args[])
{
Graph graph = new Graph();
GraphNode source = graph.buildGraph();
System.out.println("BFS traversal of a graph before cloning");
graph.bfs(source);
GraphNode newSource = graph.cloneGraph(source);
System.out.println("BFS traversal of a graph after cloning");
graph.bfs(newSource);
}
}
BFS Traversal before cloning Value of Node 1 Address of Node 0x1b6ce70 Value of Node 2 Address of Node 0x1b6cea0 Value of Node 4 Address of Node 0x1b6cf00 Value of Node 3 Address of Node 0x1b6ced0 BFS Traversal after cloning Value of Node 1 Address of Node 0x1b6e5a0 Value of Node 2 Address of Node 0x1b6e5d0 Value of Node 4 Address of Node 0x1b6e620 Value of Node 3 Address of Node 0x1b6e670
Clonar un gráfico no dirigido con múltiples componentes conectados Chirag Agarwal contribuye con este artículo . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org.
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