Estrutura de Dados - Exercício Extra 1 - Árvores de Altura Mínima

Disciplina Estrutura de Dados Professor Daniel Porto Semestre 20231 EXERCÍCIO EXTRA Exercício 1 Uma árvore é um grafo não direcionado no qual dois vértices quaisquer são conectados por exatamente um caminho Em outras palavras qualquer grafo conectado sem ciclos simples é uma árvore Imagine que você tem uma árvore de n nós rotulados de 0 a n1 na qual você pode escolher qualquer nó da árvore como raiz Quando você seleciona um nó x como raiz a árvore resultante tem altura h Entre todas as árvores rotacionadas possíveis aquelas com altura mínima são chamadas de árvores de altura mínima MHTs Dada uma árvore como entrada retorne a menor altura que é possível encontrar ao se escolher qualquer um dos vértices da árvore A altura de uma árvore é o número de arestas no caminho descendente mais longo entre a raiz e uma folha Exemplo 1 Entrada n 4 4 é só a quantidade de nós Eles podem estar arranjados de qualquer maneira Isso é que fará diferença na altura Saída esperada 1 Explicação A altura da árvore é 1 quando a raiz é o nó com rótulo 1 que é a única MHT Exemplo 2 Estrutura de Dados Exercício Extra 1 Entrada n 6 Saída esperada 2 quandos os nós são 3 e 4 Considere qu você pode usar as classes já implementadas from pythondsgraphs import Graph Vertex from pythondsbasic import Queue import collections class Solucaoobject def encontrarArvoresAlturaMinimaself n arestas Caso base se n 1 retorne 0 if n 1 return 0 Cria um dicionário para armazenar os vizinhos de cada nó vizinhos collectionsdefaultdictset for u v in arestas vizinhosuaddv vizinhosvaddu Inicializa a lista de nós do nível anterior e o conjunto de nós não visitados nivelanterior naovisitados set for i in rangen Se o nó tem apenas um vizinho é uma folha if lenvizinhosi 1 nivelanteriorappendi naovisitadosaddi Enquanto houver mais de 2 nós não visitados while lennaovisitados 2 nivelatual for u in nivelanterior naovisitadosdiscardu for v in vizinhosu if v in naovisitados vizinhosvremoveu Se o nó tem apenas um vizinho é uma folha if lenvizinhosv 1 nivelatualappendv nivelanterior nivelatual return listnaovisitados Solicitar valores de entrada ao usuário n intinputDigite o valor de n arestas printDigite os vértices da aresta separados por espaço for in rangen1 u v inputsplit arestasappendintu intv Chamar a função e exibir o resultado resultado SolucaoencontrarArvoresAlturaMiniman arestas printSaída resultado