Qrafik Klonlama

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Qrafik Klonlama nədir?

Bu gün yanımızda yönləndirilməmiş bir istinad var grafik. Nə etməliyik? Təqdim olunan dərin bir nüsxə qaytarılır graph.

Gəlin quruluşa baxaq:

Sinif Nodu:

Bu məlumat dəyərindən və bu sinifin hər bir obyekti ilə əlaqəli qonşulardan ibarətdir. Buna uyğun olaraq obyektlər / yeni qovşaqlar yaratmaq üçün bir neçə metod var.

class Node {
    public int val;
    public List<Node> neighbors;
    
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

Bizə verilən düyün həmişə kök düyün olacaqdır. Bir istinad / nüsxəni kökünə qaytarmaq bizə verdiyimiz qrafın klonunu qaytarmağa kömək edəcəkdir.

Nümunə sınaq işi:

Pin

Giriş: [[1,2], [2,3], [3,4], [4,5], [1,2]]

Output :  [[1,2],[2,3],[3,4],[4,5],[1,2]]

Klon buna bənzər bir şey göstərməlidir

Pin

yəni eyni dəyərlərə malik olan qovşaqların surətindən ibarətdir.

İmtina: Eyni qrafiki qaytarmayın

Həll

Genişlik-İlk Axtarış və HashMap istifadə

BFS istifadə edərək keçə bilərik və orijinal və klon qovşaqlarının xəritəsini saxlamaq üçün bir HashMap saxlaya bilərik.

Psevdokod

• Bir hashmap yaradın
• Kök qovşağını və surətini hashmap-ə əlavə edin
• Kök nodu yığına qoyun
• Qonşuların arasından keçin və yuxarıdakı prosesi təkrarlayın
• Hər qovşaq üçün qonşuları əlavə edin
• Yuxarıdakı prosesi növbə boşalana qədər təkrarlamağa davam edin

Daha çox istinad üçün axtarış BFS: Bir qrafik üçün genişlik-ilk axtarış (BFS)(Yeni bir tarayıcı sekmesinde açılır)

Yuxarıdakı prosesi göstərmək üçün sadə bir görüntü

Pin

Şeyi necə edəcəyimizə dair əsas bir fikrimiz olduğuna görə koda girək

Qrafik Klonlama üçün Java Proqramı

class Solution 
{
    public Node cloneGraph(Node node) 
    {
     if(node==null)
         return null;
     //Creating a Queue for BFS
     Queue<Node>store=new LinkedList<Node>();
     //Adding the root node
     store.add(node);
     //Creating a hashmap of nodes and copies
     HashMap<Node,Node>hash=new HashMap<Node,Node>();
     hash.put(node,new Node(node.val));
     //Firing up the BFS!
     while(!store.isEmpty())
     {
         Node cur=store.poll();
         for(Node neigh:cur.neighbors)
         {
             if(!hash.containsKey(neigh))
             {
             hash.put(neigh,new Node(neigh.val));
             store.add(neigh);   
             }
             //Adding the neighbours to the duplicate nodes
             hash.get(cur).neighbors.add(hash.get(neigh));
         }
     }
     return(hash.get(node));
    }
}

Qrafik Klonlama üçün C ++ Proqramı

class Solution 
{
public:
    Node* cloneGraph(Node* node)
    {
     if(!node)
         return NULL;
     //Creating a Queue for BFS
     queue<Node*>store;
     //Adding the root node
     store.push(node);
     //Creating a hashmap of nodes and copies
     map<Node*,Node*>hash;
     hash[node]=new Node(node->val,{});
     //Firing up the BFS!
     while(!store.empty())
     {
         Node* cur=store.front();
         store.pop();
         for(Node* neigh:cur->neighbors)
         {
             if(hash.count(neigh)==0)
             {
             hash[neigh]=new Node(neigh->val,{});
             store.push(neigh);   
             }
             //Adding the neighbours to the duplicate nodes
             hash[cur]->neighbors.push_back(hash[neigh]);
         }
     }
     return(hash[node]); 
    }
};

[[1,2],[2,3],[3,4],[4,5],[1,2]]

[[1,2],[2,3],[3,4],[4,5],[1,2]]

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi = O (V + E)

Kosmik mürəkkəblik = O (n)

V = Diklərin sayı

E = Kənarların sayı

Zaman və məkan mürəkkəbliyi bununla necə başa çatdı?

• Kodda V dəfə işləyən növbəni boşaldan bir döngə var. Döngədə
  • Veriləri növbədən çıxarırıq = O (1) əməliyyatı
  • Klonları əldə etmək üçün bütün qonşu kənarları keçin = O (Adj)
  • Qonşuları əlavə edin = O (1) əməliyyatı
• Mürəkkəbliyi xülasə edərək = V * (O (1) + O (Adj) + O (1))
• Hansı O (V) + O (V * Adj) qədər qaynar
• Zamanın mürəkkəbliyini etmək = O (V + E)
• Məkan mürəkkəbliyi O (n) dir, çünki bizə lazım olan hər şey növbə idi

References