Итерационный обход графа в глубину


Сложный уровень Легко
Часто спрашивают в Амазонка Avalara Набор фактов Фанатики Google Oracle
Поиск в глубину График Стек

В итеративном углубленном первом обходе проблемы графа мы дали структуру данных графа. Напишите программу для печати первого обхода заданного графа в глубину, используя итерационный метод.

Итерационный обход графа в глубину

Пример

Вход: 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, представляющее исходный узел в качестве параметра. Инициализируйте вектор логического типа и установите все значения вектора как false.
  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 узлов / элементов.

дело