5489230
Description
Mind Map by Abraham Garcia7041, updated more than 1 year ago
|
Created by Abraham Garcia7041
almost 8 years ago
|
|
GRAFOS
- ESTRUCTURA
- Almacena datos de dos tipos:
.Vertices o Nudos .Aristas o
Arcos
- 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
- caracterizada porque cada
elemento puede tener cero, uno o
muchos elementos
- CARACTERISTICAS
- Un grafo es una estructura
de datos utilizada para
representar una colección
de 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.
- 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.
- 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.
- 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.
- Es un grafo en el que hay
pares de vertices unidos por
mas de una arista.
- GRAFO CONEXO
- 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.
- 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.
- Los arcos en el grafo no tienen
una dirección particular,es decir,
son bidireccionales.
- GRAFOS DIRIGIDOS
- 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.
- 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.
- Se asocia a cada nodo del grafo
una lista que contenga todos
aquellos nodos que sean
adyacentes a el.
- MATRIZ DE ADYACENCIA
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- ALGORITMO DE PRIM
- BUSQUEDA PRIMERO EN AMPLITUD O ANCHURA
Want to create your own Mind Maps for free with GoConqr? Learn more.