Ітэратыўная глыбіня Першы развод графіка


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка Avalara Факты Фанатыкі Google Аракул
Глыбіня Першы пошук Графік Стэк

У ітэратыўнай глыбіні першага абходу задачы графа мы далі структуру дадзеных графа. Напішыце праграму для друку глыбіні першага абходу дадзенага графіка з выкарыстаннем ітэратыўнага метаду.

Ітэратыўная глыбіня Першы развод графіка

Прыклад

Уваход: 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. Стварыце клас Графік. Ініцыялізуйце цэлалікавую зменную для захоўвання вяршыняў і спісу цэлага тыпу.
  2. Стварыце параметрызаваны канструктар класа, які прымае цэлае значэнне вяршыні, паколькі гэта параметр. Захоўваеце значэнне, якое перадаецца як параметр, у пераменнай вяршыні класа і стварайце спіс у спісе класа.
  3. Аналагічным чынам стварыце функцыю, каб дадаць край, які прымае вяршыню і значэнне канца краю, як яго параметр. Націсніце значэнне краю ў спісе дадзенай вяршыні.
  4. Нарэшце, стварыце функцыю для абход глыбіні які прымае цэлае слова "s", якое прадстаўляе зыходны вузел як параметр. Ініцыялізуйце вектар лагічнага тыпу і ўсталюйце ўсе значэнні вектара як ілжывыя.
  5. Стварыце структуру дадзеных стэка і захавайце ў ёй значэнне зыходнага вузла.
  6. Траверс, пакуль стэк не пусты. Абнавіце значэнне зыходнага вузла як элемента ў верхняй частцы стэка і вынясіце яго з стэка.
  7. Калі значэнне ў вектары ў індэксе s, гэта значыць зыходны вузел, ілжывае, раздрукуйце зыходны вузел і абнавіце значэнне ў вектары з індэксам 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

Праграма Java для ітэратыўнай глыбіні Першы развод графіка

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 вузлоў / элементаў.

Спасылкі