Estructura de datos del lenguaje C (preguntas de examen, pruebe su capacidad): escritura de código fuente
P88 El algoritmo de suma de listas entrelazadas de matriz dispersa es el siguiente:
/*Supongamos que ha es el puntero principal de una lista entrelazada de matriz dispersa, hb es el puntero principal de B lista de enlaces cruzados de matriz dispersa*/
#include
#define maxsize 100
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext
{ int v;
struct linknode *next ;} k;
};
struct linknode creatlindmat() /*Crear una lista con enlaces cruzados*/
{ int x, m, n, t , s, i, j, k;
struct linknode *p, *q, *cp[maxsize],*hm;
printf("Ingrese el número de filas, columnas y elementos distintos de cero de la matriz dispersa\ n");
scanf("%d%d%d",&m,&n,&t);
if (m >n) s=m; else s=n ;
hm=(struct linknode*)malloc(sizeof(struct linknode)) ;
hm->i=m; ->j=n;
cp[0]=hm;
for (i=1; i<=s;i++)
{ p= (struct linknode*)malloc(sizeof(struct linknode )) ;
p->i=0; p->j=0;
p->rptr=p; ->cptr=p;
cp[i]=p;
cp[i-1]->k.next=p;
}
cp[s]- >k.next=hm;
for( x=1;x<=t;x++)
{ printf("Por favor ingrese un triple (i,j,v )\n");
scanf("%d%d%d",&i,&j,&k);
p=( struct linknode*)malloc(sizeof(struct linknode));
p->i=i; p->j=j; Lo siguiente es insertar p en la i-ésima fila en la lista vinculada*/
q=cp[i];
mientras ((q->rptr!=cp[ i]) &&( q->rptr->j q=q->rptr; p->rptr=q->rptr; q->rptr=p; /*Lo siguiente es insertar P en la j-ésima columna de la lista vinculada*/ q=cp[j ]; mientras((q->cptr!=cp [j]) &&( q->cptr->i q=q->cptr; p->cptr=q->cptr; q->cptr=p; } p>return hm; } /* Suma las dos matrices dispersas representadas por ha y hb, y coloca el resultado agregado en ha*/ struct linknode *matadd(struct linknode *ha, struct linknode *hb) { struct linknode *pa, *pb, *qa, *ca,*cb,*p,*q; struct linknode *hl[maxsize]; int i , j, n; if((ha->i!=hb->i)||( ha- >j!=hb->j)) printf("Las matrices no coinciden y no se pueden sumar\n"); else { p=ha->k.next; n=ha->j; for (i=1;i<=n; i++) { hl[i]=p ; p=p->k.next; } ca=ha->k.next; mientras(ca->i==0) {pa=ca->rptr; pb=cb->rptr; qa=ca; mientras(pb->j!=0) { si((pa->j { qa=pa; pa=pa->rptr;} si no ((pa->j>pb->j)||(pa->j==0 )) /*Insertar un nodo*/ { p=(struct linknode*)malloc(sizeof(struct linknode)); p->i=pb->i ; p->j=pb->j; p->k.v=pb->k.v; qa->rptr=p; p->rptr=pa;< / p> qa=p; pb=pb->rptr; j=p->j; q=hl[j]->cptr; mientras( ( q->i { hl[j]=q; q=hl[j]->cptr;} hl[j]->cptr=p; p->cptr=q; hl[j]=p; } else {pa->k.v=pa->k.v+pb->k.v; if(pa->k.v==0) /*Eliminar un nodo */ { qa->rptr=pa->rptr; j=pa->j; q=hl[j]->cptr; mientras (q->i {hl[j]=q; q=hl[j]->cptr;} hl[j] -> cptr=q->cptr; pa=pa->rptr; pb=pb->rptr; libre(q); } else { qa=pa; pa=pa->rptr; pb=pb->rptr; } } } ca=ca->k.next; cb=cb->k.next; } } return ha; } void print(struct linknode *ha) /*Salida de lista de enlaces cruzados*/ { struct linknode *p,*q; p=ha->k.next; mientras(p->k.next!=ha) { q=p->rptr; while(q->rptr!=p) { printf("%3d%3d%3d\t" , q->i,q->j,q->k.v); q=q->rptr; } if(p! = q) printf("%3d%3d%3d",q->i,q->j,q->k.v); printf("\n" ) ; p=p->k.next; } q=p->rptr; mientras(q - >rptr!=p) { printf("%3d%3d%3d\t",q->i,q->j,q->k.v); q=q->rptr; } if(p!=q) printf("%3d%3d%3d",q- > i,q->j,q->k.v); printf("\n"); } void main() { struct linknode *ha=NULL,*hb=NULL,*hc=NULL; ha=creatlindmat( ); ha* / hb=creatlindmat( ); /*Generar otra lista con enlaces cruzados hb*/ printf("A:\n"); */ print(ha);printf("\n"); printf("B:\n"); /*Salida de lista de enlaces cruzados hb*/ print(hb);printf("\n"); hc=matadd(ha,hb);*Adición de lista con enlaces cruzados*/ printf ("A+ B:\n"); /*Emitir el resultado de la suma*/ print(hc);printf("\n"); > La descripción del tipo de datos P94 es la siguiente: #define elemtype char struct node1 { int atom; estructura nodo1 *enlace ; unión { estructura nodo1 *slink; ele mtype data; } ds; } El tipo de datos P95 se describe a continuación: struct node2 { elemtype data; struct node2 *link1,*link2; } P96 Encuentre la profundidad (LS) de la tabla generalizada int profundidad(estructura nodo1 *LS) { int max=0,dep; mientras(LS!=NULL) { if(LS->atom==0) //Hay una subtabla { dep=profundidad(LS->ds.slink); if(dep>max ) max=dep; } LS=LS->enlace; } return max +1; } P96 Creación de tabla generalizada creat(LS) void creat(struct node1 *LS) { char ch; scanf("%c",&ch); if(ch=='#') LS=NULL; else if(ch=='(') {LS=(struct node*)malloc(sizeof(struct node)); LS->atom =0; creat(LS->ds.slink); } else { LS=(struct node* )malloc(sizeof(struct node)); LS->atom=1; LS->ds.data=ch; } scanf("%c",&ch); if(LS==NULL); else if(ch==' ,') creat(LS->link); else if((ch==')')||(ch==';')) LS- >link=NULL; } P97 Impresión de tabla generalizada de salida (LS) impresión vacía (estructura nodo1 *LS) { if(LS->atom==0) { printf("("); if(LS ->ds.slink==NULL) printf("#"); els e print(LS->ds.slink); } else printf("%c ",LS- >ds.data); if(LS->atom==0) printf(")"); if(LS->enlace !=NULL) { printf(";"); print(LS->enlace); } } P98 La complejidad temporal de este algoritmo es O(n). El programa completo completo es el siguiente: #include #define elemtype char struct node1 { int átomo; estructura nodo1 *enlace; unión { estructura nodo1 *slink; elemtype data; } ds; }; void creat(struct node1 LS) /*Crear una lista enlazada individualmente de una tabla generalizada*/ { char ch; scanf("%c",&ch); if(ch=='#') LS=NULL; else if(ch=='(') {LS=(struct node1*)malloc(sizeof(struct node1) ); LS->atom=0; creat(LS->ds.slink); } else { LS=(struct node1*)malloc(sizeof(struct node1)); LS->atom=1; LS->ds.data =ch; } scanf("%c",&ch); if(LS==NULL); else if(ch== ',') creat(LS->link); else if((ch==')')||(ch==' ;')) LS->link=NULL; } void print(struct node1 LS) /*Salida de lista enlazada individualmente generalizada*/ { if(LS->atom==0) { printf("("); if(LS- >ds.slink==NULL) printf("#"); else print(LS->ds .slink); } else printf("%c",LS->ds.data); si (LS->atom== 0) printf(")"); if(LS->link!=NULL) { printf( ";"); print(LS->link); } } int Depth(struct node1 LS) /*Encontrar la profundidad de la tabla generalizada*/ { int max=0; mientras(LS!=NULL) { if(LS->atom==0 ) { int dep=profundidad(LS->ds.slink); if(dep>max) max=dep; } LS=LS->enlace; } return max+1; } principal() { int dep; struct node1 *p=NULL; creat(p); /*Crear una lista enlazada individualmente de tabla generalizada*/ print(p); /*Generar una lista enlazada individualmente generalizada*/ dep=profundidad(p); /*Encontrar la profundidad de la lista generalizada*/ printf("%d\ n",dep); } Capítulo 6 Árbol P109 Se define el tipo de nodo de una lista enlazada binaria de la siguiente manera: typedef struct btnode { anytype data; struct btnode *Lch,*Rch; }tnodetype; P109 Lista enlazada de tres vías El tipo de nodo se define de la siguiente manera: typedef struct btnode3 { anytype data; struct btnode *Lch,*Rch,*Parent; }tnodetype3; P112 Algoritmo transversal de pedido anticipado en lenguaje C: pedido anticipado vacío (tnodetype *t) /*Algoritmo de árbol binario transversal de pedido previo, t es el puntero al nodo raíz*/ { if (t!=NULL) {printf("% d ",t->datos); preorden(t->lch); preorden(t->rch); } } P113 Algoritmo de recorrido en orden en lenguaje C: void inorder(tnodetype *t) /*Binario de recorrido en orden algoritmo de árbol, t es el puntero al nodo raíz*/ { if(t!=NULL) {inorder(t->lch) ; printf("%d ",t ->datos); inorder(t->rch); } } P113 Algoritmo de recorrido posterior al orden en lenguaje C: void postorder(tnodetype *t) /*Algoritmo de árbol binario transversal del postorden, t es el puntero al nodo raíz*/ { if(t!=NULL) { postorder(t->lch); publicación orden(t->rch); printf("%d ",t->datos); } } P114 Si las colas se introducen como herramientas de almacenamiento auxiliares, el algoritmo para atravesar el árbol binario por nivel se puede describir de la siguiente manera: voidlevelorder(tnodetype *t) /*The algoritmo para atravesar el árbol binario por nivel, t Es el puntero al nodo raíz*/ {tnodetype q[20] /*cola auxiliar*/ front=0; rear=0 ; /*Vaciar la cola*/ if (t!=NULL) { rear++; q [rear]=t; /*Nudo raíz Haga clic para unirse a la cola*/ } while (front!=rear) { front++; t=q [frente] ; printf ("%c\n",t->datos); if (t->lch!= NULL) /*El hijo izquierdo de t no está vacío, entonces Enqueue*/ { rear++; q [rear]=t->lch; } if (t- >rch!=NULL) /*Si el hijo derecho de t no está vacío, únete a la cola*/ { rear++; q [rear]=t->rch; } } } P115 Usar en orden recorrido para contar el número de nodos y nodos hoja en un árbol binario. El algoritmo se describe como: void inordercount (tnodetype *t) /*Recorre el árbol binario en orden. , cuente el número de nodos y nodos hoja en el árbol*/ { if (t!=NULL) { inordercount (t->lch); recorrido del subárbol izquierdo*/ printf ("%c\n",t-> data /*Acceder al nodo raíz*/ countnode++ /*Recuento de nodos*; / if ((t->lch==NULL)&&(t-> rch==NULL)) countleaf++ /*Recuento de nodos de hoja*/ inordercount (t->rch); /*Recorrido en orden del subárbol derecho*/ } } P115 La profundidad de un árbol binario se puede calcular de la siguiente manera: void preorderdeep (tnodetype *t,int j) /*Recorre el árbol binario en orden y calcula la profundidad del árbol binario* / { if (t!=NULL) { printf ("%c\ n",t->data /*Acceder al nodo raíz*/ j++; if (k preorderdeep (t-> lch,j); /*El pedido anticipado atraviesa el subárbol izquierdo*/ preorderdeep (t->rch,j); /*El pedido anticipado atraviesa el subárbol derecho*/ } } P117 El tipo de nodo del árbol binario de pistas se define de la siguiente manera: struct nodexs {anytype data; struct nodexs *lch, *rch; int ltag,rtag; /*Campos de bandera izquierdo y derecho*/ } P117 En -order algoritmo de pista de orden void inorderxs (struct nodexs *t) /*Atraviesa en orden el árbol binario señalado por t y crea pistas para los nodos*/ { if (t!=NULL) { inorderxs (t->lch); printf ("%c\n",t->data) ; if (t->lch!=NULL) t->ltag=0; else { t->ltag=1; t->lch=pr; } /*Crea la pista izquierda del nodo señalado por t, para que apunte al nodo predecesor pr*/ if (pr!=NULL ) { if (pr->rch!=NULL) pr->rtag=0; else { pr->rtag=1; pr->rch=p; } } /*Crea la pista correcta del nodo señalado por pr, para que apunte al nodo sucesor p*/ pr=p; inorderxs (t->rch); } } P118 El algoritmo para recuperar el nodo predecesor de un nodo en el árbol de pistas de la raíz media se describe a continuación: struct nodexs * impre (struct nodexs *q) /*Recuperar en el árbol de pistas de la raíz media El nodo predecesor del nodo señalado por q*/ { if (q->ltag==1) p=q->lch; else { r=q->lch; while (r->rtag!=1) r=r->rch; p= r; } retorno (p); } P119 Recuperar el nodo sucesor de un nodo en el árbol de pistas raíz. El algoritmo de puntos se describe a continuación: struct nodexs * insucc (struct nodexs *q) /* Recupera el nodo sucesor del nodo señalado por q en el árbol de pistas de la raíz media*/ { if (q->rtag==1) p=q->rch ; else { r=q->rch; mientras (r->ltag!=1) r=r->l ch; p=r; } return (p); } Algoritmo P120 El programa se describe en lenguaje C de la siguiente manera: void sortBT(BT *t,BT *s) /*Inserte el nodo señalado por el puntero s en el árbol binario con t como puntero raíz*/ { if (t==NULL) t=s; /*Si t apunta a un árbol vacío, el nodo al que apunta s es la raíz*/ else if (s ->data < t->data) sortBT(t->lch,s); /*El nodo s se inserta en el subárbol izquierdo de t*/ else sortBT(t->rch,s); /*El nodo s se inserta en el subárbol derecho de t*/ } P121 Árbol de clasificación binaria eliminación de nodo La descripción del algoritmo en lenguaje C es la siguiente: void delnode(bt,f,p) /*bt es el puntero raíz de un árbol de clasificación binario, y p apunta al nodo eliminado, f apunta a sus padres*/ /*f es NULL cuando p=bt*/ { fag=0 /*When fag=0; , la información del puntero f debe modificarse. No se requiere modificación cuando fag=1*/ if (p->lch==NULL) s=p->rch. ; /*El nodo eliminado es una hoja u otro El subárbol izquierdo está vacío*/ else if (p->rch==NULL) s=p->lch; else { q= p; /*Ni el subárbol izquierdo ni el derecho del nodo eliminado están vacíos*/ s=p->lch; while (s->rch!=NULL) { q=s; s=s->rch; } /*Buscar el nodo s* / if (q=p) q->lch=s->lch; else q->rch=s->lch; p-> data=s->data; /*El nodo señalado por s reemplaza el nodo eliminado*/ DISPOSE(s); Maricón =1; } if (fag=0) /*Necesita modificar el puntero principal*/ { if (f=NULL) bt=s; / *El nodo eliminado es el nodo raíz*/ else if (f->lch=p) f->lch=s; else f->rch=s; DISPOSE(p); /*Liberar el nodo eliminado*/ } } Capítulo 7 Gráficos P134 Uso de la representación de matriz de adyacencia para representar gráficos, además de almacenar la matriz de adyacencia utilizada para representar la relación adyacente entre vértices, generalmente también es necesario usar un Una tabla de secuencia para almacenar información de vértices. Su descripción formal es la siguiente: # define n 6 /*El número de vértices del gráfico*/ # define e 8 /*El número de aristas (arcos) de el gráfico*/ typedef char vextype /*vertex data type*/ typedef float adjtype /*weight type*/ typedef struct { vextype vexs[n]; adjtype arcs[n][n]; }graph; P135 Algoritmo para construir un Red no dirigida. CREAGRAPH(ga) /*Crear una red no dirigida*/ Gráfica * ga; { int i,j, k; float w; for(i＝0;i ga ->vexs[i]＝getchar(); /*Leer la información de los vértices y crear una tabla de vértices*/ for(i＝0;i for(j＝0;j ga ->arcs[i][j]＝0; /*Inicialización de matriz de adyacencia*/ for(k＝0;k (scanf("%d%d%f",&I,&j,&w); /*Leer el peso w en el borde (vi, vj) */ ga ->arcos[i][j]＝w; ga - >arcos[j][i]＝w; } } /*CREAGRAPH*/ P136 Descripción formal de la lista de adyacencia y su algoritmo de establecimiento: typedef struct node {int adjvex /*adjacency Point; dominio*/ estructura nodo * siguiente; /*Dominio de cadena*/ }edgenode /*Nodo de tabla de borde*/ estructura typedef {vextype vertex; /*Información de vértice*/ enlace de borde de tabla; /*Puntero de encabezado de tabla de borde*/ }vexnode /*Nodo de tabla de vértice */ vexnode ga[n]; CREATADJLIST(ga) /*Crear una lista de adyacencia de un gráfico no dirigido*/ Vexnode ga[ ]; {int i,j,k; edgenode * s; for(i=o;i (ga[i].vertex=getchar(); ga[i].1ink=NULL; /*Inicialización del puntero del encabezado de borde*/ } for(k＝0;k {scanf("%d%d",&i,&j ); / *Leer el número del par de vértices del borde (vi, vj)*/ s=malloc(sizeof(edgenode) /*Generar un nodo de tabla con el número de punto adyacente j*s * / s-> adjvex=j; s- ->siguiente：＝ga[i].Link; ga[i].1ink＝ s; Inserte *s en el encabezado de la tabla perimetral del vértice vi*/ s=malloc(size0f(edgende)); /*Genere un nodo de tabla perimetral *s con el número de punto adyacente i / s ->adjvex=i; s ->next=ga[j].1ink; ga[j].1ink=s; s en el encabezado de la tabla de borde del vértice vj*/ } } /* CREATADJLIST */ P139 respectivamente La matriz de adyacencia y la lista de adyacencia se utilizan como estructura de almacenamiento del gráfico para dar un algoritmo específico. En el algoritmo, g, g1 y visitado son cantidades completas, y los valores iniciales de cada componente de visitado son FALDOS. int visited[n] /*Definir el vector booleano visitd como la cantidad total del proceso*/ Gráfico g /*El gráfico g es la cantidad total del proceso*/ DFS (i) /*Gráfico de búsqueda en profundidad g a partir de Vi+1, g está representado por una matriz de adyacencia*/ int i; { int j; printf("node：%c＼n" , g.vexs[i]); /*Visita punto de partida vi+1 */ Visitado[i]＝ TRUE; /*Marcar vi+l ha sido visitado*/ for (j＝0;j if((g.arcs[i ][j]＝＝1) &&(! visited[j])) DFS(j) /*Si el punto adyacente vj+l de Vi+l no ha sido visitado, luego comience desde vj+l Iniciar búsqueda en profundidad*/ } /*DFS*/ vexnode gl[n] /*Adyacencia completa list*/ DFSL(i ) /*Gráfico de búsqueda en profundidad g1 a partir de vi+l, g1 está representado por una lista de adyacencia*/ int i; { int j; edgenode * p; printf("nodo:%C\n" ,g1[i].vertex); visitated[i]＝TRUE; p＝g1[i].1ink; /*Obtiene el puntero del encabezado de la tabla de borde de vi+1*/ while(p ! ＝NULL) /*Buscar los puntos adyacentes de vi+l en secuencia*/ { if(! Vistited[p ->adjvex]) DFSL(p ->adjvex); /*unvisited from vi+1 Iniciar una búsqueda en profundidad desde el punto adyacente*/ p＝p ->next; vi+l*/ } } /* DFSL */ P142 utiliza la matriz de adyacencia y la lista de adyacencia como estructura de almacenamiento del gráfico y proporciona algoritmos de búsqueda en amplitud respectivamente. BFS(k) /*Gráfico de búsqueda de amplitud primero g a partir de vk+l, g está representado por una matriz de adyacencia, visitado es el vector de bandera de acceso*/ int k ; { int i,j; SETNULL(Q); /*Establecer cola vacía Q */ printf("%c＼n"， g.vexs[ k]); /*Visita el punto de inicio vk+l*x/ visitado[k]＝TRUE /*Marca vk+l ha sido visitado*/ ENQUEUE(Q, K); /*Los vértices visitados (números de serie) se colocan en la cola*/ While(!EMPTY(Q)) /*Se ejecuta cuando la cola no está vacía*/ {i =DEQUEUE(Q); /*El número de secuencia del elemento principal se retira de la cola*/ for(j＝0;j if((g.arcs[i ][j]＝＝1)&&(! visitó[j])) {printf("%c＝" , g.vexs[ j]); /*Visitado vi+l nunca ha visitado el punto adyacente vj+l */ visitado[j]＝TRUE; ENQUEUE(Q,j); Los vértices visitados están en cola*/ } } } /* BFS */ BFSL(k) /*Comenzar desde vk+l y busque primero el gráfico g1, g1 está representado por una lista de adyacencia */ int k { int i; edgenode * p; SETNULL(Q); printf("%c＝" , g1[k].vertex); visitó[k]＝TRUE; ENQUEUE(Q,k ); while(! EMPTY(Q)); { i＝DEQUEUE(Q); p＝g1[i].1ink /* Obtener el puntero del encabezado de la tabla de borde de vi+l*/ while(p !＝NULL) /*Buscar los puntos adyacentes de vi+l en secuencia */ { if( ! visited[ p - >adjvex]) /*Acceder a los puntos adyacentes no visitados de vi+l*/ { printf{"%c＼n" , g1[p - >adjvex].vertex}; p> visitó[p - >adjvex]＝TRUE; ENQUEUE(Q,p - >adjvex) ; /*Los vértices visitados están en cola*/ } p＝p - >next; /*Encontrar el siguiente punto adyacente de vi+l*/ } } } /*BFSL*/ P148 Antes de refinar el algoritmo Prim, primero determine la estructura de almacenamiento relevante de la siguiente manera: typdef struct {Int fromvex, endvex; /*El punto inicial y final del borde*/ longitud flotante /*El peso del borde*; / } edge; float dist[n ][n]; /*Matriz de adyacencia ponderada de la red conectada*/ e dgeT[n-1]; /*Árbol de expansión*/ P149 La declaración abstracta (1) se puede refinar a: for(j=1;j {T[j-1].fromvex=1} /*El punto inicial del borde morado es el punto rojo; */ T[j-1].endvex＝j+1; /*El punto final del borde morado es el punto azul*/ T[j-1] .1ength＝dist[0][j ]; /*Longitud del borde púrpura*/ } P149 El k-ésimo borde púrpura más corto requerido por la declaración abstracta (3) puede ser refinado a: min＝max; /*znax es mayor que el peso en cualquier borde*/ for (j＝k;j if(T[j].1ength {min=T[j].1ength;m =j; /*Registra la posición actual del borde morado más corto*/ } P149 Refinamiento de la declaración abstracta ( 4): e=T[ m];T[m]＝T[k];T[k]＝e, /* Intercambia T[k] y T[m]*/ v＝T[kl.Endvex]; /* v es el vértice recién pintado de rojo*/ P149 La declaración abstracta (5) se puede refinar como: for(j＝k+1;j {d＝ dist[v-1][T[j].endvex-1 ]; /*La longitud del nuevo borde morado*/ if(d {T[j].1ength=d; T[j].fromvex=v /*; El nuevo borde violeta reemplaza el borde violeta más corto original*/ } } P150 Algoritmo completo: PRIM() / *Construya el árbol de expansión mínimo de la red conectada dist comenzando desde el primer vértice y coloque el resultado en T*/ {int j , k , m , v , min , max＝l0000; float d; edge e; for(j=1;j {T[j-1].formvex=1; /*Vertex 1 es el primero en unir puntos rojos en el árbol*/ T[j-1].endvex＝j +1; T[j-1].length＝dist[o][j] ; } for(k＝0;k< n-1;k++) /*Encontrar el k-ésimo lado*/ {min＝max ; for(j＝k;j if(T[j].1ength {min＝T[j].1ength; m＝j; } /*T[m] es el borde morado más corto actual */ } e＝T [m];T[m]＝T[k];T[k]＝e; /*T[k] y T[ m] Después del intercambio, T[k] es el k-ésimo borde del árbol rojo*/ v＝T[k].endvex; /* v es el nuevo punto rojo*/ for(j＝k+1;j {d＝dist[v-1][ T [j].endvex-1]; if(d {T[j].1ength=d; T[j].fromvex=v; } } } /* PRIM */ P151 Kruskl algoritmo Descripción aproximada de: T=(V,φ); Mientras (número de aristas contenidas en T {De E Seleccione el borde más corto actual (u, v); Elimine el borde (u, v) de E; Si ((u, v) se fusiona con T, no se realizará ningún bucle. ser generado, fusionar el borde (u, v) en T; } P153 Implementación del algoritmo de Dijkstra. El algoritmo se describe de la siguiente manera: #define max 32767 /*max representa un número grande*/ void dijkstra (coste flotante[][n],int v) /*Encuentra el camino más corto desde el punto fuente v a otros vértices y su longitud*/ { v1=v-1; for (i=0; i< n;i++) { dist[i]=costo[v1][i] /*Inicializar dist*/ if (dist[i] pre[i]=v; else pre[i]=0; } pre[v1]=0; for (i=0;i s[i]=0; /*s la matriz se inicializa como vacía*/ s[v1 ]=1; /*Clasifica el punto fuente v en el conjunto s*/ for (i=0;i { min =max; for (j=0;j si (!s[j] && (dist[j] { min= dist[j]; k=j; } /*Seleccione el vértice k+1 con el valor de dist más pequeño*/ s[k]=1 ; /*Incluir el vértice k+1 en el conjunto s*/ for (j=0;j if ( !s[j]&&( dist[j]>dist[k]+coste[k][j])) { dist[j]=dist[k]+coste[k][j ]; /*Modificar el conjunto V-S El valor dist de cada vértice en */ pre[j]=k+1 /*k+1 vértice es el predecesor de j+1 vértice*/<; /p> } } /*Todos los vértices han sido agregados al conjunto S*/ for (j=0;j { printf("%f\n%d",dist[j],j+1;); p=pre[j]; mientras (p!=0 ) { printf("%d",p); p=pre[p-1]; } } } P155 El algoritmo de Freud se puede describir como: A(0)[i][j ]=cost[i][j ]; //el costo es la matriz de adyacencia del gráfico A(k)[i][j]=min{A(k-1) [i][ j],A(k-1) [ i][k]+A(k-1) [k][j]} Donde k=1,2,…,n P155 Implementación del algoritmo de Freud. El algoritmo se describe a continuación: int path[n][n]; /*path Matrix*/ void floyd (float A[][n],cost[] [n] ) { for (i=0;i for (j=0 ;j { if (coste[i][j] ruta[i][j]=j; else { ruta[i ][j]=0; A[i][j]=coste[i][j]; } } for (k=0;k /*Haga n iteraciones, cada vez intentando expandir el vértice k al camino más corto obtenido actualmente desde i a j */ para (i=0;i para (j=0;j si ( A[i][j]>(A[i][k]+A[k]