# #1 Graph: Depth-first Search

###### tags:`Graph` `Easy`

<br>

## Issue

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.
If you're unfamiliar with Depth-first Search, we recommend watching the Conceptual Overview section of this question's video explanation before starting to code.

### Sample Input


### Sample Output

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

### Hints
:::spoiler Hint 1
The Depth-first Search algorithm works by traversing a graph branch by branch. In other words, before traversing any Node's sibling Nodes, its children nodes must be traversed. How can you simply and effectively keep track of Nodes' sibling Nodes as you traverse them, all the while retaining the order in which you must traverse them?
:::

:::spoiler Hint 2
Start at the root Node and try simply calling the depth FirstSearch method on all of its children Nodes. Then, call the depth FirstSearch method on all children Nodes of each child node. Keep applying this logic until the entire graph has been traversed. Don't forget to add the current Node's name to the input array at every call of depth FirstSearch.
:::

### Optimal Space & Time Complexity

:::spoiler Answer
O(v + e) time O(v) space - where v is the number of vertices of the input graph, and e is the number of edges of the input graph
:::

<br>

## Solutions

### Official

:::spoiler Solution 1

class Node {
  constructor(name) {
    this.name = name;
    this.children = [];
  }

  addChild(name) {
    this.children.push(new Node(name));
    return this;
  }

  // O(v + e) time | 0(v) space
  depthFirstSearch(array) {
    array.push(this.name);
    for (const child of this.children) {
      child.depthFirstSearch(array);
    }
    return array;
  }
}

exports.Node = Node;

:::

### Everyone's

:::spoiler 東

  /* 
  Time O(n) | Space O(h)
  n is the number of nodes 
  h is the depth of nodes
  */
  depthFirstSearch(array) {
    function dfsTraverse(children){
      while(children.length !== 0){
        const currChild = children.shift();
        array.push(currChild.name);
        dfsTraverse(currChild.children);
      }
      return;
    }
    array.push(this.name);
    dfsTraverse(this.children);
    return array;
  }
}

改進寫法QQQ

depthFirstSearch(array) {
    array.push(this.name);
    for(const childNode of this.children){
      childNode.depthFirstSearch(array);
    }
    return array;
  }

:::

<br>

:::spoiler Hao

  depthFirstSearch(array) {
    array.push(this.name);
    this.children.length && this.children.forEach((node) => node.depthFirstSearch(array));
    return array;
  }

:::

<br>

:::spoiler YC

depthFirstSearch(array) {
  /*
    time: O(v + e) - where v is the number of vertices of the graph, e is the number of edges of the graph
    space: O(v) - where v is the number of vertices of the graph
  */
  array.push(this.name)
  for(const child of this.children){
    child.depthFirstSearch(array);
  }
  return array;
}

:::

<br>

:::spoiler Becky

:::

<br>

:::spoiler 月薪

  // Time: O(v+e) | Space: O(v)
  // where v is the number of vertexes and e is the number of edges
  depthFirstSearch(array) {
    array.push(this.name);
    this.children.forEach((child) => child.depthFirstSearch(array))；
    return array
  }

:::

<br>

## Discussion
### Why is the time complexity of both DFS and BFS O( V + E )
[Why is the time complexity of both DFS and BFS O( V + E )](https://stackoverflow.com/questions/11468621/why-is-the-time-complexity-of-both-dfs-and-bfs-o-v-e)

But why we intuitively think the time complexity in the case would be O(n) just like that in the case of DFS with binary tree?

`O(v + e) = O(n + n) ~= O(n)?`

### More for Graph

[ramonliao 30天學演演算法和資料結構: Graph 常用圖說](https://ithelp.ithome.com.tw/articles/10208277)
[ramonliao 30天學演演算法和資料結構: Depth-first Search](https://ithelp.ithome.com.tw/articles/10208441)
[Graph: Depth-First Search(DFS，深度優先搜尋)](https://alrightchiu.github.io/SecondRound/graph-depth-first-searchdfsshen-du-you-xian-sou-xun.html)