Neste laboratório, você irá implementar um algoritmo de travessia de grafo chamado <dfn>depth-first search</dfn> (DFS). Enquanto uma <dfn>busca em largura</dfn> (BFS) explora os vizinhos nível por nível, a <dfn>busca em profundidade</dfn> mergulha o mais fundo possível em um único path de arestas antes de retroceder. Uma vez que o algoritmo alcança o fim de um path (um node sem vizinhos não visitados), ele retrocede para o node mais recente que ainda possui arestas não exploradas e continua a busca a partir daí. Para implementar esse algoritmo iterativamente, você vai querer usar uma stack. Em Javascript, um Array padrão serve perfeitamente como uma stack usando os métodos .push() e .pop(), seguindo o princípio Last-In-First-Out (LIFO). Isso garante que o vizinho mais recentemente adicionado à stack seja o próximo a ser explorado. Uma saída simples deste algoritmo é uma lista de nós que são acessíveis a partir de um determinado nó. Portanto, você também vai querer acompanhar os nós que visita. Objetivo: Cumprir as user stories abaixo e fazer com que todos os testes passem para completar o laboratório. Histórias de Usuário: 1. Você deve definir uma função chamada dfs. 1. A função dfs deve receber dois argumentos:

• graph: Uma matriz de adjacência (um array de arrays).
• root: Um rótulo numérico de nó (o índice inicial) que é o valor numérico do nó entre 0 e n - 1, onde n é o número total de nós no grafo.

1. A função deve retornar um array contendo todos os rótulos de nós alcançáveis a partir do nó inicial.

Testes:

• Você deve ter uma função chamada `dfs` que recebe dois argumentos.
• `dfs([[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]], 1)` deve retornar uma lista com `1`, `2`, `3` e `0`.
• `dfs([[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]], 3)` deve retornar uma lista com `1`, `2`, `3` e `0`.
• `dfs([[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 0]], 3)` deve retornar `[3]`.
• `dfs([[0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]], 3)` deve retornar uma lista com `3` e `2`.
• `dfs([[0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]], 0)` deve retornar uma lista com `0` e `1`.