Iteracyjne przejście przez pierwszą głębokość wykresu

Poziom trudności Łatwo
Często zadawane pytania Amazonka Avalara Zestaw faktów Fanatycy Google wyrocznia
Głębokie pierwsze wyszukiwanie Wykres Stosodwiedzajacy 75

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W iteracyjnej głębi pierwszego przejścia problemu grafu, przedstawiliśmy strukturę danych grafu. Napisz program, który wydrukuje głębokość pierwszego przejścia danego wykresu metodą iteracyjną.

Iteracyjne przejście przez pierwszą głębokość wykresuszpilka

Przykład

wejście: 0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3

wyjście: 1 2 0 3

wejście: 2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3

wyjście: 2 0 1 3

Algorytm iteracyjnego przejścia przez pierwszą głębokość wykresu

  1. Utwórz zajęcia Wykres. Zainicjuj zmienną całkowitą, aby przechowywać wierzchołki i listę typu całkowitego.
  2. Utwórz sparametryzowany konstruktor klasy, która przyjmuje wartość całkowitą wierzchołka jako parametr. Przechowuj wartość przekazaną jako parametr w zmiennej wierzchołkowej klasy i utwórz listę na liście klasy.
  3. Podobnie, utwórz funkcję, aby dodać krawędź, która akceptuje wierzchołek i wartość końcową krawędzi jako parametr. Wepchnij wartość edge na listę danego wierzchołka.
  4. Na koniec utwórz funkcję dla przechodzenie w głąb który akceptuje liczbę całkowitą, powiedz s reprezentującą węzeł źródłowy jako parametr. Zainicjuj wektor typu boolowskiego i ustaw wszystkie wartości wektora na fałsz.
  5. Utwórz strukturę danych stosu i zapisz w niej wartość węzła źródłowego.
  6. Przechodź, gdy stos nie jest pusty. Zaktualizuj wartość węzła źródłowego jako elementu na szczycie stosu i zdejmij go ze stosu.
  7. Jeśli wartość w wektorze przy indeksie s tj. Węźle źródłowym jest fałszywa, wydrukuj węzeł źródłowy i zaktualizuj wartość w wektorze przy indeksie s jako prawdę.
  8. Przejrzyj listę wierzchołków / węzłów i sprawdź, czy wartość w bieżącym indeksie wektora jest fałszywa, aby umieścić ją na stosie.

Program w C ++ do iteracyjnego przejścia przez pierwszą głębokość wykresu

#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

Program w języku Java do iteracyjnego przechodzenia przez pierwszą głębokość przez wykres

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

Analiza złożoności

Złożoność czasowa: O (V + E) gdzie V i E to odpowiednio liczby wierzchołków i krawędzi danego wykresu.

Złożoność przestrzeni: O (V), ponieważ wykorzystaliśmy miejsce na węzły / elementy V.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »