Neste laboratório, você implementará um algoritmo de travessia de grafo chamado <dfn>depth-first search</dfn>. Enquanto a <dfn>breadth-first search</dfn> busca incrementos de comprimento de arestas a partir do nó fonte, a <dfn>depth-first search</dfn> primeiro segue por um caminho de arestas o máximo que pode. Ao chegar ao fim de um caminho, a busca voltará para o último nó com um caminho de aresta não visitado e continuará a procurar. Ao contrário da busca em largura, toda vez que um nó é visitado, ele não visita todos os seus vizinhos. Em vez disso, ele primeiro visita um dos seus vizinhos e continua por esse caminho até que não haja mais nós a serem visitados nesse caminho. Para implementar este algoritmo, você vai querer usar uma pilha (um array onde o último elemento adicionado é o primeiro a ser removido, seguindo o princípio <dfn>Last-In-First-Out</dfn>). Uma pilha é útil em algoritmos de busca em profundidade porque, à medida que você adiciona vizinhos à pilha, você quer visitar primeiro os vizinhos adicionados mais recentemente e removê-los da pilha. 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 ter uma função chamada dfs. 1. A função dfs deve receber dois argumentos:

• Uma matriz de adjacência não direcionada.
• Um rótulo de nó, 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 dfs deve implementar o algoritmo de busca em profundidade para gerar uma lista de todos os nós alcançáveis a partir do nó passado para ela.

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`.
• A função `dfs` deve retornar os resultados corretos.