Recorrido de Grafos

¿Que es un grafo?

Un grafo es una representación de un conjunto de objetos donde algunos pares de objetos están conectados por enlaces. Los objetos interconectados están representados por abstracciones matemáticas llamadas Vértices, y los vínculos que unen algunos pares de vértices se denominan bordes.

¿Que tipos de grafos hay?

Grafo simple  

   Es aquel que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo.

Multigrafo 

 son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.

Multigrafo

Grafo dirigido.

 Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha.

Grafo etiquetado.

 Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices.

Grafo aleatorio.

 Grafo cuyas aristas están asociadas a una probabilidad.

Hipergrafo.

 Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.

Grafo infinito.

 Grafos con conjunto de vértices y aristas de cardinal infinito.

Composición de Grafos.

• Aristas: una relación entre dos vértices de un grafo.                                                                                                                                                                                                                                

• Aristas paralelas: Son dos o más aristas que son incidentes (es decir, que conectan) a al menos dos vértices.
  

• Aristas Adyacentes: dos aristas son adyacentes si tienen un vértice en común.
  

Algoritmo de Prim

  El algoritmo de prim incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le va agregando sucesivamente vértices cuya distancia a los anteriores es la mínima. Esto significa que en casa paso las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.

Algoritmo de Dijkstra

  Determina el camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos en cada arista.

• Lo que quisimos hacer fue comparar los dos algoritmos, para ver su funcionamiento y poder entender como funcionan. 

                                       Click para  descargar el código en C.