depth first search c program traverse graph
이 자습서에서는 그래프 또는 트리가 깊이 방향으로 순회되는 C ++의 DFS (Depth First Search)를 다룹니다. 또한 DFS 알고리즘 및 구현을 배우게됩니다.
깊이 우선 검색 (DFS)은 트리 또는 그래프를 탐색하는 데 사용되는 또 다른 기술입니다.
DFS는 루트 노드 또는 시작 노드로 시작한 다음 그래프 또는 트리로 더 깊이 들어가 현재 노드의 인접 노드를 탐색합니다. 즉, DFS에서 노드는 자식이없는 노드를 만날 때까지 깊이 탐색됩니다.
리프 노드에 도달하면 DFS는 역 추적하고 유사한 방식으로 더 많은 노드를 탐색하기 시작합니다.
=> 여기에서 초보자 C ++ 교육 가이드를 확인하십시오.
학습 내용 :
C ++의 깊이 우선 검색 (DFS)
노드를 폭 넓게 탐색하는 BFS와 달리 DFS에서는 노드를 깊이 탐색합니다. DFS에서는 탐색중인 노드를 저장하기 위해 스택 데이터 구조를 사용합니다. 우리를 탐험하지 않은 노드로 이끄는 가장자리를 '검색 가장자리'라고하고 이미 방문한 노드로 이어지는 가장자리를 '블록 가장자리'라고합니다.
다음으로 DFS 기술에 대한 알고리즘과 의사 코드를 살펴 보겠습니다.
DFS 알고리즘
- 1 단계: 스택에 트리 또는 그래프의 루트 노드 또는 시작 노드를 삽입합니다.
- 2 단계: 스택에서 최상위 항목을 꺼내 방문 목록에 추가합니다.
- 3 단계 : 방문으로 표시된 노드의 모든 인접 노드를 찾고 아직 방문하지 않은 노드를 스택에 추가합니다.
- 4 단계 : 스택이 비워 질 때까지 2 단계와 3 단계를 반복합니다.
의사 코드
DFS의 의사 코드는 다음과 같습니다.
위의 의사 코드에서 DFS 알고리즘이 각 정점에서 재귀 적으로 호출되어 모든 정점이 방문되도록합니다.
삽화가있는 순회
이제 그래프의 DFS 순회를 설명하겠습니다. 명확성을 위해 BFS 그림에서 사용한 것과 동일한 그래프를 사용합니다.
0을 시작 노드 또는 소스 노드로 둡니다. 먼저 방문한 것으로 표시하고 방문 목록에 추가합니다. 그런 다음 인접한 모든 노드를 스택에 푸시합니다.
다음으로 인접한 노드 중 하나를 사용하여 처리합니다. 즉, 스택의 맨 위가 1입니다. 방문한 목록에 추가하여 방문한 것으로 표시합니다. 이제 인접 노드 1을 찾으십시오. 0이 이미 방문 목록에 있으므로이를 무시하고 스택의 최상위 인 2를 방문합니다.
다음으로 노드 2를 방문한 것으로 표시합니다. 인접한 노드 4가 스택에 추가됩니다.
다음으로, 방문한 스택의 맨 위에있는 4를 표시합니다. 노드 4에는 이미 방문한 인접 노드 2 만 있으므로 무시합니다.
이 단계에서는 노드 3 만 스택에 있습니다. 인접한 노드 0은 이미 방문되었으므로 무시합니다. 이제 3을 방문한 것으로 표시합니다.
이제 스택은 비어 있고 방문 목록은 주어진 그래프의 깊이 우선 순회 순서를 보여줍니다.
주어진 그래프와 순회 시퀀스를 관찰하면 DFS 알고리즘의 경우 실제로 그래프를 깊이 방향으로 순회 한 다음 다시 역 추적하여 새 노드를 탐색합니다.
깊이 우선 검색 구현
C ++를 사용하여 DFS 순회 기술을 구현해 보겠습니다.
#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited[]); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list[V]; } // function to add an edge to graph void addEdge(int v, int w){ adjList[v].push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited[]) { // current node v is visited visited[v] = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList[v].begin(); i != adjList[v].end(); ++i) if(!visited[*i]) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited[i] == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'< 산출:
주어진 그래프에 대한 깊이 우선 순회 :
012 4 3
우리는 설명 목적으로 사용한 프로그램에서 그래프를 다시 사용했습니다. DFS 알고리즘 (두 개의 함수로 분리됨)이 그래프의 각 정점에서 재귀 적으로 호출되어 모든 정점이 방문되었는지 확인합니다.
런타임 분석
DFS의 시간 복잡성은 BFS와 동일합니다. O (| V | + | E |) 여기서 V는 정점의 수이고 E는 주어진 그래프의 간선 수입니다.
BFS와 유사하게 그래프가 거의 채워지지 않았는지 또는 밀집되어 있는지 여부에 따라 지배적 인 요소는 시간 복잡도 계산에서 각각 꼭지점 또는 모서리가됩니다.
반복 DFS
DFS 기술에 대해 위에 표시된 구현은 본질적으로 재귀 적이며 함수 호출 스택을 사용합니다. DFS 구현을위한 또 다른 변형이 있습니다. ' 반복적 인 깊이 우선 검색 ”. 여기에서 명시 적 스택을 사용하여 방문한 정점을 유지합니다.
아래에 반복 DFS의 구현이 나와 있습니다. 구현은 큐 대신 스택 데이터 구조를 사용한다는 점을 제외하면 BFS와 동일합니다.
#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list[V]; } void addEdge(int v, int w) // add an edge to graph { adjList[v].push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited[s]) { cout << s << ' '; visited[s] = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList[s].begin(); i != adjList[s].end(); ++i) if (!visited[*i]) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited[i]) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal:
'; gidfs.DFS(); return 0; }
산출:
반복 깊이 우선 탐색의 출력 :
0 3 2 4 1
재귀 구현에서 사용한 것과 동일한 그래프를 사용합니다. 출력의 차이는 반복 구현에서 스택을 사용하기 때문입니다. 스택이 LIFO 순서를 따를 때 다른 DFS 순서를 얻습니다. 동일한 시퀀스를 얻으려면 정점을 역순으로 삽입 할 수 있습니다.
BFS 대 DFS
지금까지 그래프에 대한 순회 기법, 즉 BFS 및 DFS에 대해 논의했습니다.
이제 둘의 차이점을 살펴 보겠습니다.
BFS DFS 'Breadth-first search'의 약자 '깊이 우선 검색'의 약자 노드는 수준별로 넓게 탐색됩니다. 노드는 리프 노드 만있을 때까지 깊이 탐색 한 다음 방문하지 않은 다른 노드를 탐색하기 위해 역 추적합니다. BFS는 큐 데이터 구조의 도움으로 수행됩니다. DFS는 스택 데이터 구조의 도움으로 수행됩니다. 성능이 느립니다. BFS보다 빠릅니다. 두 노드 사이의 최단 경로를 찾는 데 유용합니다. 주로 그래프에서주기를 감지하는 데 사용됩니다.
DFS의 응용
- 그래프에서주기 감지 : 그래프에서 DFS를 수행하는 동안 백 에지를 찾으면 그래프에주기가 있다는 결론을 내릴 수 있습니다. 따라서 DFS는 그래프에서주기를 감지하는 데 사용됩니다.
- 길 찾기: 두 개의 꼭지점 x와 y가 주어지면 DFS를 사용하여 x와 y 사이의 경로를 찾을 수 있습니다. 정점 x로 시작한 다음 y를 만날 때까지 모든 정점을 스택으로 밀어 넣습니다. 스택의 내용은 x와 y 사이의 경로를 제공합니다.
- 최소 스패닝 트리 및 최단 경로 : 가중치가없는 그래프의 DFS 순회는 최소 스패닝 트리와 노드 간의 최단 경로를 제공합니다.
- 토폴로지 정렬 : 작업간에 주어진 종속성에서 작업을 예약해야 할 때 토폴로지 정렬을 사용합니다. 컴퓨터 과학 분야에서는 주로 링커, 데이터 직렬화, 명령어 스케줄링 등에서 심볼 종속성을 해결하는 데 사용합니다. DFS는 토폴로지 정렬에 널리 사용됩니다.
결론
지난 몇 번의 튜토리얼에서 우리는 그래프에 대한 두 가지 순회 기법, 즉 BFS와 DFS에 대해 자세히 살펴 보았습니다. 우리는 두 기술의 차이점과 적용을 보았습니다. BFS와 DFS는 기본적으로 그래프의 모든 노드를 방문하는 것과 동일한 결과를 얻지 만 출력 순서와 수행 방식이 다릅니다.
우리는 또한 두 기술의 구현을 보았습니다. BFS는 큐를 사용하지만 DFS는 스택을 사용하여 기술을 구현합니다. 이것으로 그래프의 순회 기법에 대한 튜토리얼을 마칩니다. 나무에 BFS와 DFS를 사용할 수도 있습니다.
숙련 된 PDF에 대한 SQL 개발자 인터뷰 질문 및 답변
다가오는 튜토리얼에서 그래프 노드 사이의 최단 경로를 찾기위한 스패닝 트리와 몇 가지 알고리즘에 대해 자세히 알아볼 것입니다.
=> 전체 C ++ 자습서 목록을 탐색하려면 여기를 참조하십시오.
추천 도서