Almacena datos de dos tipos:
.Vertices o Nudos .Aristas o
Arcos
DEFINICION
Un grafo es una estructura
de datos utilizada para
representar una colección
de elementos.
CARACTERISTICAS
caracterizada porque cada
elemento puede tener cero, uno o
muchos elementos
TIPOS
GRAFO CONEXO
Es un grafo no dirigido de tal modo que
para cualquier par de nodos existe al
menos un camino que los une.
GRAFO COMPLETO
Es un grafo no direccionado
donde existe un arco entre cada
par de vertices cualesquiera del
mismo.
GRAFO ETIQUETADO
Es la asignacion de etiquetas
representado mediante
enteros.
GRAFO MULTIGRAFO
Es un grafo en el que hay
pares de vertices unidos por
mas de una arista.
ESTUDIO
GRAFOS DIRIGIDOS
Los arcos en el grafo tienen
una direccion asociada.El
primer elemento del arco es
origen y el segundo es
considerado el destino.
GRAFOS NO DIRIGIDOS
Los arcos en el grafo no tienen
una dirección particular,es decir,
son bidireccionales.
REPRESENTACIONES DE GRAFOS
MATRIZ DE ADYACENCIA
Esta matriz consiste en un
arreglo bidimensional de
tamaño "n", donde "n" es la
maxima cantidad de nodos en
el grafo.
LISTA DE ADYACENCIA
Se asocia a cada nodo del grafo
una lista que contenga todos
aquellos nodos que sean
adyacentes a el.
TIPOS DE BUSQUEDA
BUSQUEDA PRIMERO EN AMPLITUD O ANCHURA
Es un algoritmo para recorrer o buscar
elementos en un grafo.Intuitivamente, se
comienza en la raiz.
BUSQUEDA PRIMERO EN PROFUNDIDAD
Es un algoritmo que permite recorrer
todos los nodos de un grafo o árbol de
manera ordenada, pero no uniforme.
ALGORITMOS DE BUSQUEDA
ALGORITMO DE PRIM
Se refiere a tomar las aristas de
menor peso hasta recorrer todo
el grafo sin repetir los nodos.
ALGORITMO DE KRUSKAL
Es unir las aristas de menor peso
pero sin formar ciclos, para
encotrar el arbol de expandido
minimo.
ALGORITMO DE DIJKSTRA
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
interaciones.