Клонировать неориентированный граф с несколькими связными компонентами

Опубликовано: 14 Января, 2022

Учитывая неориентированный граф с несколькими связными компонентами, задача состоит в том, чтобы клонировать граф. Клонирование графа с одним компонентом связности можно увидеть здесь.

Примеры:

 Пример неориентированного графа 
с 3 подключенными компонентами:

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:
Идея состоит в том, чтобы следовать тому же подходу, что и для клонирования связного графа, но с каждым узлом, чтобы мы могли клонировать графы с несколькими связными компонентами.

Мы собираемся использовать класс GraphNode и класс Graph. Класс Graph является обязательным, поскольку у нас может быть несколько связанных компонентов (см. Пример выше), и мы не можем иметь дело с ними, имея только GraphNode в качестве входных данных. Для класса Graph нам действительно нужен список GraphNodes. Также возможно составить список узлов вместо создания класса, работают оба способа.

Чтобы отслеживать посещенные узлы, нам нужна структура данных; карта является подходящей, поскольку мы можем отображать «старые» узлы в «новые» (клонированные). Итак, мы определяем основную функцию, которая создает карту и использует вспомогательную функцию для ее заполнения. После создания карты можно создать новый граф, используя клонированные узлы на карте.
Вспомогательная функция будет устанавливать связи между узлами (помимо заполнения карты). Поскольку мы имеем дело со всем подключенным компонентом, мы будем придерживаться аналогичного подхода к BFS.

Обратите внимание, что в основной функции мы не вызываем вспомогательную функцию для каждого узла в Graph; если узел хранится на карте, это означает, что мы уже посетили его и разобрались с его подключенным компонентом, поэтому нет необходимости повторять шаги снова.
Чтобы проверить, правильно ли был клонирован граф, мы можем распечатать адреса памяти узлов и сравнить их, чтобы увидеть, клонировали ли мы их или скопировали.

Below is the implementation of the above approach: 

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 << " Node " << child->getData()
                 << " - " << child << endl;
            q.push(child);
        }
    }
}
};
 
// Driver code
int main()
{
    GFG *gfg = new GFG();
    Graph *g = gfg->buildGraph();
     
    // Original graph
    cout << " INITIAL GRAPH ";
    set<GraphNode *> visited;
    for(GraphNode *n : g->getNodes())
        gfg->printConnectedComponent(n, visited);
     
    // Cloned graph
    cout << " CLONED GRAPH ";
    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
   &nbs
Алгоритмы Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023