Zusammenfassung der Ressource
GRAFOS
- ESTRUCTURA
- 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.