Рубрики

Клонировать неориентированный граф

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

Идея состоит в том, чтобы выполнить обход BFS графа и при посещении узла сделать его узел-клон (копию исходного узла). Если встречается узел, который уже посещен, то у него уже есть узел клона.

Как отслеживать посещенные / клонированные узлы?
HashMap / Map требуется для поддержания всех узлов, которые уже были созданы.
Ключевые магазины : Ссылка / Адрес оригинального узла
Значение магазинов : Ссылка / Адрес клонированного узла

Была сделана копия всех узлов графа, как соединить узлы клона?
Посещая соседние вершины узла u, вы получите соответствующий клонированный узел для u, давайте назовем этот cloneNodeU , теперь посетим все соседние узлы для u, и для каждого соседа найдите соответствующий узел клона (если не найден, создайте один), а затем нажмите на соседний вектор узла cloneNodeU .

Как проверить, является ли клонированный граф правильным?
Выполните обход BFS до и после клонирования графа. В обходе BFS отображается значение узла вместе с его адресом / ссылкой.
Сравните порядок, в котором отображаются узлы, если значения одинаковы, но адрес / ссылка отличаются для обоих обходов, чем клонированный график, является правильным.

C ++

// Программа на C ++ для клонирования неориентированного графа
#include<bits/stdc++.h>

using namespace std;

  

struct GraphNode

{

    int val;

  

    // Соседний вектор, который содержит адреса

    // все соседи GraphNode

    vector<GraphNode*> neighbours;

};

  
// Функция, которая клонирует график и
// возвращает адрес клонированному
// узел src
GraphNode *cloneGraph(GraphNode *src)
{

    // Карта для отслеживания всех

    // узлы, которые уже были созданы

    map<GraphNode*, GraphNode*> m;

    queue<GraphNode*> q;

  

    // ставим в очередь узел src

    q.push(src);

    GraphNode *node;

  

    // Сделать узел клона

    node = new GraphNode();

    node->val = src->val;

  

    // Поместить узел клона на карту

    m[src] = node;

    while (!q.empty())

    {

        // Получить передний узел из очереди

        // а затем посетить всех своих соседей

        GraphNode *u = q.front();

        q.pop();

        vector<GraphNode *> v = u->neighbours;

        int n = v.size();

        for (int i = 0; i < n; i++)

        {

            // Проверяем, был ли этот узел уже создан

            if (m[v[i]] == NULL)

            {

                // Если нет, то создайте новый узел и

                // положить в HashMap

                node = new GraphNode();

                node->val = v[i]->val;

                m[v[i]] = node;

                q.push(v[i]);

            }

  

            // добавляем этих соседей в клонированный узел графа

            m[u]->neighbours.push_back(m[v[i]]);

        }

    }

  

    // Возвращаем адрес клонированного узла src

    return m[src];

}

  
// Построить нужный график
GraphNode *buildGraph()
{

    / *

        Примечание: все края ненаправлены

        Данный график:

        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;

}

  
// Простой бфс обход графа в
// проверка правильности клонирования графа

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;

}

  
// Программа драйвера для проверки вышеуказанной функции

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-программа для клонирования неориентированного графа

import java.util.*;

  
// класс GraphNode представляет каждый
// Узел графика

class GraphNode

{

    int val;

  

    // соседний вектор, который содержит ссылки на

    // все соседи GraphNode

    Vector<GraphNode> neighbours;

    public GraphNode(int val)

    {

        this.val = val;

        neighbours = new Vector<GraphNode>();

    }

}

  

class Graph

{

    // Метод, который клонирует график и

    // возвращает ссылку на новый клонированный исходный узел

    public GraphNode cloneGraph(GraphNode source)

    {

        Queue<GraphNode> q = new LinkedList<GraphNode>();

        q.add(source);

  

        // HashMap для отслеживания всех

        // узлы, которые уже были созданы

        HashMap<GraphNode,GraphNode> hm =

                        new HashMap<GraphNode,GraphNode>();

  

        // Поместить узел в HashMap

        hm.put(source,new GraphNode(source.val));

  

        while (!q.isEmpty())

        {

            // Получить передний узел из очереди

            // а затем посетить всех своих соседей

            GraphNode u = q.poll();

  

            // Получить соответствующий узел клонированного графика

            GraphNode cloneNodeU = hm.get(u);

            if (u.neighbours != null)

            {

                Vector<GraphNode> v = u.neighbours;

                for (GraphNode graphNode : v)

                {

                    // Получить соответствующий клонированный узел

                    // Если узел не клонирован, тогда мы будем

                    // просто получить ноль

                    GraphNode cloneNodeG = hm.get(graphNode);

  

                    // Проверяем, был ли этот узел уже создан

                    if (cloneNodeG == null)

                    {

                        q.add(graphNode);

  

                        // Если нет, то создайте новый узел и

                        // положить в HashMap

                        cloneNodeG = new GraphNode(graphNode.val);

                        hm.put(graphNode,cloneNodeG);

                    }

  

                    // добавляем cloneNodeG к соседу

                    // вектор cloneNodeG

                    cloneNodeU.neighbours.add(cloneNodeG);

                }

            }

        }

  

        // Возвращаем ссылку на клонированный исходный узел

        return hm.get(source);

    }

  

    // Построить нужный график

    public GraphNode buildGraph()

    {

        / *

            Примечание: все края ненаправлены

            Данный график:

            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 графа до

    // проверка правильности клонированного графа

    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();

    }

}

  
// Код драйвера

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);

    }

}


Вывод на Java:

BFS traversal of a graph before cloning
Value of Node 1
Address of Node GraphNode@15db9742
Value of Node 2
Address of Node GraphNode@6d06d69c
Value of Node 4
Address of Node GraphNode@7852e922
Value of Node 3
Address of Node GraphNode@4e25154f

BFS traversal of a graph after cloning
Value of Node 1
Address of Node GraphNode@70dea4e
Value of Node 2
Address of Node GraphNode@5c647e05
Value of Node 4
Address of Node GraphNode@33909752
Value of Node 3
Address of Node GraphNode@55f96302

Вывод в C ++:

BFS Traversal before cloning
Value of Node 1
Address of Node 0x24ccc20
Value of Node 2
Address of Node 0x24ccc50
Value of Node 4
Address of Node 0x24cccb0
Value of Node 3
Address of Node 0x24ccc80

BFS Traversal after cloning
Value of Node 1
Address of Node 0x24cd030
Value of Node 2
Address of Node 0x24cd0e0
Value of Node 4
Address of Node 0x24cd170
Value of Node 3
Address of Node 0x24cd200

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

Эта статья предоставлена Чирагом Агарвалом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Клонировать неориентированный граф

0.00 (0%) 0 votes