MAPA MENTAL
miércoles, 28 de noviembre de 2012
UNIDAD III Grafos y Arboles
Resumen
GRAFOS
Un
grafo en el ámbito de las ciencias
de la computación es
una estructura
de datos, en concreto
un tipo
abstracto de datos
(TAD), que consiste en un conjunto de nodos
(también llamados vértices) y un conjunto de arcos
(aristas) que establecen relaciones entre los
nodos. El concepto de grafo TAD desciende directamente del
concepto matemático de grafo.
Informalmente
se define como G = (V, E), siendo los elementos de V los vértices, y los
elementos de E, las aristas (edges en inglés). Formalmente, un grafo,
G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y
E es un conjunto que consta de dos elementos de V.
Formas de representación
Existen diferentes implementaciones del tipo grafo:
con una matriz de adyacencias (forma acotada) y con listas y metalistas de
adyacencia (no acotadas).
- Matriz de adyacencias: se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.
- Lista
de adyacencias: se
asocia a cada nodo del grafo una lista que contenga todos aquellos nodos
que sean adyacentes a él.
Especificación de los tipos abstractos de datos de un
grafo no dirigido
GENERADORES
Crear
un grafo vacío: Devuelve un grafo vacío.
- op crearGrafo
: -> Grafo [ctor] .
Añadir
una arista: Dado un grafo, añade una relación entre dos nodos de dicho grafo.
- op
añadirArista : Grafo Nodo Nodo -> [Grafo] [ctor] .
Añadir
un nodo: Dado un grafo, incluye un nodo en el en caso en el que no exista
previamente.
- op añadirNodo
: Grafo Nodo -> Grafo [ctor] .
CONSTRUCTORES
Borrar
nodo: Devuelve un grafo sin un nodo y las aristas relacionadas con él. Si dicho
nodo no existe se devuelve el grafo inicial.
- op borrarNodo
: Grafo Nodo -> Grafo .
Borrar
arista: Devuelve un grafo sin la arista indicada. En caso de que la arista no
exista devuelve el grafo inicial.
- op
borrarArista : Grafo Nodo Nodo -> Grafo .
SELECTORES
Grafo
Vacio: Comprueba si un grafo no tiene ningún nodo.
- op esVacio :
Grafo -> Bool .
Contener
Nodo: Comprueba si un nodo pertenece a un grafo.
- op contiene:
Grafo Nodo -> Bool .
Adyacentes:
Comprueba si dos nodos tienen una arista que los relacione.
- op adyacentes:
Grafo Nodo Nodo -> Bool .
Para
la especificación de un grafo dirigido tenemos que modificar algunas de las
ecuaciones de las operaciones borrar Arista y añadir Arista para que no se
considere el caso de aristas bidireccionales.
Y
sustituir la operación adyacente por:
- op predecesor:
Grafo Nodo Nodo -> Bool .
- op sucesor:
Grafo Nodo Nodo -> Bool .
Segunda
Definición de Grafos
El origen de la palabra grafo es griego y su
significado etimológico es "trazar". Aparece con gran frecuencia como
respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser los
siguientes: un gráfico de una serie de tareas a realizar indicando su
secuenciación (un organigrama),grafos matemáticos que representan las
relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o
aéreos o la red eléctrica de una ciudad.(Véase la figura 1).En cada caso, es
conveniente representar gráficamente el problema dibujando un grafo como un
conjunto de puntos(vértices)con líneas conectándolos (arcos).
De aquí se podría deducir que un grafo es
básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio,
es decir, un conjunto de puntos y un conjunto de líneas tomado de entre el
conjunto de líneas que une cada par de vértices. Por otro lado, y debido a su
generalidad y a la gran diversidad de formas que pueden usarse, resulta
complejo tratar con todas las ideas relacionadas con un grafo.
Los grafos son estructuras de datos no lineales que
tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos
grandes bloques:
- Grafos
Dirigidos.
- Grafos
no Dirigidos (pueden ser considerados un caso particular de los
anteriores).
Un ejemplo de grafo dirigido lo constituye la red
de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra
en un único sentido. Por el contrario, la red de carreteras de un país
representa en general un grafo no dirigido, puesto que una misma carretera
puede ser recorrida en ambos sentidos. No obstante, podemos dar unas
definiciones generales para ambos tipos.
A continuación daremos definiciones de los dos
tipos de grafos y de los conceptos que llevan asociados.
no dirigido.
EJEMPLO:
Estructuras
Internas del TDA grafo.
/* Implementacion basada en una lista de nodos de los que cuelga */
/* la lista de arcos de salida. */
#include
#include
#include
#define TE 5
#define Nulo NULL
typedef char *tetq;
typedef float tvalor;
typedef struct arco {
struct nodo *origen;
struct nodo *destino;
tvalor valor;
struct arco *sig;
} *tarco;
typedef struct nodo {
int nodo;
tetq etiq;
tarco ady;
tarco inc;
struct nodo *sig;
} *tnodo;
typedef tnodo tgrafo;
IMPLEMENTACIÓN
DE LAS PRIMITIVAS.
tgrafo Crear(void)
{
tnodo aux;
aux = (tnodo)malloc(sizeof(struct nodo));
if (aux == NULL) {
error(\"Error en Crear.\");
} else {
aux->nodo = 0;
aux->etiq = NULL;
aux->ady = NULL;
aux->inc = NULL;
aux->sig = NULL;
return aux;
}
}
void BorrarArco(tnodo org, tnodo
dest, tgrafo g)
{
tarco a,ant;
int enc=0;
if (org->ady==NULL) return;
else if (org->ady->destino==dest) {
a = org->ady;
org->ady = a->sig;
free(a);
}
else {
ant = org->ady;
a = ant->sig;
while (!enc && (a!=NULL)) {
if (a->destino==dest) enc=1;
else {
a = a->sig;
ant
= ant->sig;
}
}
if (a==NULL) return;
else {
ant->sig = a->sig;
free(a);
}
}
enc=0;
if (dest->inc==NULL) return;
else if (dest->inc->origen==org) {
a = dest->inc;
dest->inc = a->sig;
free(a);
}
else {
ant = dest->inc;
a = ant->sig;
while (!enc && (a!=NULL)) {
if (a->origen == org) enc=1;
else {
a = a->sig;
ant = ant->sig;
}
}
if (a==NULL) return;
else {
ant->sig = a->sig;
free(a);
}
}
}
void Destruir(tgrafo G)
{
tnodo n;
tarco a_aux;
while (g->sig != NULL) {
n = g->sig;
while (n->ady != NULL) {
a_aux =
n->ady;
n->ady =
a_aux->sig;
free(a_aux);
}
while (n->inc != NULL) {
a_aux = n->inc;
n->inc = a_aux->sig;
free(a_aux);
}
g->sig = n->sig;
free(n->etiq);
free(n);
}
free(g);
}
Un
grafo dirigido G consiste en un conjunto de vértices V y un conjunto de arcos o aristas A. Los vertice se denominan también nodos o puntos.
Un
arco, es un par ordenado de vértices(V,W) donde V es el vértice inicial y W es el vértice terminal del arco. Un arco se expresa como:
V–>W
Los
vértice de un grafo pueden usarse para representar objetos. Los
arcos se utilizan para representar relaciones entre estos objetos.
Las
aplicaciones más importantes de los grafos
son las siguientes:
Rutas
entre ciudades.
Determinar
tiempos máximos y mínimos en un proceso.
Flujo
y control en un programa.
ARBOLES
Un árbol es una estructura no lineal en la que cada
nodo puede apuntar a uno o varios nodos.
También se suele dar una definición recursiva: un
árbol es una estructura en compuesta por un dato y varios árboles.
Esto son definiciones simples. Pero las
características que implican no lo son tanto.
Árbol
Definiremos varios conceptos. En relación con otros
nodos:
- Nodo
hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En
el ejemplo, 'L' y 'M' son hijos de 'G'.
- Nodo
padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo
'A' es padre de 'B', 'C' y 'D'.
Los árboles con los que trabajaremos tienen otra
característica importante: cada nodo sólo puede ser apuntado por otro nodo, es
decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén
fuertemente jerarquizados, y es lo que en realidad les da la apariencia de
árboles.
En cuanto a la posición dentro del árbol:
- Nodo
raíz: nodo que no tiene padre. Este es el nodo que usaremos para
referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
- Nodo
hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I',
'K', 'L', 'M', 'N' y 'O'.
- Nodo
rama: aunque esta definición apenas la usaremos, estos son los nodos que
no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo:
'B', 'C', 'D', 'E', 'G' y 'J'.
Otra característica que normalmente tendrán
nuestros árboles es que todos los nodos contengan el mismo número de punteros,
es decir, usaremos la misma estructura para todos los nodos del árbol. Esto
hace que la estructura sea más sencilla, y por lo tanto también los programas
para trabajar con ellos.
Tampoco es necesario que todos los nodos hijos de
un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno
de los punteros de cada nodo.
Un árbol en el que en cada nodo o bien todos o
ninguno de los hijos existe, se llama árbol completo.
En una cosa, los árboles se parecen al resto de las
estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos
considerarlo como una estructura independiente. Es decir, un nodo cualquiera
puede ser considerado como la raíz de un árbol completo.
Existen otros conceptos que definen las características
del árbol, en relación a su tamaño:
- Orden:
es el número potencial de hijos que puede tener cada elemento de árbol. De
este modo, diremos que un árbol en el que cada nodo puede apuntar a otros
dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
- Grado:
el número de hijos que tiene el elemento con más hijos dentro del árbol.
En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D'
tienen tres hijos, y no existen elementos con más de tres hijos.
- Nivel:
se define para cada elemento del árbol como la distancia a la raíz, medida
en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así
sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene
nivel 2, y el nodo 'N', nivel 3.
- Altura:
la altura de un árbol se define como el nivel del nodo de mayor nivel.
Como cada nodo de un árbol puede considerarse a su vez como la raíz de un
árbol, también podemos hablar de altura de ramas. El árbol del ejemplo
tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la
'H' cero, etc.
Los árboles de orden dos son bastante especiales,
de hecho les dedicaremos varios capítulos. Estos árboles se conocen también
como árboles binarios.
Frecuentemente, aunque tampoco es estrictamente
necesario, para hacer más fácil moverse a través del árbol, añadiremos un
puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en
dirección a la raíz, y no sólo hacia las hojas.
Es importante conservar siempre el nodo raíz ya que
es el nodo a partir del cual se desarrolla el árbol, si perdemos este nodo,
perderemos el acceso a todo el árbol.
El nodo típico de un árbol difiere de los nodos que
hemos visto hasta ahora para listas, aunque sólo en el número de nodos. Veamos
un ejemplo de nodo para crear árboles de orden tres:
struct
nodo \{
int dato;
struct nodo *rama1;
struct nodo *rama2;
struct nodo *rama3;
};
O generalizando más:
#define ORDEN 5
struct nodo \{
int dato;
struct nodo *rama[ORDEN];
};
Para C, y basándonos en la declaración de nodo que
hemos visto más arriba, trabajaremos con los siguientes tipos:
typedef
struct _nodo \{
int dato;
struct _nodo *rama[ORDEN];
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Arbol;
Al igual que hicimos con las listas que hemos visto
hasta ahora, declaramos un tipo tipoNodo para declarar nodos, y un tipo pNodo
para es el tipo para declarar punteros a un nodo.
Arbol es el tipo para declarar árboles de orden
ORDEN.
Segunda
de Definición de Arboles
En
ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la
forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre
la que se construye el árbol y puede tener cero o más nodos hijos conectados a
él. Se dice que un nodo
es padre de un nodo
si existe un enlace desde
hasta
(en ese caso, también decimos
que
es hijo de
). Sólo puede haber un único
nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como
hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como
rama.
Formalmente, podemos definir un árbol de la siguiente
forma:
- Caso
base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
- Un
nuevo árbol a partir de un nodo
Una sucesión de nodos del árbol, de forma que entre
cada dos nodos consecutivos de la sucesión haya una relación de parentesco,
decimos que es un recorrido árbol. Existen dos recorridos típicos para listar
los nodos de un árbol: primero en profundidad y primero en anchura. En el
primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta
llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente
hijo y así sucesivamente. En el segundo, por su parte, antes de listar los
nodos de nivel
(a distancia
aristas de la raíz), se
deben haber listado todos los de nivel
. Otros recorridos típicos
del árbol son preorden, postorden e inorden:
- El
recorrido en preorden, también llamado orden previo consiste en recorrer
en primer lugar la raíz y luego cada uno de los hijos
- El
recorrido en inorden, también llamado orden simétrico (aunque este nombre
sólo cobra significado en los árboles binarios) consiste en recorrer en
primer lugar
- El
recorrido en postorden, también llamado orden posterior consiste en
recorrer en primer lugar cada uno de los hijos
Finalmente, puede decirse que esta estructura es
una representación del concepto de árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico.
Tipos de árboles
.png){kind=link}
.png){kind=link}
Ejemplo
de árbol (binario).
Suscribirse a:
Entradas (Atom)