반복 깊이 그래프의 첫 번째 순회

난이도 쉽게
자주 묻는 질문 아마존 아 발라 라 팩트 셋 광신자 구글 신탁
깊이 우선 검색 Graph 스택조회수 28

그래프 문제의 반복적 인 깊이 우선 순회에서는 그래프 데이터 구조를 제공했습니다. 반복 방법을 사용하여 주어진 그래프의 깊이 첫 번째 순회를 인쇄하는 프로그램을 작성하십시오.

반복 깊이 그래프의 첫 번째 순회

입력 : 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. 마지막으로 다음에 대한 함수를 만듭니다. 깊이 우선 순회 이것은 매개 변수 인 소스 노드를 나타내는 정수 say s를받습니다. 부울 유형의 벡터를 초기화하고 벡터의 모든 값을 false로 설정합니다.
  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

그래프의 반복 깊이 첫 번째 탐색을위한 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 노드 / 요소에 공간을 사용했기 때문입니다.

참조

Translate »