დიაგრამაზე განმეორებითი სიღრმის პირველი გადაკვეთა  


Რთული ტური Easy
ხშირად ეკითხებიან Amazon ავალარა ფაქტები ფანატიკა Google Oracle
სიღრმისეული პირველი ძებნა Graph დასტის

გრაფიკის პრობლემის განმეორებითი სიღრმეში პირველი, ჩვენ მივეცით გრაფიკული მონაცემების სტრუქტურა. დაწერეთ პროგრამა მოცემული გრაფიკის სიღრმისეული პირველი გადაკვეთის დასაბეჭდად განმეორებითი მეთოდის გამოყენებით.

დიაგრამაზე განმეორებითი სიღრმის პირველი გადაკვეთაPin

მაგალითი  

შეყვანა: 0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3

გამოყვანა: 1 2 0 3

შეყვანა: 2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3

გამოყვანა: 2 0 1 3

გრაფიკის განმეორებითი სიღრმის პირველი გადაკვეთის ალგორითმი  

  1. კლასის შექმნა Graph. მთლიანი ცვლადის ინიციალიზაცია ვერტიკების შესანახად და მთელი ტიპის ტიპის სიის შესანახად.
  2. შექმენით კლასის პარამეტრიზებული კონსტრუქტორი, რომელიც იღებს ვერტექსის მთლიან მნიშვნელობას, რადგან ის არის პარამეტრი. შეინახეთ პარამეტრის სახით გატარებული მნიშვნელობა კლასის vertex ცვლადში და შექმენით სია სიაში კლასის სიაში.
  3. ანალოგიურად, შექმენით ფუნქცია, რომ დაამატოთ ზღვარი, რომელიც იღებს ვერტიკსა და კიდის დაბოლოების მნიშვნელობას, რადგან ის არის პარამეტრი. მოცემული წვეროს სიაში დააყენეთ ზღვრის მნიშვნელობა.
  4. დაბოლოს, შექმენით ფუნქცია for სიღრმის პირველი გატარება რომელიც იღებს მთელ რიცხვს, რომელიც წარმოადგენს წყაროს კვანძს, როგორც ის პარამეტრს. ლოგიკური ტიპის ვექტორის ინიცირება და ვექტორის ყველა მნიშვნელობის დაყენება ყალბი სახით.
  5. შექმენით მონაცემთა დასტის სტრუქტურა და შეინახეთ მასში წყაროს კვანძის მნიშვნელობა.
  6. გადაკვეთა, სანამ დასტა ცარიელი არ არის. განაახლეთ წყაროს კვანძის მნიშვნელობა, როგორც ელემენტის სტეკის ზედა ნაწილში და გამოაქვეყნეთ იგი სტეკიდან.
  7. თუ ინდექსის s ანუ წყაროს კვანძში ვექტორის მნიშვნელობა მცდარია, დაბეჭდეთ წყაროს კვანძი და განაახლეთ მნიშვნელობა ვექტორში ინდექსში, როგორც სიმართლე.
  8. გადაკვეთეთ ვერტექსის / კვანძის სიაში და შეამოწმეთ არის თუ არა ვექტორული მიმდინარე ინდექსის მნიშვნელობა ყალბი, რომ დააჭიროთ მას სტეკში.
იხილეთ ასევე
მინიმალური დროა საჭირო ყველა ფორთოხლის გასანადგურებლად

C ++ პროგრამა დიაგრამაზე განმეორებითი სიღრმისეული პირველი გადახედვისთვის  

#include<bits/stdc++.h> 
using namespace std; 
  
class Graph{ 
    int V;  
    list<int> *adj;  
    
    public: 
        Graph(int V); 
        void addEdge(int v, int w);
        void DFS(int s);  
}; 
  
Graph::Graph(int V){ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Graph::addEdge(int v, int w){ 
    adj[v].push_back(w); 
} 
  
void Graph::DFS(int s){ 
    vector<bool> visited(V, false); 
  
    stack<int> stack; 
  
    stack.push(s); 
  
    while (!stack.empty()){ 
        s = stack.top(); 
        stack.pop(); 
  
        if(!visited[s]){ 
            cout << s << " "; 
            visited[s] = true; 
        } 
  
        for(auto i = adj[s].begin(); i != adj[s].end(); ++i){ 
            if(!visited[*i]){ 
                stack.push(*i);
            }
        }
    } 
} 
  
int main(){ 
    Graph g(5);
    
    g.addEdge(1, 0); 
    g.addEdge(0, 2); 
    g.addEdge(2, 1); 
    g.addEdge(0, 3); 
    g.addEdge(1, 4); 
  
    g.DFS(0); 
  
    return 0; 
}
0 3 2 1 4

ჯავა პროგრამა დიაგრამაზე განმეორებითი სიღრმისეული პირველი გადახედვისთვის  

import java.util.*; 
  
class IterativeTraversal{ 
    
    static class Graph{ 
        int V; 
          
        LinkedList<Integer>[] adj; 
          
        Graph(int V){ 
            this.V = V; 
            adj = new LinkedList[V]; 
              
            for(int i = 0; i < adj.length; i++){ 
                adj[i] = new LinkedList<Integer>();
            }
        } 
          
        void addEdge(int v, int w){ 
            adj[v].add(w); 
        } 
          
        void DFS(int s){ 
            Vector<Boolean> visited = new Vector<Boolean>(V); 
            
            for(int i = 0; i < V; i++){ 
                visited.add(false); 
            }
      
            Stack<Integer> stack = new Stack<>(); 
              
            stack.push(s); 
              
            while(stack.empty() == false){ 
                s = stack.peek(); 
                stack.pop(); 
                  
                if(visited.get(s) == false){ 
                    System.out.print(s + " "); 
                    visited.set(s, true); 
                } 
                  
                Iterator<Integer> itr = adj[s].iterator(); 
                  
                while (itr.hasNext()){ 
                    int v = itr.next(); 
                    if(!visited.get(v)){ 
                        stack.push(v); 
                    }
                } 
            } 
        } 
    } 
      
    public static void main(String[] args){ 
        
        Graph g = new Graph(5); 
          
        g.addEdge(1, 0); 
        g.addEdge(0, 2); 
        g.addEdge(2, 1); 
        g.addEdge(0, 3); 
        g.addEdge(1, 4); 
              
        g.DFS(0); 
    } 
}
0 3 2 1 4

სირთულის ანალიზი  

დროის სირთულე: O (V + E), სადაც V და E მოცემულია გრაფიკის წვერებისა და კიდეების რიცხვები.

სივრცის სირთულე: O (V) რადგან ჩვენ გამოვიყენეთ სივრცე V კვანძების / ელემენტებისათვის.

ლიტერატურა