Clonar un gráfico no dirigido – Part 1

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);
    }
}
Producción

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

Deja una respuesta

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