시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
그래프 문제의 반복적 인 깊이 우선 순회에서는 그래프 데이터 구조를 제공했습니다. 반복 방법을 사용하여 주어진 그래프의 깊이 첫 번째 순회를 인쇄하는 프로그램을 작성하십시오.
차례
예
입력 : 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
그래프의 반복 깊이 첫 번째 순회를위한 알고리즘
- 수업 만들기 Graph. 정수 변수를 초기화하여 정점과 정수 유형 목록을 저장합니다.
- 매개 변수로서 꼭짓점의 정수 값을 받아들이는 클래스의 매개 변수화 된 생성자를 만듭니다. 매개 변수로 전달 된 값을 클래스의 vertex 변수에 저장하고 클래스 목록에 목록을 만듭니다.
- 마찬가지로, 매개 변수로 꼭지점과 가장자리 끝 값을 받아들이는 가장자리를 추가하는 함수를 만듭니다. 주어진 정점 목록에서 가장자리 값을 밀어 넣습니다.
- 마지막으로 다음에 대한 함수를 만듭니다. 깊이 우선 순회 이것은 매개 변수 인 소스 노드를 나타내는 정수 say s를받습니다. 부울 유형의 벡터를 초기화하고 벡터의 모든 값을 false로 설정합니다.
- 스택 데이터 구조를 생성하고 그 안에 소스 노드의 값을 저장합니다.
- 스택이 비어 있지 않은 동안 트래버스합니다. 소스 노드의 값을 스택 맨 위에있는 요소로 업데이트하고 스택에서 팝합니다.
- 인덱스, 즉 소스 노드의 벡터 값이 거짓이면 소스 노드를 인쇄하고 인덱스 s의 벡터 값을 참으로 업데이트합니다.
- 정점 / 노드 목록을 탐색하고 벡터의 현재 인덱스 값이 거짓인지 확인하여 스택에 푸시합니다.
그래프의 반복 깊이 첫 번째 순회를위한 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 노드 / 요소에 공간을 사용했기 때문입니다.
