Algoritmo de Prim - Árvores Geradoras Mínimas - Algoritmos em Grafos
HTML-код
- Опубликовано: 8 фев 2025
- Neste vídeo vamos aprender o funcionamento do algoritmo de Prim para árvores geradoras mínimas. Porque ele é importante? Para que usamos esse algoritmo? Qual o objetivo principal ao utilizá-lo? Acompanhe o vídeo e descubra. Vamos analisar o seu funcionamento e complexidade.
SE INSCREVA NO CANAL E AJUDE O MEU TRABALHO: www.youtube.co...
-----------
Melhor fonte sobre algoritmos e estruturas de dados: amzn.to/36St31Y
CONCEITOS BÁSICOS DO ALGORITMO DE PRIM:
pt.wikipedia.o...
ALGUNS CONCEITOS BÁSICOS SOBRE TEORIA DOS GRAFOS:
pt.wikipedia.o...
Compartilhe este vídeo com os seus amigos:
• Video
----------
VEJA TAMBÉM NOSSA PLAYLIST DE ALGORITMOS E ESTRUTURAS DE DADOS:
• Invariante de Loop
O canal Aulas de Computação tem como foco disponibilizar notas de aula de diversas disciplinas de cursos de computação, como o objetivo de ajudar alunos que estão cursando cursos da área, professores e também profissionais já graduados. Esses conceitos podem ser úteis para entrevistas de emprego, provas de concurso, etc.
#programação, #algoritmos, #grafos
Muito bom! queria ter você como meu professor na faculdade! parabens!! está me ajudando mt com suas video aulas.
Obrigado Leonardo! Um comentário desse é como um troféu para mim. Fico muito feliz de verdade e me dá forças para continuar. Muito obrigado mesmo!
Eu também, meu professor odeia os alunos dele e é sofrido demais pra explicar uma linhazinha
@@aninham Obrigado Ana! Fico muito feliz que gosta do meu trabalho. Poderia me dar uma força e divulgar o canal para os seus colegas?
fantastico prof. obrigado por esta aula fenomenal.
17:08 Professor, pode explicar porque nessa parte o pai de D foi ele mesmo e não o B? Achei que seria o B porque foi por ele que chegamos no D
obs: acabei de chegar em 19:50 kkkkkkkkkkkkkk. Ótima aula professor, você está me ajudando demais na cadeira de Analise de Algoritmos na faculdade!!
Otimas aulas!! Assisti a playlist toda, gostei mto. Obrigado pela ajuda.
Professor! Continue com este trabalho! Essas suas playlists estão ajudando muito!
Vou continuar sim
Fiquei com uma dúvida na execução desse algoritmo: inicialmente, de A para C, tínhamos peso 5. No final, a árvore geradora ligou esses pontos com peso 8, porque teríamos que passar por todos os outros pontos para chegar em C (então o custo de A para C seria o somatório de todo o caminho). Entendendo que 8 é maior que 5, fiquei com essa dúvida. Achei que o caminho direto de A até C deveria permanecer sendo 5 e não 8.
imagino que seja porque o algoritmo gera um grafo sem ciclos, caso continuasse a aresta de A para C, o grafo teria um ciclo
Muito didático, parabéns pelo trabalho.
Muito obrigado, Vinicius! Se ainda não se inscreveu, se inscreva e fortaleça meu trabalho!
Top
Ótima explicação! Em qual situação seria o pior caso de complexidade O(V²)?
O pior caso vai ser aquele que eu vou ter que avaliar arestas entre vértices igual a quantidade de vezes do número de vértices ao quadrado. No caso um grafo conpleto, nesse caso um grafo com todos os vértices conectados entre si.
@ Muito obrigada :)
@ Adriano, apresentei um ótimo seminário sobre esse algoritmo e seu material me ajudou bastante, obrigada pelos videos e pela explicação, você é fera :) ah, e te referenciei, é claro
Vc falou em ~9:30 que o algoritmo guloso "nunca perde" e que nunca vai existir uma solução melhor do que ele. Mas não seria o caso de que ele sempre encontra a melhor solução local? Na heurística dele ele sempre escolhe o melhor pra o momento que ele tá do processamento, mas globalmente pode não ser a melhor solução. Então ele nem sempre encontra o melhor resultado (mas sempre encontra um).
Na verdade, os algoritmos gulosos conhecem o problema por inteiro. Sendo assim, deveriam sempre encontrar a melhor solução (global). Algoritmos de soluções aproximadas geralmente se concentram em encontrar uma solução aceitável porque seus problemas são computacionalmente impossíveis de se observar por inteiro, por serem muito complexos. Porém fiquei com uma dúvida na execução desse algoritmo: inicialmente, de A para C, tínhamos peso 5. No final, a árvore geradora ligou esses pontos com peso 8, porque teríamos que passar por todos os outros pontos para chegar em C. Entendendo que 8 é maior que 5, fiquei com essa dúvida. Achei que o caminho direto de A até C deveria permanecer.
Tenho uma dúvida. No final, chega-se a por E. No total, o caminho seria de custo 8. Sendo que saindo de A, poderia se chegar a C com custo 5, se verificarmos o grado inicial. Não entendi esse ponto.
O algoritmo de prim avalia o menor curso por aresta e não pelo valor total dos pesos.
Essa lista de prioridades pode ser implementada *apenas* com heap minimo ou é apenas uma sugestão?
Oi Ana, tudo bem? É apenas uma sugestão. Pode usar outras estruturas. Entretanto a mais rápida é o heap de Fibonacci.
pq tu iniciou a key de A como 0 em vez de infinito assim como nos outros vértices? n entendi isso
Olá, o vértice com K = 0 é aquele em que eu vou iniciar o algoritmo. Ele é o vértice com valor de chave = 0 depois eu olho os pesos dos vértices adjacentes e vou atualizando os k's dos outros vértices. O primeiro sempre vai ter k=0
esse E ai é do que?
na complexidade
@@lucascamillo8272 melhor caso O = E log V e no pior caso O=V2 (lê-se v ao quadrado).