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

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ą.

szpilka

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