KLONIRAJTE NEUSMERJENI GRAF

Preizkusite na GfG Practice Klonirajte neusmerjeni graf' title=

Glede na a povezani neusmerjeni graf predstavljen s seznamom sosednosti adjList[][] z n vozlišča in m robovi, pri čemer ima vsako vozlišče a razločno oznako od 0 do n-1 in vsak adj[i] predstavlja seznam točk, povezanih z točko i.

Ustvari a klon grafa, kjer vsako vozlišče v grafu vsebuje celo število val in niz ( sosedje ) vozlišč ki vsebuje vozlišča, ki so sosednja trenutnemu vozlišču.

vozlišče razreda {
val: celo število
sosedje: seznam [vozlišče]
}

Vaša naloga je klonirati dani graf in vrniti referenco na klonirani graf.

Opomba: Če vrnete pravilno kopijo danega grafa, bo rezultat resničen; drugače, če je kopija napačna, bo natisnjena napačna.

Primeri

Vnos: n = 4 adjList[][] = [[1 2] [0 2] [0 1 3] [2]]
Izhod: res
Pojasnilo:

Ker je klonirani graf identičen izvirniku, bo rezultat resničen.
Vnos: n = 3 adjList[][] = [[1 2] [0] [0]]
Izhod: res
Pojasnilo:
Ker je klonirani graf identičen izvirniku, bo rezultat resničen.

Kazalo vsebine

Zakaj moramo slediti obiskanim/kloniranim vozliščem?
Kako slediti obiskanim/kloniranim vozliščem?
Kako povezati vozlišča klonov?
Kako preveriti, ali je klonirani graf pravilen?
[Pristop 1] Uporaba prečkanja BFS - O(V+E) čas in O(V) prostor
[Pristop 2] Uporaba prečkanja DFS - O(V+E) čas in O(V) prostor

Zakaj moramo slediti obiskanim/kloniranim vozliščem?

Slediti moramo obiskanim ali kloniranim vozliščem, da se izognemo neskončni rekurziji in odvečnemu delu pri kloniranju grafa. Ker lahko grafi vsebujejo cikle (kjer lahko vozlišče kaže nazaj na predhodno obiskano vozlišče), ne da bi sledili vozliščem, ki smo jih že klonirali, bi funkcija kloniranja neskončno znova obiskovala ista vozlišča, kar bi povzročilo prelivanje sklada ali nepravilno podvajanje.

Kako slediti obiskanim/kloniranim vozliščem?

HashMap/Map je potreben za vzdrževanje vseh že ustvarjenih vozlišč. Shramba ključev : Referenca/naslov izvirnega vozlišča Zaloge vrednosti : Referenca/naslov kloniranega vozlišča Narejena je bila kopija vseh vozlišč grafa.

Kako povezati vozlišča klonov?

Med obiskom sosednjih oglišč a vozlišče v dobite ustrezen klon vozlišče za vas, recimo temu IN zdaj obiščite vsa sosednja vozlišča za v in za vsakega soseda poiščite ustrezno vozlišče klona (če ga ne najdete, ga ustvarite) in nato potisnite v sosednji vektor IN vozlišče.

Kako preveriti, ali je klonirani graf pravilen?

Izvedite prečkanje BFS na izvirnem grafu pred kloniranjem in nato znova na kloniranem grafu, ko je kloniranje končano. Med vsakim prehodom natisnite vrednost vsakega vozlišča skupaj z njegovim naslovom (ali referenco). Da preverite pravilnost kloniranja, primerjajte vrstni red vozlišč, obiskanih v obeh prehodih. Če se vrednosti vozlišč pojavljajo v istem vrstnem redu, vendar se njihovi naslovi (ali reference) razlikujejo, to potrjuje, da je bil graf uspešno in pravilno kloniran.

Raziščite, kako klon neusmerjenega grafa, vključno z grafi z več povezanimi komponentami z uporabo BFS ali DFS, da zagotovite popolno globoko kopijo vseh vozlišč in robov.

[Pristop 1] Uporaba prečkanja BFS - O(V+E) čas in O(V) prostor

Pri pristopu BFS se graf klonira iterativno z uporabo čakalne vrste. Začnemo s kloniranjem začetnega vozlišča in njegovo postavitvijo v čakalno vrsto. Ko obdelujemo vsako vozlišče iz čakalne vrste, obiščemo njegove sosede. Če sosed še ni bil kloniran, ustvarimo klon, ki ga shranimo v zemljevid in postavimo v čakalno vrsto za kasnejšo obdelavo. Nato dodamo klon soseda na seznam sosedov klonov trenutnega vozlišča. Ta proces se nadaljuje od ravni do ravni in zagotavlja, da so vsa vozlišča obiskana v vrstnem redu v širino. BFS je še posebej uporaben za izogibanje globoki rekurziji in učinkovito ravnanje z velikimi ali širokimi grafi.

C++

#include    #include  #include  #include  using namespace std; // Definition for a Node struct Node {  int val;  vector<Node*> neighbors; }; // Clone the graph  Node* cloneGraph(Node* node) {  if (!node) return nullptr;  map<Node* Node*> mp;  queue<Node*> q;    // Clone the source node  Node* clone = new Node();  clone->val = node->val;  mp[node] = clone;  q.push(node);  while (!q.empty()) {  Node* u = q.front();  q.pop();  for (auto neighbor : u->neighbors) {    // Clone neighbor if not already cloned  if (mp.find(neighbor) == mp.end()) {  Node* neighborClone = new Node();  neighborClone->val = neighbor->val;  mp[neighbor] = neighborClone;  q.push(neighbor);  }  // Link clone of neighbor to clone of current node  mp[u]->neighbors.push_back(mp[neighbor]);  }  }  return mp[node]; } // Build graph Node* buildGraph() {  Node* node1 = new Node(); node1->val = 0;  Node* node2 = new Node(); node2->val = 1;  Node* node3 = new Node(); node3->val = 2;  Node* node4 = new Node(); node4->val = 3;  node1->neighbors = {node2 node3};  node2->neighbors = {node1 node3};  node3->neighbors = {node1 node2 node4};  node4->neighbors = {node3};  return node1; }   // Compare two graphs for structural and value equality bool compareGraphs(Node* node1 Node* node2   map<Node* Node*>& visited) {  if (!node1 || !node2)   return node1 == node2;    if (node1->val != node2->val || node1 == node2)  return false;  visited[node1] = node2;  if (node1->neighbors.size() != node2->neighbors.size())   return false;  for (size_t i = 0; i < node1->neighbors.size(); ++i) {  Node* n1 = node1->neighbors[i];  Node* n2 = node2->neighbors[i];  if (visited.count(n1)) {  if (visited[n1] != n2)   return false;  } else {  if (!compareGraphs(n1 n2 visited))  return false;  }  }  return true; } // Driver Code int main() {  Node* original = buildGraph();  Node* cloned = cloneGraph(original);  map<Node* Node*> visited;  cout << (compareGraphs(original cloned visited) ?   'true' : 'false') << endl;  return 0; }

Java

import java.util.*; // Definition for a Node class Node {  public int val;  public ArrayList<Node> neighbors;  public Node() {  neighbors = new ArrayList<>();  }  public Node(int val) {  this.val = val;  neighbors = new ArrayList<>();  } } public class GfG {  // Clone the graph  public static Node cloneGraph(Node node) {  if (node == null) return null;  Map<Node Node> mp = new HashMap<>();  Queue<Node> q = new LinkedList<>();  // Clone the starting node  Node clone = new Node(node.val);  mp.put(node clone);  q.offer(node);  while (!q.isEmpty()) {  Node current = q.poll();  for (Node neighbor : current.neighbors) {  // Clone neighbor if it hasn't been cloned yet  if (!mp.containsKey(neighbor)) {  mp.put(neighbor new Node(neighbor.val));  q.offer(neighbor);  }  // Add the clone of the neighbor to the current node's clone  mp.get(current).neighbors.add(mp.get(neighbor));  }  }  return mp.get(node);  }  // Build graph  public static Node buildGraph() {  Node node1 = new Node(0);  Node node2 = new Node(1);  Node node3 = new Node(2);  Node node4 = new Node(3);  node1.neighbors.addAll(new ArrayList<>  (Arrays.asList(node2 node3)));  node2.neighbors.addAll(new ArrayList<>  (Arrays.asList(node1 node3)));  node3.neighbors.addAll(new ArrayList<>  (Arrays.asList(node1 node2 node4)));  node4.neighbors.addAll(new ArrayList<>  (Arrays.asList(node3)));  return node1;  }  // Compare two graphs for structure and value  public static boolean compareGraphs(Node n1 Node n2   HashMap<Node Node> visited) {  if (n1 == null || n2 == null)  return n1 == n2;  if (n1.val != n2.val || n1 == n2)  return false;  visited.put(n1 n2);  if (n1.neighbors.size() != n2.neighbors.size())  return false;  for (int i = 0; i < n1.neighbors.size(); i++) {  Node neighbor1 = n1.neighbors.get(i);  Node neighbor2 = n2.neighbors.get(i);  if (visited.containsKey(neighbor1)) {  if (visited.get(neighbor1) != neighbor2)  return false;  } else {  if (!compareGraphs(neighbor1 neighbor2 visited))  return false;  }  }  return true;  }  public static void main(String[] args) {  Node original = buildGraph();  Node cloned = cloneGraph(original);  boolean isEqual = compareGraphs(original cloned  new HashMap<>());  System.out.println(isEqual ? 'true' : 'false');  } }

Python

from collections import deque # Definition for a Node class Node: def __init__(self val=0): self.val = val self.neighbors = [] # Clone the graph def cloneGraph(node): if not node: return None # Map to hold original nodes as keys and their clones as values mp = {} # Initialize BFS queue q = deque([node]) # Clone the starting node mp[node] = Node(node.val) while q: current = q.popleft() for neighbor in current.neighbors: # If neighbor not cloned yet if neighbor not in mp: mp[neighbor] = Node(neighbor.val) q.append(neighbor) # Link clone of neighbor to the clone of the current node mp[current].neighbors.append(mp[neighbor]) return mp[node] # Build graph def buildGraph(): node1 = Node(0) node2 = Node(1) node3 = Node(2) node4 = Node(3) node1.neighbors = [node2 node3] node2.neighbors = [node1 node3] node3.neighbors = [node1 node2 node4] node4.neighbors = [node3] return node1 # Compare two graphs structurally and by values def compareGraphs(n1 n2 visited): if not n1 or not n2: return n1 == n2 if n1.val != n2.val or n1 is n2: return False visited[n1] = n2 if len(n1.neighbors) != len(n2.neighbors): return False for i in range(len(n1.neighbors)): neighbor1 = n1.neighbors[i] neighbor2 = n2.neighbors[i] if neighbor1 in visited: if visited[neighbor1] != neighbor2: return False else: if not compareGraphs(neighbor1 neighbor2 visited): return False return True # Driver if __name__ == '__main__': original = buildGraph() cloned = cloneGraph(original) result = compareGraphs(original cloned {}) print('true' if result else 'false')

using System; using System.Collections.Generic; // Definition for a Node public class Node {  public int val;  public List<Node> neighbors;  public Node() {  neighbors = new List<Node>();  }  public Node(int val) {  this.val = val;  neighbors = new List<Node>();  } } class GfG {    // Clone the graph   public static Node CloneGraph(Node node) {  if (node == null)   return null;  var mp = new Dictionary<Node Node>();  var q = new Queue<Node>();  // Clone the starting node  var clone = new Node(node.val);  mp[node] = clone;  q.Enqueue(node);  while (q.Count > 0) {  var current = q.Dequeue();  foreach (var neighbor in current.neighbors) {  // If neighbor not cloned clone it and enqueue  if (!mp.ContainsKey(neighbor)) {  mp[neighbor] = new Node(neighbor.val);  q.Enqueue(neighbor);  }  // Add clone of neighbor to clone of current  mp[current].neighbors.Add(mp[neighbor]);  }  }  return mp[node];  }  // Build graph  public static Node BuildGraph() {  var node1 = new Node(0);  var node2 = new Node(1);  var node3 = new Node(2);  var node4 = new Node(3);  node1.neighbors.AddRange(new[] { node2 node3 });  node2.neighbors.AddRange(new[] { node1 node3 });  node3.neighbors.AddRange(new[] { node1 node2 node4 });  node4.neighbors.AddRange(new[] { node3 });  return node1;  }  // Compare two graphs for structure and value  public static bool CompareGraphs(Node n1 Node n2 Dictionary<Node Node> visited) {  if (n1 == null || n2 == null)   return n1 == n2;    if (n1.val != n2.val || ReferenceEquals(n1 n2))   return false;  visited[n1] = n2;  if (n1.neighbors.Count != n2.neighbors.Count)   return false;  for (int i = 0; i < n1.neighbors.Count; i++) {  var neighbor1 = n1.neighbors[i];  var neighbor2 = n2.neighbors[i];  if (visited.ContainsKey(neighbor1)) {  if (!ReferenceEquals(visited[neighbor1] neighbor2))   return false;  } else {  if (!CompareGraphs(neighbor1 neighbor2 visited))  return false;  }  }  return true;  }  public static void Main() {  var original = BuildGraph();  var cloned = CloneGraph(original);  var visited = new Dictionary<Node Node>();  Console.WriteLine(CompareGraphs(original cloned visited)   ? 'true' : 'false');  } }

JavaScript

// Definition for a Node class Node {  constructor(val = 0) {  this.val = val;  this.neighbors = [];  } } // Clone the graph function cloneGraph(node) {  if (!node) return null;  const mp = new Map();  const q = [node];  // Clone the initial node  mp.set(node new Node(node.val));  while (q.length > 0) {  const current = q.shift();  for (const neighbor of current.neighbors) {  if (!mp.has(neighbor)) {  mp.set(neighbor new Node(neighbor.val));  q.push(neighbor);  }  // Link clone of neighbor to clone of current  mp.get(current).neighbors.push(mp.get(neighbor));  }  }  return mp.get(node); } // Build graph function buildGraph() {  const node1 = new Node(0);  const node2 = new Node(1);  const node3 = new Node(2);  const node4 = new Node(3);  node1.neighbors = [node2 node3];  node2.neighbors = [node1 node3];  node3.neighbors = [node1 node2 node4];  node4.neighbors = [node3];  return node1; } // Compare two graphs structurally and by value function compareGraphs(n1 n2 visited = new Map()) {  if (!n1 || !n2)   return n1 === n2;    if (n1.val !== n2.val || n1 === n2)   return false;  visited.set(n1 n2);  if (n1.neighbors.length !== n2.neighbors.length)   return false;  for (let i = 0; i < n1.neighbors.length; i++) {  const neighbor1 = n1.neighbors[i];  const neighbor2 = n2.neighbors[i];  if (visited.has(neighbor1)) {  if (visited.get(neighbor1) !== neighbor2)   return false;    } else {  if (!compareGraphs(neighbor1 neighbor2 visited))  return false;    }  }  return true; } // Driver const original = buildGraph(); const cloned = cloneGraph(original); const result = compareGraphs(original cloned); console.log(result ? 'true' : 'false');

Izhod

true

[Pristop 2] Uporaba prečkanja DFS - O(V+E) čas in O(V) prostor

Pri pristopu DFS je graf kloniran z uporabo rekurzije. Začnemo pri danem vozlišču in raziščemo, kolikor je mogoče, vzdolž vsake veje, preden se vrnemo nazaj. Zemljevid (ali slovar) se uporablja za sledenje že kloniranim vozliščem, da se prepreči večkratna obdelava istega vozlišča in za obravnavo ciklov. Ko prvič naletimo na vozlišče, ustvarimo njegov klon in ga shranimo v zemljevid. Nato za vsakega soseda tega vozlišča rekurzivno kloniramo in dodamo kloniranega soseda klonu trenutnega vozlišča. To zagotavlja, da so vsa vozlišča podrobno obiskana pred vrnitvijo in da je struktura grafa zvesto kopirana.

C++

#include    #include  #include  #include  using namespace std; // Definition for a Node struct Node {  int val;  vector<Node*> neighbors; }; // Map to hold original node to its copy unordered_map<Node* Node*> copies; // Function to clone the graph  Node* cloneGraph(Node* node) {    // If the node is NULL return NULL  if (!node) return NULL;  // If node is not yet cloned clone it  if (copies.find(node) == copies.end()) {  Node* clone = new Node();  clone->val = node->val;  copies[node] = clone;  // Recursively clone neighbors  for (Node* neighbor : node->neighbors) {  clone->neighbors.push_back(cloneGraph(neighbor));  }  }  // Return the clone  return copies[node]; } // Build graph Node* buildGraph() {  Node* node1 = new Node(); node1->val = 0;  Node* node2 = new Node(); node2->val = 1;  Node* node3 = new Node(); node3->val = 2;  Node* node4 = new Node(); node4->val = 3;  node1->neighbors = {node2 node3};  node2->neighbors = {node1 node3};  node3->neighbors = {node1node2 node4};  node4->neighbors = {node3};  return node1; } // Compare two graphs for structural and value equality bool compareGraphs(Node* node1 Node* node2 map<Node* Node*>& visited) {  if (!node1 || !node2)   return node1 == node2;  if (node1->val != node2->val || node1 == node2)  return false;  visited[node1] = node2;  if (node1->neighbors.size() != node2->neighbors.size())   return false;  for (size_t i = 0; i < node1->neighbors.size(); ++i) {  Node* n1 = node1->neighbors[i];  Node* n2 = node2->neighbors[i];  if (visited.count(n1)) {  if (visited[n1] != n2)   return false;  } else {  if (!compareGraphs(n1 n2 visited))  return false;  }  }  return true; } // Driver Code int main() {  Node* original = buildGraph();  // Clone the graph  Node* cloned = cloneGraph(original);  // Compare original and cloned graph  map<Node* Node*> visited;  cout << (compareGraphs(original cloned visited) ?   'true' : 'false') << endl;  return 0; }