Estructura de Datos : Algoritmos

Algoritmo de PRIM

De forma básica, es de la siguiente forma:

Funcion Prim()

aristas_marcadas = NULL

nodos_arbol = NULL

Mientras_Que(nodos_arbol != nodos_grafo)

aristas_marcadas = Minimo(nodos_arbol,

(nodos_grafo – nodos_arbol))

nodos_arbol = Falta(arista_marcadas, nodos_grafo)

Fin_Mientras_Que

Fin_Funcion

Algoritmo de DIJKSTRA

//matriz de pesos 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? */

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 FLOYD- WARSHALL

#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 LISTA ADYACENTE

#include "stdio.h"

#include "conio.h"

#include "stdlib.h"

#define MAXIMO 20

#define PR(x) printf ("%s",x)

#define SALTO printf ("\n")

#define localizar (nodo *)malloc (sizeof (nodo))

typedef struct nodo nodo;

struct nodo {

int v;

nodo *sig;

};

int main() {

nodo grafo[MAXIMO];

int nv;

int lea_grafo (nodo grafo[]);

void listar_g (nodo g[], int nv);

nv = lea_grafo (grafo);

listar_g (grafo,nv);

getch();

}

int lea_grafo (nodo grafo[])

{

int v,ad,i,n;

void ins_lista (nodo g[],int v, int ad);

int lea();

PR("De numero de vertices...");

SALTO;

n = lea();

for (i=1; i <= n; i++) {

grafo[i].v = 0;

grafo[i].sig = NULL;

}

PR ("Lea el primer vertice. 99 para terminar...");

SALTO;

v = lea();

grafo[v].v = v;

while (v != 99) {

PR ("Lea el primer adjunto al vertice ");

printf ("%d ",v);

PR(". 99 para terminar");

SALTO;

ad = lea();

while (ad != 99) {

ins_lista (grafo,v,ad);

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();

if (v != 99) {

// No olvide que MAXIMO es 20

grafo[v].v = v;

}

return (n);

}

int lea() {

char L[10];

gets (L);

return (atoi (L));

}

void ins_lista (nodo g[],int v, int ad) {

nodo *p,*q,*nuevo;

nuevo = localizar;

nuevo->v = ad;

nuevo->sig = NULL;

q = NULL;

p = g[v].sig;

while (p != NULL) {

q = p;

p = p->sig;

}

if (q == NULL)

g[v].sig = nuevo;

else q->sig = nuevo;

}

void listar_g (nodo g[], int nv) {

int i;

nodo *p;

for (i=1; i <= nv; i++) {

printf ("%d --> ",g[i].v);

p = g[i].sig;

while (p != NULL) {

printf ("%d ",p->v);

p = p->sig;

}

SALTO;

}

Algoritmo de MATRIZ DE CAMINOS

#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],a[MAXIMO][MAXIMO],R[MAXIMO][MAXIMO];

void copiar (int a[][MAXIMO], int b[][MAXIMO],int nv);

int nv,n,i,lea();

void listar_g (int g[][MAXIMO], int nv);

int lea_grafo (int grafo[][MAXIMO]);

void producto (int a[][MAXIMO],int b[][MAXIMO],int c[][MAXIMO],int m);

nv = lea_grafo (M);

listar_g (M ,nv);

getch();

PR("De longitud del camino a calcular");

SALTO;

n = lea();

copiar (a,M,nv);

for (i=1; i<n; i++) {

producto (a,M,R,nv);

listar_g (R,nv);

SALTO;

getch();

copiar (a,R,nv);

}

listar_g (R,nv);

getch();

}

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 producto (int a[][MAXIMO],int b[][MAXIMO],int c[][MAXIMO],int m) {

for (int i=1; i<=m; i++)

for (int k=1; k<=m; k++) {

c[i][k] = 0;

for (int j=1; j<=m; j++)

c[i][k] += a[i][j] * b[j][k];

}

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 MATRIZ COMPLETA

#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],a[MAXIMO][MAXIMO],R[MAXIMO][MAXIMO];

int S[MAXIMO][MAXIMO];

int nv,i;

void producto (int a[][MAXIMO],int b[][MAXIMO],int c[][MAXIMO],int m);

void listar_g (int g[][MAXIMO], int nv);

void sumar (int S[][MAXIMO],int R[][MAXIMO],int nv);

int lea_grafo (int grafo[][MAXIMO]);

void copiar (int a[][MAXIMO], int b[][MAXIMO],int nv);

nv = lea_grafo (M);

listar_g (M ,nv);

getch();

copiar (a,M,nv);

copiar (S,M,nv);

for (i=1; i<nv; i++) {

producto (a,M,R,nv);

sumar (S,R,nv);

listar_g (R,nv);

SALTO;getch();

copiar (a,R,nv);

}

listar_g (R,nv);

SALTO;

listar_g (S,nv);

getch();

}

void sumar (int S[][MAXIMO],int R[][MAXIMO],int nv) {

int i,j;

for (i=1;i<=nv;i++)

for (j=1; j<=nv;j++)

S[i][j] += R[i][j];

}

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 producto (int a[][MAXIMO],int b[][MAXIMO],int c[][MAXIMO],int m) {

for (i=1; i<=m; i++)

for (k=1; k<=m; k++) {

c[i][k] = 0;

for (j=1; j<=m; j++)

c[i][k] += a[i][j] * b[j][k];

}

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];

}

Estructura de Datos

Algoritmos

Algoritmo MATRIZ COMPLETA

No hay comentarios:

Publicar un comentario