Árvores Flashcards
Árvore
É um grafo conexo e sem ciclos em que há somente um caminho entre qualquer par de vértices.
Subárvore
É um subgrafo conexo e acíclico de uma árvore.
Floresta
é um grafo que não contém ciclos conexo ou não.
Árvore geradora
é um subgrafo conectado que inclui todos os vértices do grafo original, mas sem formar ciclos.
Árvore geradora mínima
Uma árvore geradora mínima para um grafo com peso é uma árvore geradora que tem o menor peso total possível dentre todas as possíveis árvores geradoras do grafo.
Algoritmo de Kruskal
É um algoritmo para encontrar uma árvore geradora mínima em um grafo ponderado não direcionado.
O algoritmo de Kruskal constrói gradualmente uma árvore geradora mínima, adicionando as arestas de menor peso que não formam ciclos com as arestas já incluídas. O algoritmo para quando todas as arestas tiverem sido verificadas ou quando a árvore geradora mínima estiver completa.
Algoritmo de Prim
É um algoritmo para encontrar uma árvore geradora mínima em um grafo ponderado não direcionado.
O algoritmo de Prim constrói gradualmente uma árvore geradora mínima, começando de um vértice inicial e adicionando, em cada iteração, a aresta de menor peso que liga um vértice visitado a um vértice não visitado. Dessa forma, a árvore geradora mínima vai se expandindo até incluir todos os vértices do grafo.
Árvores de busca
árvores que têm uma estrutura hierárquica. O vértice no topo é chamado de raiz e os outros vértices se ramificando a partir dela são as folhas.
Busca em largura
A busca é feita visitando-se todos os vértices adjacentes ao vértice atual antes de prosseguir para outro vértice.
O algoritmo funciona para grafos não direcionados e direcionados.
Busca em profundidade
é um algoritmo utilizado para explorar e percorrer um grafo. Ele segue uma estratégia de visitar o máximo possível de vértices em uma ramificação antes de retroceder. O algoritmo mantém um registro dos vértices já visitados para evitar ciclos infinitos.
