Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

// Algoritmo de Prim

No description
by

Yurs Sanchez

on 15 October 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of // Algoritmo de Prim


1. Se selecciona un nodo cualquiera siendo
éste el nodo de partida.
2. Se considera la arista de menor valor
incidente al nodo marcado anteriormente,
y se marca el nodo que corresponda
a dicha arista.
3. Se repite el literal dos siempre que la
arista elegida enlace un nodo marcado
junto a otro que no lo esté.
4. El proceso finaliza cuando se han marcado
todos los nodos del grafo.
Algoritmo
de Prim
El algoritmo de Prim ayuda a ahorrar recursos, llegando a cada uno de sus nodos, por lo tanto, el tipo de estructura de datos que emplea es el de cola por prioridad.
El algoritmo de Prim es un algoritmo de la teoría de grafos que encuentra un árbol de expansión mínima para un grafo ponderado conexo. Esto significa que se encuentra un subconjunto de las aristas que forma un árbol que incluye todos los nodos, donde el total peso de todas las aristas en el árbol se reduce al mínimo.
Algoritmo de Prim
¡¡¡ Gracias por su
Atención !!!
5
7
9
8
7
15
6
8
11
9
5
Funcionamiento

. Se inicia escogiendo un nodo cualquiera, del cual de desprenda una arista con una peso pequeño y este será el nodo de partida.
. Escogemos la arista de menor peso o valor que sale del nodo marcado y lo conectamos con el siguiente nodo.
Repetir el paso 2 escogiendo las aristas de menor peso.
El algoritmo termina una vez estén todos los nodos conectados.

El algoritmo de Prim resuelve el problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal
manera que la suma de los pesos de las aristas que lo constituye es mínima.
[Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.Entendiendo la prioridad como un valor numérico y asignando a altas prioridades valores pequeños, las colas de prioridad nos permiten añadir elementos en cualquier orden y recuperarlos de menor a mayor]
¿Preguntas?
Para implementar este algoritmo eficientemente, se puede mantener una tabla donde, para cada nodo de V-A, se almacena el costo del arco más barato que lo conecta al conjunto A. Estos costos pueden cambiar en cada iteración.
Si se organiza la tabla como una cola de prioridad, el tiempo total es O(m log n). Si se deja la tabla desordenada y se busca linealmente en cada iteración, el costo es O(n2). Esto último es mejor que lo anterior si el grafo es denso, pero no si está cerca de ser un grafo completo.
COMPLEJIDAD
Cola de Prioridad
El algoritmo funciona de la siguiente manera:
Pseudocodigo
Ejemplo de cableado eléctrico
una de las mejores aplicaciones de este algoritmo es para ahorro de material en cableado
Yurley Sánchez
&
Andrés Maldonado
UIS
INTRODUCCIÓN
Full transcript