[演算法題目] Depth-first Search

本題資訊

難度：easy
使用語言：C++
相關概念：Graph

題目敘述

You’re given a Node class that has a name and an array of optional children nodes. When put together, nodes form an acyclic tree-like structure.

Implement the depthFirstSearch method on the Node class, which takes in an empty array, traverses the tree using the Depth-first Search approach (specifically navigating the tree from left to right), stores all of the nodes’ names in the input array, and returns it.

看起來是要實作 Depth-first Search (DFS)，也就是所謂的深度優先搜尋。深度優先搜尋簡單來說就是節點若能往下挖就往下挖，無法再繼續挖下去時才一層層退回去看另外一個子節點是否能繼續挖下去。

Input

graph = A
     /  |  \
    B   C   D
   / \     / \
  E   F   G   H
     / \   \
    I   J   K

Output

["A", "B", "E", "F", "I", "J", "C", "D", "G", "K", "H"]

Idea

其實也沒什麼，主要是注意樹的建構，演算法部分專注於每一回都找目前節點的子節點們做迴圈，針對每一個子節點再繼續 depthFirstSearch 往下找。

#include <vector>
using namespace std;

class Node {
public:
  string name;
  vector<Node *> children;

  Node(string str) { name = str; }

  vector<string> depthFirstSearch(vector<string> *array) {
    array->push_back(this->name);
    for (auto child : this->children){
      child->depthFirstSearch(array);
    }
    return *array;
  }

  Node *addChild(string name) {
    Node *child = new Node(name);
    children.push_back(child);
    return this;
  }
};

時間複雜度：\(O(v+e)\)，其中 \(v\) 是圖的點的個數、 \(e\) 是邊的個數。
空間複雜度：\(O(v)\)