Grafos:
Los grafos son estructuras de datos que permiten representar diferentes tipos de relaciones entre objetos, se utilizan en el manejo de redes, en la construcción de circuitos eléctricos, en la estrategia de ventas, economía, cartografía etc.
Grafo Dirigido:
Es un tipo de grafo en el cual las aristas o arcos tienen una dirección definida es decir:
Como pueden observar el arco tiene una dirección o sentido definido.
Adyacencia:
Existe adyacencia entre dos vértices si están unidos por un arco o arista.
- Para el grafo seria:
a y c son adyacentes o viceversa, c y a son adyacentes.
b y d son adyacentes o viceversa, d y b son adyacentes.
c y d son adyacentes o viceversa, d y c son adyacentes.
Observe que los vértices a y d no están conectados por un arco por lo tanto no son adyacentes, lo mismo pasa con los vértices c y b.
- Para el dígrafo:
Adyacencia: - Desde
- Hacia
a es adyacente "hacia" b
a es adyacente "desde" c
d es adyacente "desde" b
Si notan el "hacia" lo utilizamos cuando es de un vértice apuntando al otro mientras que el "desde" lo utilizamos cuando del vértice llega un arco.
Incidencia:
Los arcos inciden en los vértices, si una de sus puntas llega a ese vértice.
- Para el grafo seria:
- Para el dígrafo seria:
El arco " f " es incidente en D
Grado de un vértice:
El grado de un vértice es el numero de arcos que inciden en ese vértice es decir:
El grado del vértice " 1 " es 4
El grado del vértice " 2 " es 4
El grado del vértice " 3 " es 2
El grado del vértice " 4 " es 4
El grado del vértice " 5 " es 2
El grado del vértice " 6 " es 4
El grado del vértice " 7 " es 4
El grado del vértice " 8 " es 2
Tipos de grafos
- Componentes conectados separadamente:
Estos grafos pueden tener varios componentes separados es decir, si observan del nodo A al nodo D no puedo pasar directamente sino tengo que pasar por B para poder llegar a D.
Grafo
Dígrafo
Para que un grafo y un dígrafo estén fuertemente conectados es empezando desde cualquier vértice poder llegar a los demás.
- Dígrafo débilmente conectado:
Un dígrafo débilmente conectado es cuando se empieza desde cualquier vértice pero no puede llegar a todos los demás vértices es decir:
Si queremos llegar desde el vértice A al vértice E, veremos que no se puede llegar porque no hay ningún arco que apunte al vértice E por lo tanto lo llamamos un dígrafo débilmente conectado.
- Camino simple
si partiendo de un vértice podemos recorrer el grafo sin repetir vértices ni arcos es decir:
Si partimos de A podemos recorrer todos los vértices sin repetir arcos
- Grafo Euleriano:
El grafo euleriano consiste en comenzar desde cualquier vértice y recorrer todos los vértices para llegar de nuevo al punto de partida, pero hay que tener en cuenta de que al recorrer el grafo no se pueden repetir arcos pero si se pueden repetir vértices.
Como hay que recorrer todo el grafo y terminar en el mismo vértice de partida entonces si empezamos desde el vértice " 1 ", debemos terminar en el mismo vértice entonces quedaría:
1 - 4 - 7 - 8 - 3 - 2 - 4 - 6 - 5 - 1 , como ven recorrimos todos los vértices y llegamos al mismo punto de partida sin repetir arcos.
Si partiendo de cualquier vértice podemos recorrer los vértices sin repetir ninguno y finalmente podemos llegar al vértice origen. Los arcos se pueden recorrer una o mas veces.
Ejemplo:
Si hacemos el recorrido nos quedaria:
1 - 5 - 6 - 7 - 8 - 3 - 2 - 4 - 1
como pueden observar no repetimos ningún vértice.
- Grafo regular
Es regular si todos los vértices tienen el mismo grado
este es un grafo regular ya que si nos fijamos todos los vértices tienen el mismo grado, su grado es 1.
- Grafo cíclico:
Un grafo es cíclico si se parte del vértice y llega al mismo vértice hay que tener en cuenta que se presentan en los dígrafos es decir:
- Multigrafo:
Es un grafo donde dos vértices están unidos por mas de un arco
- Grafo completo:
Un grafo es completo si cada vértice tiene un grado igual a n-1 donde n es el numero de vértices que componen el grafo
Si nos fijamos bien se cumple la regla ya que el grafo esta compuesto por 4 vértices y su grado es de 3, pero también podemos interpretarlo como: cada vértice se conecta directamente con los demás.
En este link encontraras mas tipos de grafos
http://docencia.udea.edu.co/regionalizacion/teoriaderedes/tiposu1.html
Lista de adyacencia
Se hace con un arreglo de listas, cada lista almacena los adjuntos a un vértice dado
Es decir:
si dice que tiene que ser las adjuntos a un vértice dado, entonces los adjuntos al vértice A serian B y E. Así hay que hacerlo con todos los vertices del grafo y quedaría representado de la siguiente manera
Donde la primera columna son los vértices que vamos escogiendo para hacer la lista de adyacencia.
Aquí un vídeo donde podrás entender mejor el concepto de lista de adyacencia
Matriz de adyacencia
La matriz de adyacencia tiene el mismo objetivo que el de la lista de adyacencia, lo que cambia ahora es que vamos a guardar los vértices adyacentes en una matriz.
El tamaño de la matriz la decidimos por el numero de vértices que hay en el grafo, es decir, si el grafo tiene 5 vértices, la matriz sera de 5x5, si el grafo tiene 8 vértices entonces la matriz sera de 8x8.
Ejemplo:
Realizaremos la matriz de adyacencia a partir del grafo que utilizamos en la lista de adyacencia.
Entonces si realizamos la matriz de adyacencia quedaría de la siguiente maneraLa matriz de adyacencia tiene el mismo objetivo que el de la lista de adyacencia, lo que cambia ahora es que vamos a guardar los vértices adyacentes en una matriz.
El tamaño de la matriz la decidimos por el numero de vértices que hay en el grafo, es decir, si el grafo tiene 5 vértices, la matriz sera de 5x5, si el grafo tiene 8 vértices entonces la matriz sera de 8x8.
Ejemplo:
Realizaremos la matriz de adyacencia a partir del grafo que utilizamos en la lista de adyacencia.
Como ven la matriz es de 6x6 por que el grafo contiene 6 vertices, lo siguiente es colocar 0 y 1 dentro de la matriz, el " 0 " se coloca cuando un vertice no es adyacente a otro.
Es decir por ejemplo del vertice "A" al vertice "C"si se fijan en el grafo no hay un arco que los conecte por lo tanto no son adyacentes, entonces en la matriz se coloca un cero.
Así lo hacemos con los demás vértices. Si hay que colocar un "1" es por que entre dos vértices hay adyacencia como se ve de "A" a "B" o de "A" a "E", y si nos devolvemos y miramos el grafo entre "A" y "B" hay un arco que los une como también hay un arco de "A" a "E". Así lo hacemos con los demás vértices.
Este es un vídeo para una mejor comprensión de la matriz de adyacencia.
Matriz de caminosEste es un vídeo para una mejor comprensión de la matriz de adyacencia.
La matriz de caminos consiste en saber cuantos caminos de longitud n existen entre un vértice y otro
Donde
n = al numero de arcos que se recorren.
¿cuantos caminos hay de "A" a "F" para n=3?
Observamos y nos damos cuenta de que hay 2 caminos los cuales son:
A - B - D - F, y el otro es de A - E - C - F.
Pero para no hacer este proceso tan largo y complicado hacemos la matriz de caminos el cual consiste en multiplicar la matriz de adyacencia.
Hay que tener en cuenta que para multiplicar matrices es "fila x columna" como se multiplica normalmente.
Entonces para saber la matriz de caminos para n=2, solo debemos multiplicar la matriz de adyacencia por ella misma.
Si queremos saber la matriz de caminos para n=3, debemos multiplicar la matriz de adyacencia por la matriz para n=2.
Para entenderlo mejor haremos un ejemplo para n=3 de un digrafo.
Lo primero es crear la matriz de adyacencia entonces nos quedaría:
Ahora multiplicamos la matriz por ella misma para obtener la matriz de caminos para n=2, entonces nos quedaría:
Después de tener la matriz de caminos para n=2, ahora tomamos la matriz adyacente y la multiplicamos por la matriz de caminos para n=2, con esto obtenemos la matriz de caminos para n=3. Entonces al multiplicarla nos quedaría:
Y así obtenemos la matriz de caminos para n=3.
Dígrafos fuertemente conectados
Un dígrafo esta fuertemente conectado si desde cualquier vértice podemos llegar a todos los demás.
Para saber si está fuertemente conectado es necesario hallar la sumatoria de matrices.
M: las matrices para n=1, n=2 etc...
S: la sumatoria de matrices.
Entonces si necesitamos hallar la sumatoria de matrices seria primero conseguir la matriz de adyacencia y después hacer las matrices de caminos hasta n=5, es decir necesitamos hacer 5 matrices, y una sexta que seria la sumatoria de estas 5 matrices.
Para hacer un ejemplo vamos a trabajar con el dígrafo anterior y miraremos si es un dígrafo fuertemente conectado, Al hallar la sumatoria de matrices también estamos hallando todos los caminos que hay de un vértice a otro.
Ejemplo:
Entonces como ya sabemos lo primero es hallar la matriz de adyacencia que ya la tenemos y es:
Para n=2
Para n=3
Para n=4, en esta matriz hay dos posibilidades de hacerla
Ahora para hacer la suma de matrices simplemente es tomar las 5 matrices y sumarlas. Se suman como se suma una matriz normal, entonces la sumatoria de matrices nos quedaría:
Si no nos da un cero en la sumatoria de matrices, eso nos quiere decir que el dígrafo está fuertemente conectado.
Algoritmos
Algoritmo de Warshall
"Este escrito fue elaborado por el estudiante Jeisson Gonzalez de la universidad INCCA de Colombia de la facultad de ingeniería de sistemas".
Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo entre un par de vértices, como resultado nos da la mejor ruta para poder llegar al vértice destino en grafos dirigidos Como resultado nos dará una matriz de clausura transitiva.
Ejemplo:
En este link pueden apreciar la imagen mas grande
Y en este vídeo dan una explicación del algoritmo de Prim
Algoritmo de Floyd
"Este escrito fue elaborado por la estudiante luisa Aponte de la universidad INCCA de Colombia de la facultad de ingeniería de sistemas".
EJEMPLO:
Y así obtenemos la matriz de caminos para n=3.
Dígrafos fuertemente conectados
Un dígrafo esta fuertemente conectado si desde cualquier vértice podemos llegar a todos los demás.
Para saber si está fuertemente conectado es necesario hallar la sumatoria de matrices.
S= M + M2 + M3 + M4...+M(NV-1)Donde NV es : numero de vértices
M: las matrices para n=1, n=2 etc...
S: la sumatoria de matrices.
Entonces si necesitamos hallar la sumatoria de matrices seria primero conseguir la matriz de adyacencia y después hacer las matrices de caminos hasta n=5, es decir necesitamos hacer 5 matrices, y una sexta que seria la sumatoria de estas 5 matrices.
Para hacer un ejemplo vamos a trabajar con el dígrafo anterior y miraremos si es un dígrafo fuertemente conectado, Al hallar la sumatoria de matrices también estamos hallando todos los caminos que hay de un vértice a otro.
Ejemplo:
Entonces como ya sabemos lo primero es hallar la matriz de adyacencia que ya la tenemos y es:
Para n=2
Para n=3
Para n=4, en esta matriz hay dos posibilidades de hacerla
- Multiplicando la matriz de adyacencia y la matriz de caminos para n=3, con esto nos da la matriz para n=4.
- Multiplicando la matriz para n=2 con ella misma para que nos de la matriz de caminos para n=4.
Nos va a dar el mismo resultado con cualquiera de las dos formas entonces al hacerla nos quedaría la matriz:
Para la matriz n=5, también hay dos opciones:
- Multiplicar la matriz de adyacencia con la matriz de caminos para n=4, para que así nos de la matriz de caminos para n=5.
- Multiplicar la matriz para n=2 con la matriz n=3, para que asi nos de la matriz para n=5.
También nos debe de dar la misma matriz por cualquiera de las dos formas, entonces la matriz para n=5 nos quedaría:
Ahora para hacer la suma de matrices simplemente es tomar las 5 matrices y sumarlas. Se suman como se suma una matriz normal, entonces la sumatoria de matrices nos quedaría:
Si no nos da un cero en la sumatoria de matrices, eso nos quiere decir que el dígrafo está fuertemente conectado.
Algoritmos
Algoritmo de Warshall
"Este escrito fue elaborado por el estudiante Jeisson Gonzalez de la universidad INCCA de Colombia de la facultad de ingeniería de sistemas".
Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo entre un par de vértices, como resultado nos da la mejor ruta para poder llegar al vértice destino en grafos dirigidos Como resultado nos dará una matriz de clausura transitiva.
Ejemplo:
PASOS
1)
Hallamos la matriz de adyacencia.
2) Tomamos cada vértice como pivote llenando
su respectiva matriz dependiendo si hay camino o no.
3) Como resultado nos da una matriz de
adyacencia transitiva con la cual podemos saber si hay un camino de un vértice
cualquiera a otro vértice elegido al azar.
PIVOTE = cuando se dice
tomamos el vértice como pivote quiere decir que podemos formar una conexión
directa entre un vértice y un tercero, como
si el vértice tomado como pivote no estuviera.
Matriz de adyacencia.
a
|
b
|
c
|
D
|
|
a
|
0
|
1
|
0
|
0
|
b
|
0
|
0
|
1
|
0
|
c
|
1
|
0
|
0
|
1
|
d
|
0
|
0
|
0
|
0
|
·Tomamos como pivote a (a)
M1 (a)
a
|
b
|
c
|
D
|
|
a
|
0
|
1
|
0
|
0
|
b
|
0
|
0
|
1
|
0
|
c
|
1
|
1
|
0
|
1
|
d
|
0
|
0
|
0
|
0
|
·Tomamos como pivote a (b)
sin olvidar que (a) sigue siendo pivote
M2 (b)
a
|
b
|
c
|
D
|
|
a
|
0
|
1
|
1
|
0
|
b
|
0
|
0
|
1
|
0
|
c
|
1
|
1
|
1
|
1
|
d
|
0
|
0
|
0
|
0
|
· Tomamos como pivote a
(c) sin olvidar que los anteriores
vértices siguen siendo pivotes en este caso
(a) y (b)
M3 (c)
a
|
b
|
c
|
D
|
|
a
|
1
|
1
|
1
|
1
|
b
|
1
|
1
|
1
|
1
|
c
|
1
|
1
|
1
|
1
|
d
|
0
|
0
|
0
|
0
|
· No realizamos la matriz con
el pivote (d) ya que no tiene ningún arco de adyacencia por lo tanto la matriz serian ceros ( 0 )
·Matriz de clausura transitiva.
a
|
b
|
c
|
D
|
|
a
|
1
|
1
|
1
|
1
|
b
|
1
|
1
|
1
|
1
|
c
|
1
|
1
|
1
|
1
|
d
|
0
|
0
|
0
|
0
|
Este es un link donde podrás ver el algoritmo de warshall
https://www.youtube.com/watch?v=UIAX9Lj85Is
Código del algoritmo de Warshall
https://www.youtube.com/watch?v=UIAX9Lj85Is
Código del algoritmo de Warshall
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "alloc.h"
#define MAXIMO 20
#define PR(x) printf ("%s",x)
#define SALTO printf ("\n")
void main() {
int
M[MAXIMO][MAXIMO],T[MAXIMO][MAXIMO];
int
nv,i;
void
listar_g (int g[][MAXIMO], int nv);
int
lea_grafo (int grafo[][MAXIMO]);
void
WARSHALL (int M[][MAXIMO], int T[][MAXIMO], int nv);
nv = lea_grafo (M);
listar_g (M ,nv);
SALTO;
getch();
WARSHALL
(M,T,nv);
listar_g (T,nv);
SALTO;
getch();
}
void WARSHALL (int M[][MAXIMO], int T[][MAXIMO], int
nv)
{
int
i,j,k;
void
listar_g (int g[][MAXIMO], int nv);
void
copiar (int a[][MAXIMO], int b[][MAXIMO],int nv);
copiar
(T, M, nv);
for
(k=1; k<=nv; k++) {
for
(i=1; i<=nv; i++) {
if
(i!=k) {
if
(T[i][k] == 1) {
for
(j=1; j<=nv; j++) {
if
(T[i][j] == 0)
T[i][j]
= T[k][j];
}
}
}
}
SALTO;
listar_g (T,nv);getch();
SALTO;
}
}
int lea_grafo (int grafo[][MAXIMO])
{
int
v,ad,i,j,n;
int lea();
PR("De numero de
vertices...");
SALTO;
n =
lea();
for
(i=1; i <= n; i++)
for
(j=1; j <=n; j++)
grafo[i][j]
= 0;
PR ("Lea el primer
vertice. 99 para terminar...");
SALTO;
v = lea();
while (v != 99) {
PR ("Lea el primer
adjunto al vertice ");
printf ("%d
",v);
PR(". 99 para
terminar");
SALTO;
ad
= lea();
while
(ad != 99) {
grafo [v][ad] = 1;
PR ("Lea
otro adjunto al vertice ");
printf
("%d ",v);
PR(". 99
para terminar");
SALTO;
ad = lea();
}
PR ("Lea otro
vertice. 99 para terminar...");
SALTO;
v = lea();
}
return
(n);
}
int lea() {
char
L[10];
gets (L);
return (atoi (L));
}
void listar_g (int g[][MAXIMO], int nv) {
int
i,j;
for
(i=1; i <= nv; i++) {
for
(j = 1; j <= nv; j++)
printf
("%d ",g[i][j]);
SALTO;
}
}
void
copiar (int a[][MAXIMO], int b[][MAXIMO],int nv) {
int i,j;
for
(i=1; i<=nv; i++)
for
(j=1; j <= nv; j++)
a[i][j]
= b[i][j];
}
Algoritmo de Prim
Algoritmo de Dijkstra
"Este escrito fue elaborado por el estudiante Miguel Gonzalez de la universidad INCCA de Colombia de la facultad de ingeniería de sistemas".
Se le atribuye el nombre al científico de computación Holandés Edsger Dijkstra, también llamado al algoritmo de caminos mínimos. Consiste en encontrar el camino más corto entre dos vértices, cada uno de los vértices debe tener una etiquete y los arcos un peso. El grafo no debe estar dirigido ya que si lo esta no sería de este tipo.
Primero tomamos un punto de partida x, este puede ser cualquier vértices y tomamos uno como el punto de llegada, se toman los vértices adyacentes al origen y se evalúa el de menor peso, es decir, el que tenga la etiqueta con el número menor, se toma ese camino y se hace el mismo proceso hasta llegar al vértice que se tomó como final.
Ejemplo
Calcular la longitud entre a y g.
Vértice
|
1
|
2
|
3
|
5
|
6
|
a
|
[0
, x]
|
||||
b
|
[8
– a]
|
[6
– d]
|
[10
– e]
|
||
c
|
[5
– a]
|
||||
d
|
[3
– c]
|
||||
e
|
[2
– d]
|
||||
f
|
[7
– c]
|
[5
– d]
|
|||
g
|
[1
- e]
|
En
el anterior cuadro se puede ver como se aplica el algoritmo de Dijkstra, se
inicia en el primer vértice donde se pone el peso acumulado y el vértice de
donde procede al ser el primero no tienen peso acumulado ni un vértice de
procedencia, en la segunda casilla se toman los vértices adyacente al primero y
se compara, el recuadro azul da la etiqueta definitiva que dice que este es el
camino más corto entre los dos vértices comparados, se realiza hasta el final y
obtenemos el camino más corto.
Aqui un vídeo para que puedas comprender mejor el algoritmo de dijkstra
Aqui un vídeo para que puedas comprender mejor el algoritmo de dijkstra
Código para el algoritmo de Dijkstra
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#define MAXIMO 20
#define PR(x) printf
("%s",x)
#define SALTO printf
("\n")
int main() {
int
M[MAXIMO][MAXIMO],T[MAXIMO][MAXIMO];
int
suma, marcas[MAXIMO],padres[MAXIMO],minimo [MAXIMO];
int nv,i;
void
DIJKSTRA (int M[][MAXIMO],int N,int minimo[],int padres[],int marcas[]);
void
listar_r (int a[],int nv);
int
lea_grafo (int grafo[][MAXIMO]);
void
listar_g (int g[][MAXIMO], int nv);
nv =
lea_grafo (M);
listar_g
(M ,nv);
SALTO;
getch();
DIJKSTRA
(M,nv,minimo,padres,marcas);
listar_r
(minimo,nv);
SALTO;
listar_r
(padres,nv);
SALTO;
listar_r
(marcas,nv);
SALTO;
getch();
}
void DIJKSTRA (int
M[][MAXIMO],int N,int minimo[],
int
padres[],int marcas[])
{
int
min;
int
j,k,escogido;
for (j=1;
j<=N; j++ ) {
minimo[j]
= M[1][j];
marcas
[j] = 0;
padres
[j] = 1;
}
minimo
[1] = 0;
padres
[1]= 0;
marcas
[1] = 1;
for (k =
2; k <= N; k++) {
min
= 32000; /* No puede ser 32767 para maquinas de 16 bits
para
cada entero. ?Porque?.
Tambien en la lectura
debe ser 32000 */
for (j=1; j <= N; j++)
if
(marcas [j] == 0 && minimo [j] < min) {
min =
minimo [j];
escogido
= j;
}
marcas
[escogido] = 1;
for
(j=1; j <= N; j++)
if
(marcas [j] == 0 &&
(min
+ M[escogido][j] < minimo[j]) ) {
minimo
[j] = min + M[escogido][j];
padres
[j] = escogido;
}
}
}
int lea_grafo (int grafo[][MAXIMO])
{
int
lea(),v,ad,i,j,n,costo;
PR("De
numero de vertices...");
SALTO;
n
= lea();
for
(i=1; i <= n; i++)
for (j=1; j <=n; j++)
grafo[i][j]
= 32000;
PR
("Vertice ... ");
v = 1;
printf
("%d",v);
SALTO;
while (v
<= n) {
PR
("Lea el primer adjunto al vertice ");
printf
("%d ",v);
PR(".
99 para terminar");
SALTO;
ad
= lea();
while
(ad != 99) {
PR("Lea
costo del arco");SALTO;
costo
= lea();
grafo
[v][ad] = costo;
PR
("Lea otro adjunto al vertice ");
printf
("%d ",v);
PR(".
99 para terminar");
SALTO;
ad
= lea();
}
PR
("Vertice ...");
v++;
printf
("%d ",v);
SALTO;
}
return
(n);
}
int lea() {
char
L[10];
gets
(L);
return
(atoi (L));
}
void listar_g (int g[][MAXIMO],
int nv) {
int
i,j;
for
(i=1; i <= nv; i++) {
for
(j = 1; j <= nv; j++)
if
(g[i][j] == 32000)
printf
("%s"," * ");
else
printf ("%2d ",g[i][j]);
SALTO;
}
}
void listar_r (int a[],int nv) {
int
k;
for
(k=1; k<=nv; k++)
printf
("%d ",a[k]);
}
Algoritmo de Prim
El
algoritmo de Prim consiste en recorrer todos los vértices de un grafo en el
menor peso posible, esto genera un árbol recubridor de menor peso, para que
esto se cumpla el grafo debe ser conexo, estar etiquetado y sus arcos deben de
tener un peso. Es decir
Si
observamos el arco que hay entre el vértice 0 y 2 tiene un numero en rojo, eso
es lo que llamamos “peso” luego también es un grafo conexo y esta etiquetado.
En
el algoritmo de Prim podemos comenzar por cualquier vértice luego para
recorrerlo hay que tener los vértices adyacentes al que hemos escogido como
punto de partida es decir, si empezamos con el vértice “0” este tiene dos
vértices adyacentes que son el “2” y el “3”.
Entonces
para saber a cuál de los dos escoger, entre el vértice “2” o “3” miramos el
peso que tiene cada arco. Así el peso del vértice “0” al vértice “2” es de 5, y del vértice “0” al vértice
“3” es de 8 entonces
simplemente escogemos el de menor peso que es del vértice “0” al vértice “2” y
ya tenemos trazado un arco. Así tenemos que hacer el mismo proceso para los
demás vértices hasta completar todo el grafo, hay que tener en cuenta que al
hacer el árbol recubridor, este no puede quedar cerrado por que quedaría como
un ciclo y no queremos eso. Aquí tendremos un ejemplo…
Y en este vídeo dan una explicación del algoritmo de Prim
El
código para el algoritmo de Prim seria:
#include
"stdio.h"
#include
"conio.h"
#include
"stdlib.h"
#define MAXIMO 20
#define PR(x) printf
("%s",x)
#define SALTO printf
("\n")
int main() {
int M[MAXIMO][MAXIMO],T[MAXIMO][MAXIMO];
int suma, marcas[MAXIMO],padres[MAXIMO],minimo [MAXIMO];
int nv,i;
int PRIM (int M[][MAXIMO],
int N,int minimo[],int
padres[],int marcas[]);
int lea_grafo (int grafo[][MAXIMO]);
void listar_g (int g[][MAXIMO], int nv);
void listar_r (int a[],int nv);
nv = lea_grafo (M);
listar_g (M ,nv);
SALTO;
getch();
suma = PRIM (M,nv,minimo,padres,marcas);
printf ("\n suma=%d\n",suma);
SALTO;
listar_r (minimo,nv);
SALTO;
SALTO;
listar_r (padres,nv);
SALTO;
listar_r (marcas,nv);
SALTO;
getch();
}
int PRIM (int
M[][MAXIMO],int N,int minimo[],int padres[],int marcas[])
{
int min;
int j,k,escogido,suma;
for (j=1; j<=N; j++ ) {
minimo[j] = M[1][j];
marcas [j] = 0;
padres [j] = 1;
}
minimo [1] = 0;
padres [1]= 0;
marcas [1] = 1;
suma = 0;
for (k = 2; k <= N; k++) {
min = 32767;
for (j=1; j <= N; j++)
if (marcas [j] == 0 &&
minimo [j] < min) {
min = minimo [j];
escogido = j;
}
marcas [escogido] = 1;
suma = suma + min;
for (j=1; j <= N; j++)
if (marcas [j] == 0 &&
M[escogido][j] <
minimo[j] ) {
minimo [j] =
M[escogido][j];
padres [j] = escogido;
}
}
return (suma);
}
int lea_grafo (int
grafo[][MAXIMO])
{
int v,ad,i,j,n,costo,lea();
PR("De numero de vertices...");
SALTO;
n = lea();
for (i=1; i <= n; i++)
for (j=1; j <=n; j++)
grafo[i][j] = 32767;
PR ("Vertice
... ");
v = 1;
printf ("%d",v);
SALTO;
while (v <= n) {
PR ("Lea el primer adjunto al vertice
");
printf ("%d ",v);
PR(". 99 para terminar");
SALTO;
ad = lea();
while (ad != 99) {
PR("Lea costo del
arco");SALTO;
costo = lea();
grafo [v][ad] = costo;
PR ("Lea otro adjunto al
vertice ");
printf ("%d ",v);
PR(". 99 para
terminar");
SALTO;
ad = lea();
}
PR ("Vertice ...");
v++;
printf ("%d ",v);
SALTO;
}
return (n);
}
int lea() {
char L[10];
gets (L);
return (atoi (L));
}
void listar_g (int
g[][MAXIMO], int nv) {
int i,j;
for (i=1; i <= nv; i++) {
for (j = 1; j <= nv; j++)
if (g[i][j] == 32767)
printf
("%s"," * ");
else printf ("%2d
",g[i][j]);
SALTO;
}
}
void listar_r (int a[],int
nv) {
int k;
for (k=1; k<=nv; k++)
printf ("%d ",a[k]);
}
Algoritmo de Floyd
"Este escrito fue elaborado por la estudiante luisa Aponte de la universidad INCCA de Colombia de la facultad de ingeniería de sistemas".
Es
un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos
dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de
vértices en una única ejecución. El algoritmo de Floyd es un ejemplo de
programación dinámica.
El
algoritmo de Floyd es más importante desde el punto de almacenamiento dado que
puede ser implementado una vez se halla actualizado la distancia de la matriz.
EJEMPLO:
Matriz de caminos
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
4
|
4
|
3
|
∞
|
B
|
3
|
-
|
5
|
∞
|
∞
|
C
|
∞
|
∞
|
-
|
3
|
2
|
D
|
∞
|
∞
|
2
|
-
|
∞
|
E
|
∞
|
2
|
∞
|
∞
|
-
|
Fila A y columna A
Matriz de Padres
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
A
|
A
|
A
|
|
B
|
B
|
-
|
B
|
||
C
|
-
|
C
|
C
|
||
D
|
D
|
-
|
|||
E
|
E
|
-
|
Lo siguiente es coger una columna con una fila
y sumarla, si la suma de la fila y la columna es menor que el número que
está en la posición evaluada se cambia
pero si es mayor no se cambia. Si hay un infinito en la posición evaluada también
se cambia por el número que haya dado la suma.
Teniendo en cuenta que no se puede sumar un
infinito con otro número u otro infinito.
En la matriz de padres se coloca la letra que
se está evaluando que es de donde proviene el número que se puso en la matriz
de caminos.
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
4
|
4
|
3
|
∞
|
B
|
3
|
-
|
5
|
6
|
∞
|
C
|
∞
|
∞
|
-
|
3
|
2
|
D
|
∞
|
∞
|
2
|
-
|
∞
|
E
|
∞
|
2
|
∞
|
∞
|
-
|
Fila B y columna B
Matriz de padres
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
A
|
A
|
A
|
|
B
|
B
|
-
|
B
|
A
|
|
C
|
-
|
C
|
C
|
||
D
|
D
|
-
|
|||
E
|
E
|
-
|
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
4
|
4
|
3
|
∞
|
B
|
3
|
-
|
5
|
6
|
∞
|
C
|
∞
|
∞
|
-
|
3
|
2
|
D
|
∞
|
∞
|
2
|
-
|
∞
|
E
|
5
|
2
|
7
|
8
|
-
|
Fila C y columna C
Matriz de padres
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
A
|
A
|
A
|
|
B
|
B
|
-
|
B
|
A
|
|
C
|
-
|
C
|
C
|
||
D
|
D
|
-
|
|||
E
|
B
|
E
|
B
|
B
|
-
|
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
4
|
4
|
3
|
6
|
B
|
3
|
-
|
5
|
6
|
7
|
C
|
∞
|
∞
|
-
|
3
|
2
|
D
|
∞
|
∞
|
2
|
-
|
4
|
E
|
5
|
2
|
7
|
8
|
-
|
Fila D y columna D
Matriz de padres
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
A
|
A
|
A
|
C
|
B
|
B
|
-
|
B
|
A
|
C
|
C
|
-
|
C
|
C
|
||
D
|
D
|
-
|
C
|
||
E
|
B
|
E
|
B
|
B
|
-
|
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
4
|
4
|
3
|
6
|
B
|
3
|
-
|
5
|
6
|
7
|
C
|
∞
|
∞
|
-
|
3
|
2
|
D
|
∞
|
∞
|
2
|
-
|
4
|
E
|
5
|
2
|
7
|
8
|
-
|
Fila E columna E
Matriz de padres
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
A
|
A
|
A
|
C
|
B
|
B
|
-
|
B
|
A
|
C
|
C
|
-
|
C
|
C
|
||
D
|
D
|
-
|
C
|
||
E
|
B
|
E
|
B
|
B
|
-
|
Este sería el resultado final
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
4
|
4
|
3
|
6
|
B
|
3
|
-
|
5
|
6
|
7
|
C
|
7
|
4
|
-
|
3
|
2
|
D
|
9
|
6
|
2
|
-
|
4
|
E
|
5
|
2
|
7
|
8
|
-
|
A
|
B
|
C
|
D
|
E
|
|
A
|
-
|
A
|
A
|
A
|
C
|
B
|
B
|
-
|
B
|
A
|
C
|
C
|
E
|
E
|
-
|
C
|
C
|
D
|
E
|
E
|
D
|
-
|
C
|
E
|
B
|
E
|
B
|
B
|
-
|
Para saber cuál es el camino que tiene menor
peso para llegar de la A a la E se mira en la última matriz de padres entonces
para llegar a la E tiene que pasar por la C que es la letra que esta subrayada
y si vemos es la que menor peso tiene para llegar a esta esto se ve en la
matriz de camino. Otro ejemplo es para llegar de la E a la C tiene que pasar
por la B que es la letra subrayada y también es el menor peso por el cual se
puede ir lo podemos observar en la matriz de caminos.
Un vídeo para el algoritmo de Floyd
Un vídeo para el algoritmo de Floyd
Código para el algoritmo de Floyd
#include
"stdio.h"
#include
"conio.h"
#include
"stdlib.h"
#define
MAXIMO 20
#define
PR(x) printf ("%s",x)
#define
SALTO printf ("\n")
int
main() {
int M[MAXIMO][MAXIMO];
int nv;
int lea_grafo (int
grafo[][MAXIMO]);
void listar_g (int g[][MAXIMO],
int nv);
void FLOYD (int M[][MAXIMO],int
N);
nv =
lea_grafo (M);
listar_g
(M ,nv);
SALTO;
getch();
FLOYD (M,nv);
SALTO;
listar_g
(M,nv);
getch();
}
void
FLOYD (int M[][MAXIMO],int N)
{
int
i,j,k;
void listar_g (int g[][MAXIMO],
int nv);
for
(k=1; k <= N; k++)
M [k][k] = 0;
for (k=1; k <= N; k++) {
for (i=1; i <=
N; i++) {
if
(i != k) {
if
(M [i][k] != 32000) {
for
(j=1; j <= N; j++) {
if
(M[i][k] + M[k][j]
<
M[i][j] )
M[i][j]
=
M[i][k]+
M[k][j];}}}}
SALTO;
listar_g (M,N);
getch();}}
int
lea_grafo (int grafo[][MAXIMO])
{
int
lea(),v,ad,i,j,n,costo;
PR("De numero de
vertices...");
SALTO;
n = lea();
for (i=1; i <= n; i++)
for (j=1; j
<=n; j++)
grafo[i][j]
= 32000;
PR
("Vertice ... ");
v
= 1;
printf
("%d",v);
SALTO;
while
(v <= n) {
PR
("Lea el primer adjunto al vertice ");
printf
("%d ",v);
PR(".
99 para terminar");
SALTO;
ad = lea();
while (ad != 99)
{
PR("Lea costo del arco");SALTO;
costo
= lea();
grafo
[v][ad] = costo;
PR
("Lea otro adjunto al vertice ");
printf
("%d ",v);
PR(".
99 para terminar");
SALTO;
ad
= lea();
}PR
("Vertice ...");
v++;
printf ("%d
",v);
SALTO;
}return (n);
}int
lea() {
char
L[10];
gets
(L);
return (atoi (L));}
void
listar_g (int g[][MAXIMO], int nv) {
int i,j;
for
(i=1; i <= nv; i++) {
for (j = 1; j
<= nv; j++)
if
(g[i][j] == 32000)
printf
("%s"," * ");
else
printf ("%2d ",g[i][j]);
SALTO;}}
Algoritmo de kruskal
"Este escrito fue elaborado por el estudiante Santiago Rodriguez de la universidad INCCA de Colombia de la facultad de ingeniería de sistemas".
El
algoritmo de kruskal es un algoritmo de recubrimiento mínimo conexo ponderado,
o sea que va unir todos los nodos formando un árbol, tomando las aristas
que tengan un peso que siempre sea menor.Este
árbol de un grafo es un sub-grafo que contiene todos sus vértices o
nodos. Un grafo puede tener múltiples árboles.
CARACTERÍSTICAS
· Algoritmo basado en las aristas
· Agregar las aristas , uno a la vez, en orden de peso creciente
· El objetivo del algoritmo de Kruskal es construir un árbol (sub-grafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
· Resuelve la misma clase de problemas que el de Prim, a diferencia que no se escoge un nodo al azar.
· Trabaja con grafos ponderados, y no dirigidos.EJEMPLO
CARACTERÍSTICAS
· Algoritmo basado en las aristas
· Agregar las aristas , uno a la vez, en orden de peso creciente
· El objetivo del algoritmo de Kruskal es construir un árbol (sub-grafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
· Resuelve la misma clase de problemas que el de Prim, a diferencia que no se escoge un nodo al azar.
· Trabaja con grafos ponderados, y no dirigidos.EJEMPLO
Un video para que puedas entender mejor el algoritmo de kruskal
Código para el algoritmo de kruskal
#include
<iostream>
#include
<string>
#include
<vector>
#include
<algorithm>
#include
<list>
#include<stdio.h>
#define
REP(i,a) for(i=0;i<a;i++)
#define
FOR(i,a,b) for(i=a;i<b;i++)
#define
ii pair<int,int>
using
namespace std;
vector<int>
pset;
vector<pair<int,ii>
>grafo;
void
initSet(int size)
{
int i;
pset.resize(size);
REP(i,size+1)
pset[i]=i;
}
int findSet(int
i)
{
return (pset[i]==i)?
i:(pset[i]=findSet(pset[i]));
}
void
unionSet(int i,int j)
{
pset[findSet(i)]=findSet(j);
}
bool
isSameSet(int i,int j)
{
if(findSet(i) == findSet(j))
return true;
return false;
}
void kruskal(int N)
{int
sum=0,i;
initSet(N);
sort(grafo.begin(),grafo.end());
for(i=0;i<grafo.size();i++)
{ pair<int,ii>aux=grafo[i];
if(!isSameSet(aux.second.first,aux.second.second))
{
cout<<"pasa en:
"<<aux.second.first<<","<<aux.second.second<<endl;
sum=aux.first+sum;
unionSet(aux.second.first,aux.second.second);
}
}
cout<<"el
peso"<<sum;
}
int
main(){
int
V,A,i,a,b,w;
cout<<"\t\tAlgoritmo
de kruskal"<<endl;
cout<<"ingrese numero de
aristas"<<endl;
cin>>A;
cout<<"ingrese numero de
vertices"<<endl;
cin>>V;
cout<<"ingrese
desde que vertice a que vertice: "<<endl;
for(i=0;i<A;i++){
cout<<"Del
vertice: "; cin>>a; cout<<"al vertice:
";cin>>b;
cout<<"su peso: "; cin>>w;
}
kruskal(V);
system
("PAUSE");
return
0;
}
Aquí finaliza las explicaciones sobre estructuras de datos espero que les haya servido de mucho para lo que necesitaran.
No hay comentarios:
Publicar un comentario