Grafos

son estructuras de datos no lineales que tienen una

naturaleza dinámica. Su estudio podría dividirse en dos grandes

bloques:

Grafos Dirigidos

Grafos No Dirigidos

Los arcos en el grafo tienen una dirección asociada. El primer

elemento del arco es el origen y el segundo es considerado el

destino

Los arcos en el grafo no tienen una dirección particular, es decir, son bidireccionales.

Estructura

Un grafo es una estructura de datos que almacena datos de dos tipos:· Vértices o nudos, con un valor almacenado.· Aristas o arcos: cada una conecta a un vértice con otro, y puede tener un valor almacenado.

Tipos de Grafos

Grafo Conexo Grafo Completo

es un grafo no dirigido de tal modo que para cualquier par de

nodos existe al menos un camino que los une

es un grafo no direccionado donde existe un arco entre cada par de vértices cualesquiera del

mismo

Tipos de Grafos

Grafo Etiquetado

es la asignación de etiquetas representado mediante

enteros, a las aristas o vértices o ambos de un grafo, se refiere

a un grafo con vértices etiquetados con todas las

etiquetas distintas

Multígrafo

es un grafo en el que hay pares de vértices unidos por más de una arista, es decir, que tiene

aristas múltiples

Representaciones de Grafos

Matriz de Adyacencia

Lista de Adyacencia

Esta matriz consiste en un arreglo bidimensional de tamaño “n”,

donde “n” es la máxima cantidad de nodos en el grafo. Cada casilla de la matriz se carga con valores

verdadero “V” o falso “F” en caso de que posea un camino de un

nodo o fila con columna. En caso de los grafos no dirigidos la matriz será

simétrica.

se asocia a cada nodo del grafo una lista que contenga todos

aquellos nodos que sean adyacentes a él.

Tipos de Búsquedas o Recorridos sobre

grafos

Búsqueda primero en profundidad

Búsqueda primero en amplitud o anchura

es un algoritmo que permite recorrer todos los nodos de un grafo o árbol de manera ordenada, pero

no uniforme

es un algoritmo para recorrer o buscar elementos en un grafo. Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de

un grafo) y se exploran todos los vecinos de este nodo

Algoritmos de Búsqueda

Algoritmo de Kruskal

Algoritmo de Prim

Algoritmo de Dijkstra

Se refiere a tomar las aristas de menor peso hasta recorrer todo

el grafo sin repetir los nodos.

Es unir las aristas de menor peso pero sin formar ciclos, para encontrar el árbol de

expandido mínimo

es un algoritmo para la determinación del camino más corto dado un vértice

origen al resto de vértices en un grafo con pesos en cada

arista, donde se va recorriendo el grafo llevando

la siguiente fórmula: [Distancia acumulada, Procedencia]^Nro de

iteraciones.