C++를 사용하여 트리의 하위 트리에 대한 깊이 우선 검색

이 문제에서 우리는 이진 트리를 얻고 특정 노드에서 dfs를 실행해야 합니다. 여기서 우리는 주어진 노드를 루트로 가정하고 그 노드에서 dfs를 실행합니다.

위의 트리에서는 DFS 노드 F를 실행해야 한다고 가정합니다.

이 튜토리얼에서는 시간 복잡도를 크게 줄이기 위해 몇 가지 비정통적인 방법을 적용하여 제약 조건 하에서 이 코드를 실행합니다.

Method - 이 접근 방식에서는 순진한 접근 방식을 사용하지 않습니다. 즉, 더 높은 제약 조건에서는 작동하지 않으므로 단순히 각 노드에 dfs를 적용하므로 TLE를 얻지 않기 위해 비정통적인 방법을 사용하려고 합니다.

#include <bits/stdc++.h>
using namespace std;
#define N 100000
// Adjacency list to store the
// tree nodes connections
vector<int> v[N];
unordered_map<int, int> mape; // will be used for associating the node with it&#39;s index
vector<int> a;
void dfs(int nodesunder[], int child, int parent){ // function for dfs and     precalculation our nodesunder
    a.push_back(child); // storing the dfs of our tree
    // nodesunder of child subtree
    nodesunder[child] = 1;
    for (auto it : v[child]) { // performing normal dfs

        if (it != parent) { // as we the child can climb up to
        //it&#39;s parent so we are trying to avoid that as it will become a cycle
            dfs(nodesunder, it, child); // recursive call
            nodesunder[child] += nodesunder[it]; // storing incrementing the nodesunder
        //by the number of nodes under it&#39;s children
        }
    }
}
// Function to print the DFS of subtree of node
void printDFS(int node, int nodesunder[]){
    int ind = mape[node]; // index of our node in the dfs array
    cout << "The DFS of subtree " << node << ": ";
    // print the DFS of subtree
    for (int i = ind; i < ind + nodesunder[node]; i++){ // going through dfs array and then
    //printing all the nodes under our given node
        cout << a[i] << " ";
    }
    cout << endl;
}
void addEdgetoGraph(int x, int y){ // for maintaining adjacency list
    v[x].push_back(y);
    v[y].push_back(x);
}
void mark(){ // marking each node with it&#39;s index in dfs array
    int size = a.size();
    // marks the index
    for (int i = 0; i < size; i++) {
       mape[a[i]] = i;
    }
}
int main(){
    int n = 7;
    // add edges of a tree
    addEdgetoGraph(1, 2);
    addEdgetoGraph(1, 3);
    addEdgetoGraph(2, 4);
    addEdgetoGraph(2, 5);
    addEdgetoGraph(4, 6);
    addEdgetoGraph(4, 7);
    // array to store the nodes present under of subtree
    // of every node in a tree
    int nodesunder[n + 1];
    dfs(nodesunder, 1, 0); // generating our nodesunder array
    mark(); // marking the indices in map
    // Query 1
    printDFS(2, nodesunder);
    // Query 2
    printDFS(4, nodesunder);
    return 0;
}

Output

The DFS of subtree 2: 2 4 6 7 5
The DFS of subtree 4: 4 6 7

코드 이해하기

이 방법에서는 dfs의 순서를 미리 계산하여 벡터에 저장합니다. dfs를 미리 계산할 때 then 아래에 존재하는 각 노드 노드에서 시작하여 각 하위 트리도 계산한 다음 간단히 노드의 시작 인덱스부터 해당 하위 트리에 존재하는 모든 노드의 수까지 순회합니다.

결론

이 튜토리얼에서는 다음 쿼리를 해결하기 위해 문제를 해결했습니다. 트리에 있는 하위 트리의 DFS. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 방법(일반)을 배웠습니다.

같은 프로그램을 다른 언어(C, java, python 등)로도 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 C++를 사용하여 트리의 하위 트리에 대한 깊이 우선 검색의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!