Dado un gráfico no dirigido con múltiples componentes conectados, la tarea es clonar el gráfico. La clonación de un gráfico con un solo componente conectado se puede ver aquí .
Ejemplos:
An example of an undirected graph with 3 connected components:
Enfoque:
la idea es seguir el mismo enfoque publicado para clonar gráficos conectados , pero con cada Node para que podamos clonar gráficos con múltiples componentes conectados.
Vamos a usar una clase GraphNode y una clase Graph. La clase Graph es obligatoria, ya que podemos tener múltiples componentes conectados (ver el ejemplo anterior), y no podemos tratar con ellos teniendo solo un GraphNode como entrada. Para la clase Graph, lo que realmente necesitamos es una lista de GraphNodes. También es posible hacer una lista de Nodes en lugar de crear una clase, ambas formas funcionan.
Para realizar un seguimiento de los Nodes visitados, necesitamos una estructura de datos; un mapa es apropiado, ya que podemos mapear desde los Nodes «antiguos» a los «nuevos» (los clonados). Entonces, estamos definiendo una función principal, que crea el mapa y usa una función auxiliar para llenarlo. Una vez que se crea el mapa, se puede crear un nuevo gráfico utilizando los Nodes clonados en el mapa.
La función auxiliar va a poner conexiones entre Nodes (además de llenar el mapa). Como estamos tratando con un componente conectado completo, se seguirá un enfoque similar al BFS.
Note que en la función principal, no llamamos a la función auxiliar para cada Node en el gráfico; si el Node está almacenado en el mapa, significa que ya lo visitamos y tratamos con su componente conectado, por lo que no es necesario repetir los pasos nuevamente.
Para comprobar si el gráfico se ha clonado correctamente, podemos imprimir las direcciones de memoria de los Nodes y compararlas para ver si las hemos clonado o las hemos copiado.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// GraphNode class represents each
// Node of the Graph
class GraphNode
{
int data;
list<GraphNode *> children;
// Constructor to initialize the
// node with value
public:
GraphNode(int data)
{
this->data = data;
}
// Function to add a child to the
// current node
void addChild(GraphNode *node)
{
this->children.push_back(node);
}
// Function to return a list of children
// for the current node
list<GraphNode *> getChildren()
{
return children;
}
// Function to set the node's value
void setData(int data)
{
this->data = data;
}
// Function to return the node's value
int getData()
{
return data;
}
};
// Class to represent the graph
class Graph
{
list<GraphNode *> nodes;
public:
Graph(){}
// Constructor to set the graph's nodes
Graph(list<GraphNode *> nodes)
{
this->nodes = nodes;
}
// Function to add a node to the graph
void addNode(GraphNode *node)
{
this->nodes.push_back(node);
}
// Function to return the list of nodes
// for the graph
list<GraphNode *> getNodes()
{
return this->nodes;
}
};
class GFG{
// Function to clone the graph
// Function to clone the connected components
void cloneConnectedComponent(GraphNode *node,
map<GraphNode *,
GraphNode *> &map)
{
queue<GraphNode *> queue;
queue.push(node);
while (!queue.empty())
{
GraphNode *current = queue.front();
queue.pop();
GraphNode *currentCloned = NULL;
if (map.find(current) != map.end())
{
currentCloned = map[current];
}
else
{
currentCloned = new GraphNode(
current->getData());
map[current] = currentCloned;
}
list<GraphNode *> children = current->getChildren();
for(auto child : children)
{
if (map.find(child) != map.end())
{
currentCloned->addChild(map[child]);
}
else
{
GraphNode *childCloned = new GraphNode(
child->getData());
map[child] = childCloned;
currentCloned->addChild(childCloned);
queue.push(child);
}
}
}
}
public:
Graph *cloneGraph(Graph *graph)
{
map<GraphNode *, GraphNode *> mapp;
for(auto node : graph->getNodes())
{
if (mapp.find(node) == mapp.end())
cloneConnectedComponent(node, mapp);
}
Graph *cloned = new Graph();
for(auto current : mapp)
cloned->addNode(current.second);
return cloned;
}
// Function to build the graph
Graph *buildGraph()
{
// Create graph
Graph *g = new Graph();
// Adding nodes to the graph
GraphNode *g1 = new GraphNode(1);
g->addNode(g1);
GraphNode *g2 = new GraphNode(2);
g->addNode(g2);
GraphNode *g3 = new GraphNode(3);
g->addNode(g3);
GraphNode *g4 = new GraphNode(4);
g->addNode(g4);
GraphNode *g5 = new GraphNode(5);
g->addNode(g5);
GraphNode *g6 = new GraphNode(6);
g->addNode(g6);
// Adding edges
g1->addChild(g2);
g1->addChild(g3);
g2->addChild(g1);
g2->addChild(g4);
g3->addChild(g1);
g3->addChild(g4);
g4->addChild(g2);
g4->addChild(g3);
g5->addChild(g6);
g6->addChild(g5);
return g;
}
// Function to print the connected components
void printConnectedComponent(GraphNode *node,
set<GraphNode *> &visited)
{
if (visited.find(node) != visited.end())
return;
queue<GraphNode *> q;
q.push(node);
while (!q.empty())
{
GraphNode *currentNode = q.front();
q.pop();
if (visited.find(currentNode) != visited.end())
continue;
visited.insert(currentNode);
cout << "Node " << currentNode->getData()
<< " - " << currentNode << endl;
for(GraphNode *child : currentNode->getChildren())
{
cout << "\tNode " << child->getData()
<< " - " << child << endl;
q.push(child);
}
}
}
};
// Driver code
int main()
{
GFG *gfg = new GFG();
Graph *g = gfg->buildGraph();
// Original graph
cout << "\tINITIAL GRAPH\n";
set<GraphNode *> visited;
for(GraphNode *n : g->getNodes())
gfg->printConnectedComponent(n, visited);
// Cloned graph
cout << "\n\n\tCLONED GRAPH\n";
Graph *cloned = gfg->cloneGraph(g);
visited.clear();
for(GraphNode *node : cloned->getNodes())
gfg->printConnectedComponent(node, visited);
}
// This code is contributed by sanjeev2552
Java
// Java implementation of the approach
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
// Class to represent the graph
class Graph {
private List<GraphNode> nodes;
// Constructor to create an empty ArrayList
// to store the nodes of the graph
public Graph()
{
this.nodes = new ArrayList<GraphNode>();
}
// Constructor to set the graph's nodes
public Graph(List<GraphNode> nodes)
{
this.nodes = nodes;
this.nodes = new ArrayList<GraphNode>();
}
// Function to add a node to the graph
public void addNode(GraphNode node)
{
this.nodes.add(node);
}
// Function to return the list of nodes
// for the graph
public List<GraphNode> getNodes()
{
return this.nodes;
}
}
// GraphNode class represents each
// Node of the Graph
class GraphNode {
private int data;
private List<GraphNode> children;
// Constructor to initialize the node with value
public GraphNode(int data)
{
this.data = data;
this.children = new ArrayList<GraphNode>();
}
// Function to add a child to the current node
public void addChild(GraphNode node)
{
this.children.add(node);
}
// Function to return a list of children
// for the current node
public List<GraphNode> getChildren()
{
return children;
}
// Function to set the node's value
public void setData(int data)
{
this.data = data;
}
// Function to return the node's value
public int getData()
{
return data;
}
}
public class GFG {
// Function to clone the graph
public Graph cloneGraph(Graph graph)
{
Map<GraphNode, GraphNode> map
= new HashMap<GraphNode, GraphNode>();
for (GraphNode node : graph.getNodes()) {
if (!map.containsKey(node))
cloneConnectedComponent(node, map);
}
Graph cloned = new Graph();
for (GraphNode current : map.values())
cloned.addNode(current);
return cloned;
}
// Function to clone the connected components
private void cloneConnectedComponent(GraphNode node,
Map<GraphNode, GraphNode> map)
{
Queue<GraphNode> queue = new LinkedList<GraphNode>();
queue.add(node);
while (!queue.isEmpty()) {
GraphNode current = queue.poll();
GraphNode currentCloned = null;
if (map.containsKey(current)) {
currentCloned = map.get(current);
}
else {
currentCloned = new GraphNode(current.getData());
map.put(current, currentCloned);
}
List<GraphNode> children = current.getChildren();
for (GraphNode child : children) {
if (map.containsKey(child)) {
currentCloned.addChild(map.get(child));
}
else {
GraphNode childCloned
= new GraphNode(child.getData());
map.put(child, childCloned);
currentCloned.addChild(childCloned);
queue.add(child);
}
}
}
}
// Function to build the graph
public Graph buildGraph()
{
// Create graph
Graph g = new Graph();
// Adding nodes to the graph
GraphNode g1 = new GraphNode(1);
g.addNode(g1);
GraphNode g2 = new GraphNode(2);
g.addNode(g2);
GraphNode g3 = new GraphNode(3);
g.addNode(g3);
GraphNode g4 = new GraphNode(4);
g.addNode(g4);
GraphNode g5 = new GraphNode(5);
g.addNode(g5);
GraphNode g6 = new GraphNode(6);
g.addNode(g6);
// Adding edges
g1.addChild(g2);
g1.addChild(g3);
g2.addChild(g1);
g2.addChild(g4);
g3.addChild(g1);
g3.addChild(g4);
g4.addChild(g2);
g4.addChild(g3);
g5.addChild(g6);
g6.addChild(g5);
return g;
}
// Function to print the connected components
public void printConnectedComponent(GraphNode node,
Set<GraphNode> visited)
{
if (visited.contains(node))
return;
Queue<GraphNode> q = new LinkedList<GraphNode>();
q.add(node);
while (!q.isEmpty()) {
GraphNode currentNode = q.remove();
if (visited.contains(currentNode))
continue;
visited.add(currentNode);
System.out.println("Node "
+ currentNode.getData() + " - " + currentNode);
for (GraphNode child : currentNode.getChildren()) {
System.out.println("\tNode "
+ child.getData() + " - " + child);
q.add(child);
}
}
}
// Driver code
public static void main(String[] args)
{
GFG gfg = new GFG();
Graph g = gfg.buildGraph();
// Original graph
System.out.println("\tINITIAL GRAPH");
Set<GraphNode> visited = new HashSet<GraphNode>();
for (GraphNode n : g.getNodes())
gfg.printConnectedComponent(n, visited);
// Cloned graph
System.out.println("\n\n\tCLONED GRAPH\n");
Graph cloned = gfg.cloneGraph(g);
visited = new HashSet<GraphNode>();
for (GraphNode node : cloned.getNodes())
gfg.printConnectedComponent(node, visited);
}
}
Python3
# Python3 implementation of the approach
from collections import deque as dq
# GraphNode class represents each
# Node of the Graph
class GraphNode:
# Constructor to initialize the
# node with value
def __init__(self,data):
self.__data = data
self.__children=[]
# Function to add a child to the
# current node
def addChild(self,node):
self.__children.append(node)
# Function to return a list of children
# for the current node
def getChildren(self):
return self.__children
# Function to set the node's value
def setData(self,data):
self.__data = data
# Function to return the node's value
def getData(self):
return self.__data
# Class to represent the graph
class Graph:
# Constructor to set the graph's nodes
def __init__(self,nodes):
self.__nodes = nodes
# Function to add a node to the graph
def addNode(self,node):
self.__nodes.append(node)
# Function to return the list of nodes
# for the graph
def getNodes(self):
return self.__nodes
class GFG:
# Function to clone the connected components
def cloneConnectedComponent(self, node, mp):
queue=dq([node,])
while (queue):
current = queue.popleft()
currentCloned = None
if (current in mp):
currentCloned = mp[current]
else:
currentCloned = GraphNode(current.getData())
mp[current] = currentCloned
children = current.getChildren()
for child in children:
if (child in mp):
currentCloned.addChild(mp[child])
else:
childCloned = GraphNode(child.getData())
mp[child] = childCloned
currentCloned.addChild(childCloned)
queue.append(child)
# Function to clone the graph
def cloneGraph(self,graph):
mapp=dict()
for node in graph.getNodes():
if (node not in mapp):
self.cloneConnectedComponent(node, mapp)
cloned = Graph([])
for current in mapp:
cloned.addNode(mapp[current])
return cloned
# Function to build the graph
def buildGraph(self):
# Create graph
G = Graph([])
# Adding nodes to the graph
g1 = GraphNode(1)
G.addNode(g1)
g2 = GraphNode(2)
G.addNode(g2)
g3 = GraphNode(3)
G.addNode(g3)
g4 = GraphNode(4)
G.addNode(g4)
g5 = GraphNode(5)
G.addNode(g5)
g6 = GraphNode(6)
G.addNode(g6)
# Adding edges
g1.addChild(g2)
g1.addChild(g3)
g2.addChild(g1)
g2.addChild(g4)
g3.addChild(g1)
g3.addChild(g4)
g4.addChild(g2)
g4.addChild(g3)
g5.addChild(g6)
g6.addChild(g5)
return G
# Function to print the connected components
def printConnectedComponent(self,node, visited):
if (node in visited):
return
q=dq([node,])
while (q):
currentNode = q.popleft()
if (currentNode in visited):
continue
visited.add(currentNode)
print("Node {} - {}".format(currentNode.getData(),hex(id(currentNode))))
for child in currentNode.getChildren():
print("\tNode {} - {}".format(child.getData(),hex(id(child))))
q.append(child)
# Driver code
if __name__ == '__main__':
gfg = GFG()
g = gfg.buildGraph()
# Original graph
print("\tINITIAL GRAPH")
visited=set()
for n in g.getNodes():
gfg.printConnectedComponent(n, visited)
# Cloned graph
print("\n\n\tCLONED GRAPH")
cloned = gfg.cloneGraph(g)
visited.clear()
for node in cloned.getNodes():
gfg.printConnectedComponent(node, visited)
# This code is contributed by Amartya Ghosh
Producción:
INITIAL GRAPH
Node 1 - GraphNode@232204a1
Node 2 - GraphNode@4aa298b7
Node 3 - GraphNode@7d4991ad
Node 2 - GraphNode@4aa298b7
Node 1 - GraphNode@232204a1
Node 4 - GraphNode@28d93b30
Node 3 - GraphNode@7d4991ad
Node 1 - GraphNode@232204a1
Node 4 - GraphNode@28d93b30
Node 4 - GraphNode@28d93b30
Node 2 - GraphNode@4aa298b7
Node 3 - GraphNode@7d4991ad
Node 5 - GraphNode@1b6d3586
Node 6 - GraphNode@4554617c
Node 6 - GraphNode@4554617c
Node 5 - GraphNode@1b6d3586
CLONED GRAPH
Node 1 - GraphNode@74a14482
Node 2 - GraphNode@1540e19d
Node 3 - GraphNode@677327b6
Node 2 - GraphNode@1540e19d
Node 1 - GraphNode@74a14482
Node 4 - GraphNode@14ae5a5
Node 3 - GraphNode@677327b6
Node 1 - GraphNode@74a14482
Node 4 - GraphNode@14ae5a5
Node 4 - GraphNode@14ae5a5
Node 2 - GraphNode@1540e19d
Node 3 - GraphNode@677327b6
Node 6 - GraphNode@7f31245a
Node 5 - GraphNode@6d6f6e28
Node 5 - GraphNode@6d6f6e28
Node 6 - GraphNode@7f31245a
Complejidad temporal : O(V + E) donde V y E son los números de vértices y aristas en el gráfico respectivamente.
Espacio Auxiliar : O(V + E).