min_span_tree_visualizer
1.0.0
Um projeto C ++ para visualizar como dois dos algoritmos de árvore mínima de abrangência (MST) mais comuns - principalmente Kruskal's e Prim. O aplicativo permite ao usuário gerar uma estrutura de árvore aleatoriamente ou importar um de um arquivo e, em seguida, selecione qual algoritmo usar para encontrar o MST. A funcionalidade útil de reprodução é implementada para que o usuário possa ver visualmente passo a passo como os algoritmos chegam à solução final. O usuário tem a capacidade de passar pelo processo de resolução de algoritmo passo a passo ou selecionar uma velocidade de reprodução e vê -lo funcionar, é mágico.
O projeto foi inspirado nos dois vídeos seguintes do YouTube, que eu achei divertido tentar me implementar em C ++:
Animação do algoritmo de Prim
Animação do algoritmo de Kruskal
Na ciência da computação, um gráfico é uma coleção de nós que são conectados juntos pelas arestas, que têm alguma ponderação associada. Em termos práticos, um peso pode dar à vantagem entre dois nós algum significado físico, como distância em metros, tempo em horas ou custo em dólares. Uma árvore é um gráfico sem ciclos. isto é) construído de tal maneira que não há caminho de bordas que possam ser seguidas, o que permitirá que você chegue de volta ao mesmo nó que você deixou. Uma árvore de abrangência é, portanto, um subgraf de algum gráfico que "abrange" ou conecta, todos os vértices do gráfico. Essa árvore de extensão também pode ser uma árvore de abrangência 'mínima' (MST) quando é selecionada de maneira a selecionar bordas que tenham um peso mínimo quando somadas. Acontece que os MSTs são bastante úteis em muitos problemas de otimização e, de fato, o primeiro algoritmo MST foi descoberto ao projetar uma rede de eletricidade para a cidade de Morávia. 1
Embora o primeiro algoritmo a ser descoberto para resolver esse problema tenha sido inventado pelo matemático tcheco Otakar Borůvka, os dois algoritmos mais populares hoje são primos e de Kruskal, que são exemplos de algoritmos gananciosos que funcionam de maneiras ligeiramente diferentes.
O algoritmo de Prim é um algoritmo ganancioso que constrói a borda MST uma de cada vez, examinando todas as bordas de saída de algum nó inicial e adicionando a borda com menor peso ao MST. Dessa maneira, o MST é construído sucessivamente até que todas as arestas sejam exploradas.
Da mesma maneira que o algoritmo de Prim constrói a MST uma borda de cada vez, o algoritmo de Kruskal também o faz, no entanto, o faz começando com vários conjuntos disjuntos de arestas entre nós e junta -se sucessivamente aos conjuntos.
O algoritmo de Chazelle é um algoritmo de tempo quase linear para encontrar um MST.
git clone o repositório da sua máquina local.
Do diretório raiz da execução do repositório:
git clone https://github.com/Microsoft/vcpkg.git
Uma vez feito, cd para a pasta vcpkg e execute:
./bootstrap-vcpkg.sh
Finalmente, corra:
./vcpkg integrate install
Execute cd .. cd build e, em seguida, execute cmake .. -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmake . Se tudo correr bem, você verá a mensagem "Os arquivos de construção foram gravados para ...". Agora você pode abrir o projeto gerado 'Minimum_spanning_tree_visualizer'.
Para executar os testes, clique com o botão direito do mouse e "selecione como projeto de inicialização":
Para executar os testes, clique com o botão direito do mouse e "selecione como projeto de inicialização":
Ó Jistém ProBlému Minimálmm (em um certo problema mínimo) ↩
