CODIGOS

LISTA DE ADYACENCIA

#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; } }

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

MATRIZ DE CAMINOS

#include "stdio.h" #include "conio.h" //#include "alloc.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) { int i,j,k;

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

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

ALGORITMO DE WARSHALL

//ARSHAL

#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")

int 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 DIJKSTRA

#include "stdio.h"

#include "conio.h"

#include "stdlib.h"

//#include "alloc.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

#include "stdio.h"

#include "conio.h"

#include "stdlib.h"

//#include "alloc.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;

}

}