1 Profesor Leopoldo Silva Bijit20-01-2010 Captulo 10 Grafos. Los grafos enfatizan las relaciones complejas de conexin entre elementos de datos. Los rboles son un caso simple de grafos. Los grafos permiten estudiar problemas como: menor distancia o costo entre puntos; bsquedas atravsdeenlacesenlaweb;redeselctricas,cableadodeimpresos;itineracindetareas, siguiendotrayectorias;sintonizarorelacionarpostulantesconofertas,partesconproveedores; conectividadentreparesdesitiosenlared;especificacindeaplicacionesmostrandolas relaciones entre subsistemas; etc. 10.1. Definiciones. Quedan definidos por un conjunto de vrtices V, ms un conjunto de elementos E que conectan pares de vrtices distintos.El grafo se describe por: G(V, E). Figura 10.1. Elemento, vrtice, incidencia. Grado de incidencia, del vrtice, es el nmero de elementos que son incidentes en ese vrtice. En grafos simples se aceptan slo un enlace entre un par de vrtices diferentes. Es decir, no se aceptanlazos(elementosadyacentesenelmismovrtice),nielementosenparalelo(dos elementos que son adyacentes con un mismo par de vrtices. Trayectoria: Secuencia de elementos entre vrtices adyacentes. Trayectoria simple: los vrtices y los elementos estn presentes slo una vez. Circuito o ciclo: Trayectoria simple, salvo que el vrtice inicial y final son uno solo. Largo de la trayectoria es el nmero de elementos que la componen. Grafo conectado: Si existe trayectoria entre cualquier par de vrtices. rbol de un grafo: Subgrafo conectado sin circuitos. vrtice elemento Vrtices adyacentes Elemento incidente en vrtice 2Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 Densidad es el promedio de los grados de incidencia de los vrtices. Si sumamos los grados de incidenciasetendrelvalor2E(secuentadosvecescadaelemento).Entoncesladensidad resulta: 2E/V. Se dice que un grafo es denso si su densidad en proporcional a V.Esto implica que el nmero de elementos E ser proporcional a V2.En caso contrario es un grafo liviano (sparse). El concepto de densidad tiene relacin con el tipo de algoritmo y la estructura de datos que se emplearpararepresentarelgrafo.ComplejidadestpicassonV2 yE*logE,laprimeraesms adecuada a grafos densos; y la segunda a grafos livianos. Grafos dirigidos: Los elementos tienen asociada una direccin. Figura 10.2. Elementos orientados. Grafosponderados:Loselementos(w(E))olosvrticestienenasociadounadistanciao costo. rbol de cobertura (Spanning tree) de un grafo conectado, con pesos y no dirigido, es un rbol cuyo peso se calcula segn:T EE w T w ) ( ) ( De los innumerables problemas asociados a grafos se estudiarn dos. El mnimo rbol de cobertura, en grafos con peso pero no dirigidos. La ruta mnima: en grafos con peso y dirigidos. 10.2. Representaciones. Paragrafosdensosseprefierelamatrizdeadyacencias,paragrafoslivianossueleemplearse una lista de adyacencias. 10.2.1. Matriz de adyacencia de los elementos en los vrtices. Se emplea una matriz cuadrada (V-1, V-1) donde V es el nmero de vrtices. a Elemento= (a, b) b a Elemento= (b, a) b Grafos3 Profesor Leopoldo Silva Bijit20-01-2010 m[0][0]m[0][3]m[1][0]m[1][3] a01..w..V-1 0 1 .. v1 .. V-1 Figura 10.3. Matriz de adyacencias. Se coloca un 1 en (v, w) si existe elemento de v hacia w; 0 en caso contrario. La matriz es simtrica si el grafo no es dirigido. Si no se aceptan lazos, la diagonal est formada por ceros. 10.2.2. Matrices estticas en C. Lanotacin:a[v][w]recuerdaquelamatrizasevisualizacomounarreglodevrenglones, donde cada rengln est formado por w columnas. Ejemplo: La matriz m se define segn: intm[2][4]; 0 2 x 4Figura 10.4. Matriz de 2 renglones por 4 columnas. Se almacenan por renglones. La siguiente figura ilustra el almacenamiento de los elementos del arreglo, con direcciones crecientes hacia abajo: Figura 10.5. Forma de almacenamiento de matrices. ndice ms derechista vara ms rpido, si se accesa segn el orden de almacenamiento. Se inicializan mediante listas: intm[2][4]={{0,1,2,3},{4,5,6,7}}; 4Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 Matrices como argumentos. Si se pasa una matriz a una funcin, la declaracin del argumento debe incluirla dimensin de la columna. La dimensin del rengln es irrelevante, ya que se pasa un puntero. f(int m[ ] [4]) f(int (*m)[4]) 10.2.3. Matrices dinmicas en C. Ver Sedgewick, cap. 17. Las siguientes declaraciones describen un grafo a travs de una matriz de adyacencias. Declaracin de estructuras de datos para un grafo. struct graph {int V;//Nmero de vrtices int E;//Nmero de elementos int **adj;// Matriz de adyacencias }; typedef struct graph *Graph; Definicin de variables. Las siguientes definiciones crean el espacio. Se define un grafo G, cuya matriz de adyacencias sedefinesegnunarregloderpunterosparaalmacenarlasdireccionesdelosarreglosdec elementos: Graph G = malloc(sizeof *G);//crea la cabecera del grafo. int **t= malloc(r * sizeof(int *));//crea arreglo de r renglones de punteros G->adj = t;//Pega el arreglo de punteros //crea y pega los renglones de c columnas: for (i = 0; i < r; i++)t[i] = malloc(c * sizeof(int)); El siguiente diagrama ilustra las variables. Se ha omitido la casilla asociada a t. Grafos5 Profesor Leopoldo Silva Bijit20-01-2010 Figura 10.6. Estructura para matriz de adyacencias. Tambinsepuededefinirunamatrizesttica(sinllamaramalloc()):comounarregloder punteros que apuntan a arreglos con la informacin de las columnas. 10.2.4. Funciones para grafos descritos por su matriz de adyacencias. La funcin creacin de un grafo vaco de V vrtices: 10.2.4.1. Creacin. Graph GRAPHinit(int V) { Graph G = malloc(sizeof *G);//crea cabecera del grafo G->V = V; G->E = 0;//Con V vrtices y 0 elementos G->adj = MATRIXint(V, V, 0);//Lo inicia con ceros. return G; } Donde MATRIXint crea la matriz de incidencias de r renglones, c columnas y la inicializa con val. //Asignacin dinmica de arreglo bidimensionalint **MATRIXint(int r, int c, int val) { int i, j; int **t = malloc(r * sizeof(int *));for (i = 0; i < r; i++) t[i] = malloc(c * sizeof(int));// t[i] equivale a *(t+i) for (i = 0; i < r; i++) for (j = 0; j < c; j++) t[i][j] = val;//equivale a **(t+i+j) = val; return t; j i t t[i] *(t+i) t[i][j] **(t+i+j) G V E adj 6Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 } De complejidad:O(r + r*c) La siguiente funcin, libera el espacio asociado al grafo, cuidando de borrar en orden inverso al solicitado, de tal modo de no perder las referencias. 10.2.4.2. Liberacin del espacio. void BorreGrafo(Graph G) { int i; int **t = G->adj; for (i = 0; i < G->V; i++) free(t[i]); //primero borra los renglones free(t);//luego el arreglo de punteros a los renglones free(G);//finalmente la cabecera } Si se tiene la definicin: Graph Grafo; Puede crearse la matriz de adyacencias del grafo mediante: #define VERTICES 5 Grafo = GRAPHinit(VERTICES); 10.2.4.3. Definicin de un elemento. Un elemento puede describirse por: typedef struct{ int v; //vrtice inicial. Desde. int w; //vrtice final. Hasta. } Edge; Con el siguiente constructor: Edge EDGE(int v, int w) { Edge t; t.v=v; t.w=w; return (t); } La siguiente definicin crea un elemento, y EDGE lo inicializa. Edge elemento; elemento = EDGE(1,2); 10.2.4.4. Insercin de elemento en un grafo. La siguiente funcin inserta un elemento e en un grafo G. Grafos7 Profesor Leopoldo Silva Bijit20-01-2010 void GRAPHinsertE(Graph G, Edge e) {if (G->adj[e.v][e.w] == 0) G->E++;//aumenta el nmero de elementos del grafo G->adj[e.v][e.w] = 1;G->adj[e.w][e.v] = 1; //si el grafo no es dirigido. } 10.2.4.5. Eliminacin de elemento. La funcin siguiente remueve el elemento e del grafo G: void GRAPHremoveE(Graph G, Edge e) {if (G->adj[e.v][e.w] == 1) G->E--; //Disminuye el contador de elementos. G->adj[e.v][e.w] = 0;G->adj[e.w][e.v] = 0; } La accin siguiente, inserta el elemento en el Grafo: GRAPHinsertE(Grafo, elemento); 10.2.4.6. Creacin de los elementos. La siguiente definicin crea el conjunto de elementos de un grafo, como un arreglo denominado Elementos.Esta es otra forma de definir un grafo. Requiere 2E datos para ser definida, en lugar de V2 que necesita la matriz de incidencia. #define ELEMENTOS 6 Edge Elementos[ELEMENTOS]={{1,2},{1,4},{2,3},{3,4},{4,0},{3,0} }; elementovw 012 114 223 334 440 530 Figura 10.7. Grafo descrito por sus elementos. Estadescripcinesnica,enelsentidoqueasocianombresdeelementosconnombresde vrtices. Entonces la creacin de la matriz de incidencia de un grafo de cinco vrtices, a partir del arreglo de elementos, definido por seis elementos, puede realizarse, segn: 8Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 for(i=0; iV, G->E);//nmero total de elementos y vrtices. for (i = 0; i < G->V; i++) { printf("%2d:", i); for (j = 0; j < G->V; j++) if (G->adj[i][j] == 1) printf(" %2d", j); putchar(\n); } } De complejidad O(V2). El cual entregara el siguiente listado. 5 vertices, 6 edges 0:34 1:24 2:13 3:024 4:013 0 3 4 1 2 0 1 2 5 3 4 Grafos9 Profesor Leopoldo Silva Bijit20-01-2010 10.2.4.8. Despliegue de la matriz de incidencias. //Muestra Matriz de incidencia. void GRAPHshowM(Graph G) { int i, j;printf("%d vertices, %d edges\n", G->V, G->E); printf(""); for (j = 0; j < G->V; j++) printf(" %2d", j); putchar(\n); for (i = 0; i < G->V; i++) { printf("%2d:", i); for (j = 0; j < G->V; j++) if (G->adj[i][j] == 1) printf(" %2d", 1); else printf(" %2d", 0); putchar(\n);} } Que genera, para el ejemplo: 5 vertices, 6 edges 01234 0:00011 1:00101 2:01010 3:10101 4:11010 10.2.4.9. Generacin de los elementos a partir de la matriz de incidencias. Si el grafo ya est construido, la generacin de los elementos, a partir del grafo, se logra con la funcin: int GRAPHedges(Edge a[], Graph G) { int v, w, E = 0;//numera los elementos desde el cero. for (v = 0; v < G->V; v++)//Para todos los renglones for (w = v+1; w < G->V; w++)//revisa por columnas if (G->adj[v][w] == 1)a[E++] = EDGE(v, w); //escribe por referencia return E;//retorna el nmero de elementos. } Se advierte que debido a los dos for anidados es O( (V2-V)/2 ), ya que revisa sobre la diagonal. Encontrar los elementos a partir del grafo se realiza con: GRAPHedges(Elementos, Grafo);//Llena el arreglo a partir del Grafo. Ntese que al recorrer la submatriz sobre la diagonal, por renglones, va reasignando, a partir de cero, los nombres de los elementos, y sus correspondientes vrtices. 10Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 elementovw 003 104 212 314 423 534 Figura 10.9. Generacin de los elementos a partir de matriz de adyacencias. Debidoaquelamatrizdeadyacenciasnoalmacenainformacinsobreelnombredelos elementos, el arreglo de elementos toma los nombres dados por el recorrido. 10.3. Trayectorias en grafos. Un primer problema es determinar si existe una trayectoria entre dos vrtices. Si se define un arreglo en que se marque si los nodos han sido o no visitados, puede plantearse el siguiente esquema recursivo: Si el vrtice inicial y el final son iguales, hay trayectoria (fin de recursin). Marcar el vrtice inicial como visitado. Revisar todos los vrtices, conectados al inicial: Si uno no ha sido revisado: ver si hay trayectoria entre ese y el final. Si revisados todos no hay trayectoria, entonces no existe la trayectoria buscada. int pathR(Graph G, int v, int w) { int t;if (v == w) return 1;//Existe trayecto. Nodo inicial y final son iguales. visited[v] = 1; for (t = 0; t < G->V; t++) if (G->adj[v][t] == 1)//Si v est conectado con t if (visited[t] == 0)//y t no ha sido visitado {printf("%d-%d ", v, t);//Debug: Muestra elemento de trayectoria en prueba. if (pathR(G, t, w)) return 1; } return 0; } 0 3 4 1 2 2 3 4 0 5 1 01234 000011 100101 201010 310101 411010 Grafos11 Profesor Leopoldo Silva Bijit20-01-2010 int GRAPHpath(Graph G, int v, int w) { int t;for (t = 0; t < G->V; t++) visited[t] = 0; return pathR(G, v, w);//Inicia bsqueda recursiva. } Un ejemplo de invocacin: if( GRAPHpath(Grafo, 1, 3)) printf("existe trayectoria, entre 1 y 3\n"); else printf("no existe trayectoria.\n");

Existendosformasbsicasdeexploracindeungrafo:Labsquedaprimeroenprofundidad (Depth-first search) y la bsqueda primero en extensin (Breadth first search). 10.3.1. Bsqueda primero en profundidad. 10.3.1.1. Definicin de bsqueda primero en profundidad. Se recorre el grafo, siempre hacia adelante hasta que se llega al final o hasta una trayectoria que ya se ha recorrido; luego se devuelve y busca trayectorias no exploradas. El objetivo es buscar un rbol. Se visita y marca un vrtice como visitado, luego se visitan (recursivamente) todos los vrtices adyacentes al recin marcado que no estn visitados. Esto va formando un rbol, con el orden en que se van visitando los vrtices. Para el grafo a la izquierda de la Figura 10.10.: Si el vrtice inicial es el 0 (se pasa el elemento (0,0), se lo visita y marca con la cuenta 0, y se generan llamados con los elementos (0,3) y (0,4), en ese orden. Figura 10.10. Orden de visitas, generacin de llamados. El llamado con el elemento (0, 3) marca el 3 con la cuenta 1, y se generan los llamados: con (3, 2), (3,4). El llamado con el elemento (3, 2) marca el 2 con la cuenta 2, y se genera el llamado:(2,1). El llamado con el elemento (2, 1) marca el 1 con la cuenta 3, y se genera el llamado:(1,4). El llamado con el elemento (1, 4) marca el 4 con la cuenta 4 y no genera nuevos llamados. Resultandoel rbol T(1, 2, 3, 4) ilustrado en la figura a la derecha. 0 3 4 1 2 0 3 4 1 2 3 4 2 1 12Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 10.3.1.2. Diseo de la operacin. La funcin recursiva: void dfsR(Graph G, Edge e) { int t, w = e.w; pre[w] = cnt++;//Marca con contador creciente for (t = 0; t < G->V; t++) { if (G->adj[w][t] != 0)//Si hay conexin entre w y t if (pre[t] == -1) dfsR(G, EDGE(w, t)); //Y si t no est visitado sigue buscando. }} La funcinque efecta la bsqueda en profundidad: void GRAPHsearchDFS(Graph G) //depth-first-search { int v; cnt = 0;//es variable global for (v = 0; v < G->V; v++) pre[v] = -1;//Marca todos como no visitados for (v = 0; v < G->V; v++)//Revisa todos los vrtices. if (pre[v] == -1) dfsR(G, EDGE(v, v));//Se invoca varias veces si el grafo es no conectado. } Sevisitantodosloselementosytodoslosvrticesconectadosalvrticedepartida,no importandoelordenenquerevisaloselementosincidentesenesevrtice.Laestrategia recursiva implica un orden: el ltimo que entr es el primero que sali (LIFO),de los elementos posibles se elige el ms recientemente encontrado. 10.3.1.3. Modificacin para entender la operacin. Seagregalavariableestticaindente,parairmostrandoloselementosquesonsometidosa revisin. Cada vez que se genera un llamado se produce un mayor nivel de indentacin; el cual es repuesto al salir del llamado recursivo. Se agrega un asterisco para mostrar los elementos que generan llamados recursivos. static int indente=0; void dfsR(Graph G, Edge e) { int t,j, w = e.w; pre[w] = cnt++; for (t = 0; t < G->V; t++) { if (G->adj[w][t] != 0) { for (j = 0; j < indente; j++) printf(""); printf("%d-%d \n", w, t); if (pre[t] == -1) { indente++; putchar('*'); dfsR(G, EDGE(w, t)); Grafos13 Profesor Leopoldo Silva Bijit20-01-2010 indente--; }else putchar(' '); }}} Para el grafo del ejemplo de la figura 10.10., se produce el listado: 0-3*3-03-2*2-1*1-21-4*4-04-14-32-3 3-4 0-4 Este algoritmo puede emplearse: para detectar circuitos, para saber si existe una trayectoria que conecte a dos vrtices dados, para determinar si es un grafo conectado, para encontrar un rbol. Ver propiedades de los rboles dfs en Sedgewick 18.4. 10.3.1.4. Arreglo de padres. Lasiguientemodificacinpermitealmacenarenelarreglostelpadredelvrticew.Esa informacin es til para aplicaciones de este algoritmo. Y es una forma de describir el rbol.

static int st[VERTICES]; void dfsR(Graph G, Edge e) { int t, j, w = e.w; pre[w] = cnt++;//Marca con contador creciente st[e.w] = e.v; //Se guarda el padre de w.for (t = 0; t < G->V; t++) { if (G->adj[w][t] != 0)//Si hay conexin entre w y t if (pre[t] == -1) dfsR(G, EDGE(w, t)); //Y t no est visitado busca t. }} Para el ejemplo, quedaran almacenados en st:0, 2, 3, 0, 1.Y en pre: 0, 3, 2, 1, 4. El rbol que genera este algoritmo, se produce revisando los elementos en el siguiente orden: 14Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 0-3,*3-0,3-2,*2-1,*1-2,1-4,*4-0,4-1,4-3,2-3,3-4,0-4.Losquegeneranllamados recursivos,seprecedenconunasterisco.Lailustracinmuestraqueseavanzaprimeroen profundidad. 0 3 4 0 24 13 24 0 13 Figura 10.11. Visualizacin de los llamados, en profundidad. 10.3.1.5. Uso de stack en bsqueda en profundidad. Se emplea un stack para guardar los vrtices. //rbol en profundidad. No recursivo void dfs(Graph G, Edge e) { int t, v, w, f; StackInit(G->V*2);StackPush(e.v);StackPush(e.w);//empuja los vrtices del elemento while(!StackEmpty()) {w=StackPop(); v=StackPop(); StackPush(v); f=1; //guarda ruta en el rbol pre[w] = cnt++;st[w] = v;// se guarda el vrtice padre de w. while(f) { for (t = 0; t < G->V; t++) { if (G->adj[w][t] != 0) if (pre[t] == -1) { StackPush(w); StackPush(t); printf("*%d-%d \n", w, t); f=0; break;}} Grafos15 Profesor Leopoldo Silva Bijit20-01-2010 if (f) //lleg al final de un recorrido en el rbol. {if (!StackEmpty()) w=StackPop(); //extrae vrtice anterior del rbol else f=0; }} } Stackdestroy(); } void GRAPHsearchDFSnr(Graph G) { int v; cnt = 0; for (v = 0; v < G->V; v++) {pre[v] = -1; st[v] = -1;} for (v = 0; v < G->V; v++) if (pre[v] == -1) dfs(G, EDGE(v, v)); } 10.3.2. Bsqueda primero en extensin. 10.3.2.1. Definicin de la bsqueda primero en extensin. La bsqueda en extensin tiene por objetivo encontrar la ruta ms corta entre dos vrtices dados. Tambin se genera un rbol. Separtedeunnodo,ysebuscaelsiguientenodoentodaslasrutasdelargo unoqueexistan; luego se buscan todas las rutas de largo dos, y as sucesivamente. Explorar los vrtices, de acuerdo a su distancia al de partida, implica que de los elementos que son posibles, se escoge uno y los otros se salvan para ser posteriormente explorados.Este orden es: el primero que se encuentra, es el primero en ser procesado (FIFO). Paravisitarunvrtice:sebuscanloselementosquesonincidentesconesevrtice,ylos elementos que tienen el otro vrtice no visitado, se encolan. Para el siguiente grafo: Figura 10.12. Ejemplo para bsqueda primero en extensin. 0 3 4 1 2 16Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 A partir del nodo inicial 0, se marca el 0, y se exploran los elementos: 0-3 y 0-4. Se encolan el 0-3 y el 0-4. Ya que el 3 y 4 no han sido visitados an. Se desencola el 0-3, se marca el 3, y se revisan el 3-0, el 3-2 y el 3-4. Se encolan el 3-2 y el 3-4. Ya que el 2 y el 4 no han sido visitados an. Se desencola el 0-4, se marca el 4, y se revisan el 4-0, 4-1 y 4-3. Se encola el 4-1. Se desencola el 3-2, se marca el 2, y se revisan el 2-1, 2-3. Se encola el 2-1. Se desencola el 3-4 sin procesar. Se desencola el 4-1, se marca el 1, y se revisan el 1-2 y 1-4. Se desencola el 2-1 sin procesar. Del rbol formado, se visualiza, que el vrtice 0 est a distancia uno de los vrtices 3 y 4, y que est a distancia 2, de los vrtices 1 y 2. Los vrtices se marcan en el siguiente orden: 0, 3, 4, 2, 1.

Figura 10.13. Orden de visitas, generacin de llamados. En extensin. La figura10.13. ilustra que se busca por largos de trayectos. 10.3.2.2. Diseo de la operacin. El cdigo de la funcin que encola los elementos.En la cola se almacenan elementos. void bfs(Graph G, Edge e)//breadth-first-search { int v; QUEUEput(e); while (!QUEUEempty()) if (pre[(e = QUEUEget()).w] == -1) { pre[e.w] = cnt++; //en pre queda el orden en que se escogen los vrtices st[e.w] = e.v;//en st queda el padre. for (v = 0; v < G->V; v++) if (G->adj[e.w][v] == 1) if (pre[v] == -1)QUEUEput(EDGE(e.w, v)); } }

La funcin que genera el rbol BFS.void GRAPHsearchBFS(Graph G) { int v; 0 34 0 24 13 24 0 13 Grafos17 Profesor Leopoldo Silva Bijit20-01-2010 cnt = 0; QUEUEinit(ELEMENTOS); for (v = 0; v < G->V; v++) {pre[v] = -1; st[v]=-1;}//Inicio de estructuras for (v = 0; v < G->V; v++) // Para todos los vrtices if (pre[v] == -1) bfs(G, EDGE(v, v));//Se invoca una vez, si el grafo es conectado. QUEUEdestroy();} 10.4. rboles con peso.Siloselementostienenasociadounpesosedeseaencontrarunrboltalquelasumadelos pesos de sus ramas sea mnimo. Previo a resolver este problema es necesario modificar las estructuras de datos para incorporar elpesodelelemento.Puedeescogerseunnmerorealentre0.ymenorque1.Estopuede lograrse dividiendo los pesos reales por el peso del mayor levemente incrementado.Modificacin de las funciones para tratar grafos con pesos. Se elige:typedef struct{ int v; //vrtice inicial int w; //vrtice final float wt;//peso.Puede ser un double } Edge; El constructor queda ahora: Edge EDGE(int v, int w, float wt) { Edge t; t.v=v; t.w=w; t.wt=wt; return (t); } Para un grafo se definen: struct graph {int V;//Nmero de vrtices int E;//Nmero de elementos float **adj;// Matriz de adyacencias }; typedef struct graph *Graph; Para marcar la no existencia de adyacencias, se define: #define maxWT1.//Todo elemento tiene menor peso que maxWT. 18Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 La inicializacin de un grafo vaco, se logra con: Graph GRAPHinit(int V) { Graph G = malloc(sizeof *G);//crea cabecera del grafo G->V = V; G->E = 0; G->adj = MATRIXfloat(V, V, maxWT); return G; } Donde la funcin que localiza espacio dinmico para la matriz de adyacencias es: float **MATRIXfloat(int r, int c, float wt) { int i, j; float **t = malloc(r * sizeof(float *)); for (i = 0; i < r; i++) t[i] = malloc(c * sizeof(float)); for (i = 0; i < r; i++) for (j = 0; j < c; j++) t[i][j] = wt; //**(t+i+j) = wt; return t; } El resto de las funciones se modifican para tratar grafos ponderados: void BorreGrafo(Graph G)//Libera el espacio adquirido por malloc. { int i; float **t = G->adj; for (i = 0; i < G->V; i++) free(t[i]); free(t); free(G); } void GRAPHinsertE(Graph G, Edge e)//Inserta elemento {if (G->adj[e.v][e.w] == maxWT) G->E++; G->adj[e.v][e.w] = e.wt;G->adj[e.w][e.v] = e.wt;//suprimir para grafos dirigidos } void GRAPHremoveE(Graph G, Edge e)//Remueve elemento { if (G->adj[e.v][e.w] != maxWT) G->E--; G->adj[e.v][e.w] = maxWT;G->adj[e.w][e.v] = maxWT; //suprimir para grafos dirigidos } int GRAPHedges(Edge a[], Graph G) //Forma arreglo de elementos a partir del grafo { int v, w, E = 0; Grafos19 Profesor Leopoldo Silva Bijit20-01-2010 for (v = 0; v < G->V; v++) for (w = v+1; w < G->V; w++) if (G->adj[v][w] != maxWT) a[E++] = EDGE(v, w, G->adj[v][w]);return E; } //muestra la matriz mediante listas de vrtices conectados a cada vrtice void GRAPHshowL(Graph G) { int i, j;printf("%d vertices, %d edges\n", G->V, G->E); for (i = 0; i < G->V; i++) { printf("%d: ", i); for (j = 0; j < G->V; j++) if (G->adj[i][j] != maxWT) printf(" %0.2f", G->adj[i][j]); putchar('\n'); } } //Muestra Matriz de adyacencias. void GRAPHshowM(Graph G) { int i, j;printf("%d vertices, %d edges\n", G->V, G->E); printf(" "); for (j = 0; j < G->V; j++) printf(" %4d ", j); printf("\n"); for (i = 0; i < G->V; i++) { printf("%2d:", i); for (j = 0; j < G->V; j++) if (G->adj[i][j] != maxWT) printf(" %0.2f", G->adj[i][j]); else printf("* "); putchar('\n');} } Se limita a dos el nmero de cifras significativas. Las siguientes lneas describen un grafo a partir de sus elementos. #define VERTICES 8 #define ELEMENTOS 12 //Variables Graph Grafo; //Edge Elementos[ELEMENTOS]={{0,2,.29},{4,3,.34},{5,3,.18},{7,4,.46},{7,0,.31},\ {7,6,.25},{7,1,.21},{0,6,.51},{6,4,.52},{4,5,.40},\ {5,0,.59},{0,1,.32} }; 20Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 Ladescripcindelgrafo,descritoporsuselementos,segnlalistadevrticesadyacentes resulta: 8 vrtices, 12 elementos 0:0.32 0.29 0.59 0.51 0.31 1:0.32 0.21 2:0.29 3:0.34 0.18 4:0.34 0.40 0.52 0.46 5:0.59 0.18 0.40 6:0.51 0.52 0.25 7:0.31 0.21 0.46 0.25 La matriz de adyacencias con los pesos, resulta: 0 1 2 3 4 5 6 7 0:* 0.32 0.29 * *0.59 0.51 0.31 1: 0.32 * * * * * *0.21 2: 0.29 * * * * * * * 3:* * * *0.34 0.18* * 4:* * *0.34*0.400.52 0.46 5: 0.59 * *0.180.40* * * 6: 0.51 * * *0.52* * 0.25 7: 0.310.21 * *0.46*0.25 * Elsiguienteejemplomuestralasmodificacionesalageneracindeunrbol,empleando bsqueda primero en profundidad. Se agrega el vector wt con los pesos. static int cnt; static int pre[VERTICES]; static int st[VERTICES]; static float wt[VERTICES]; void dfsR(Graph G, Edge e) { int t; pre[e.w] = cnt++;st[e.w] = e.v;//se guarda el vrtice v padre de w. wt[e.w]=G->adj[e.w][e.v];//se guarda el peso del elemento w-v for (t = 0; t < G->V; t++) {if (G->adj[e.w][t] != maxWT) if (pre[t] == -1) {dfsR(G, EDGE(e.w, t, maxWT)); /*printf("%d-%d \n", e.w, t);*/} }} Grafos21 Profesor Leopoldo Silva Bijit20-01-2010 void GRAPHsearchDFS(Graph G) { int v; cnt = 0; for (v = 0; v < G->V; v++) {pre[v] = -1; st[v] = -1;}//Inicializacin for (v = 0; v < G->V; v++) if (pre[v] == -1) dfsR(G, EDGE(v, v, maxWT)); } La cual entrega en st la descripcin del rbol a partir de un arreglo de padres de los vrtices. 0 1 2 3 4 5 6 7Vrtices. 0 0 0 4 7 3 4 1Padre del vrtice. 1.00.320.290.340.460.180.520.21Peso del elemento entre vrtice y su Padre. La raz del rbol (vrtice 0) tiene un lazo de peso infinito (valor 1.0) consigo misma. Este rbol cubre todos los nodos, pero no es un rbol de cobertura mnima. 10.5. Mnimo rbol de cobertura. Para un grafo dado existe un muy elevado nmero de rboles. No es fcil encontrar el rbol de cobertura mnima. Algunos conceptos para definir el rbol de cobertura mnima: Un elemento del rbol se denomina rama. Siseagregaunelementoaunrbolsecreaunnicocircuito,elelementoagregadosuele denominarsecuerda.Uncircuitofundamentalestformadoporunacuerdayelrestodelos elementos deben ser ramas. Un conjunto de corte son los elementos que unen dos conjuntos disjuntos de vrtices. Uno de los elementos del conjunto de corte debe ser rama. Si los elementos tienen pesos diferentes, la rama del conjunto de corte debe tener peso mnimo.Si existen mltiples elementos mnimos en el corte, al menos uno de ellos debe estar presente. Entonces: Cada rama de un mnimo rbol de cobertura es el elemento mnimo de un conjunto de corte. Astambinlascuerdasdebentenerlosmximospesosdeloscircuitosqueformenconel mnimo rbol de cobertura. La formacin de un MST (minimum spanning tree) consiste en aplicar las reglas anteriores, para rechazar elementos que sean cuerdas, con peso mximo; y aceptar ramas, con pesos mnimos. El algoritmo de Prim, elige un vrtice cualquiera como inicial.22Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 Luego repite para los (V-1) vrtices restantes: AgregarelementodepesomnimoqueconectelosvrticesdelMST,conlosvrtices que an no pertenecen al MST. ElalgoritmodeKruskalprocesaloselementosordenadosporsuspesos.Sevaagregandoal MST un elemento que no forme circuitos con los previamente agregados, y se detiene si se han agregado (V-1) elementos. Esto porque en grafos conectados el rbol tiene (V-1) ramas. 10.5.1. Algoritmo de Prim. Si se tienen vrtices en el MST, se busca un vrtice w que an no est en el rbol, tal que est a menor distancia de los vrtices del MST.Para esto es preciso registrar las menores distancias, de cada nodo no perteneciente al MST, a los nodos pertenecientes al MST; y elegir la menor. Figura 10.14. Conjuntos en el algoritmo de Prim. Para disear el algoritmo se emplean tres arreglos: static int padre[VERTICES];// padre del vrtice static int DistaMenosDe[VERTICES];//vrtice que dista menos del vrtice del rbol. static float wt[VERTICES+1];//distancia menor. Con espacio para centinela. El rbol se describe por el arreglo padre[v], donde se almacena el padre del vrtice v. Se inicia con valores iguales a menos uno, para indicar que ningn vrtice forma parte del rbol. SeagregaunarregloDistaMenosDe[w],enelcual,duranteelprocesamiento,sedejarel vrticemscercanoawdelrbol.SeiniciaconDistaMenosDe[i]=i,indicandoqueesta informacin no se conoce. Antes se emple un arreglo wt[w] para almacenar los pesos de los elementos, ahora se usa para almacenar la mnima distancia al rbol, si el vrtice w an no pertenece al rbol; y la distancia al padre,siel vrticewya pertenece al MST. Al inicio se lo llena con maxWT, para indicar que esta informacin sobre pesos mnimos an no se conoce. Enlavariablelocalminsealmacenaelvrtice,queannopertenecealMST, yelcualdebe cumplirlapropiedaddetenerdistanciamnimaconlosvrticesqueyaestnenel MST.Para asociarle un peso, se agrega una entrada al arreglo wt, con valor maxWT, y se lo inicia con valor V (vrtice que no existe en el grafo). De esta forma wt[min] tendr un espacio y valor definido. MST w Grafos23 Profesor Leopoldo Silva Bijit20-01-2010 #define NoVisitado -1 #define SinPadre -1 #define Peso G->adj[v][w] void mstPrim(Graph G, int raiz) { //Inicio del espacio de variables int v, w, min=raiz, cnt;for (v = 0; v < G->V; v++) { padre[v] = SinPadre; DistaMenosDe[v] = v; wt[v] = maxWT; } wt[G->V] = maxWT; //centinela. Arreglo requiere una posicin adicional wt[raiz]=0.; //raz a distancia cero de s misma. for (cnt=0; cnt< G->V; cnt++)//agrega todos los vertices O(V2) { v = min; padre[v] = DistaMenosDe[v];//agrega vrtice v al MST //printf(" %d \n", v); //orden en que son agregados los vrtices. //Selecciona vrtice min con distancia mnima a los vrtices del mst for (w = 0, min = G->V; w < G->V; w++) //Al inicio min es un vrtice que no existe. if (padre[w] == NoVisitado) //si w no est an en el MST { if (Peso < wt[w]){ wt[w] = Peso; DistaMenosDe[w] = v; } //salva distancia menor y el vrtice. if (wt[w] < wt[min]) min = w; //selecciona nuevo vrtice a distancia mnima } //Al salir del for interno se tiene el nuevo vrtice que se agrega al MST} } Paralosdatosanteriores,luegodeejecutadoelAlgoritmodePrim,conrazenvrtice0,se genera: 0 1 2 3 4 5 6 7 Vrtices. 0 7 0 4 7 3 7 0 Padre del vrtice. 0 0.210.290.340.460.180.250.31 Peso elemento entre vrtice y su Padre. 0 7 0 4 7 3 7 0 Vrtice que dista menos del vrtice del rbol La suma = 0.21+0.29+0.34+0.46+0.18+0.25+0.31es la mnima. 10.5.2. Algoritmo de Kruskal. Se inicia con un conjunto vaco los vrtices del rbol de mnima cobertura. Luego de ordenados loselementosporsuspesos,seagregaunelementoporvez,losdemenorpesoseintentan agregar primero. Antes de agregar los vrtices del elemento al rbol, se revisa que no se formen circuitos.Elprocedimientoterminacuandosetengantodoslosvrticesenelconjuntoose hayan agregado (Vrtices-1) ramas al rbol. 24Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 Verificarquelosvrticesagregados,asociadosaunelemento,noformencircuitosnoesuna tareasencilla.Unaprimeraaproximacinesdefinirunarregloiddevrticesquemantengala informacin booleana de si un vrtice ha sido agregado o no. La Figura 10.15, muestra las ramas, definidas por sus vrtices: (1, 4), (1, 5) y (0, 3), que ya han sido agregadas al rbol. Al inicio se marcan todos los vrtices con 0, indicando que an no han sidoconsiderados.Entoncessielanddeid[v]eid[w]esverdaderonoseagregaelelemento (u,w) y se considera el siguiente elemento de mayor peso; si es falso se marcan los vrtices con 1, indicando su consideracin.Los vrtices: 2 y 6 an no han sido agregados, y los elementos considerados forman una foresta o un conjunto de subrboles no conectados entre s. 14 5 0 3 0123456 1101110 Figura 10.15. Generacin MST. Algoritmo de Kruskal. La informacin anterior no permitira agregar una rama que conecte, por ejemplo los vrtices 3 y 4; ya que estos vrtices ya estn marcados. Para superar esto pueden identificarse en el arreglo acualdelossubrbolespertenecenlosvrtices.Seiniciaelarregloforestaconelndice correspondientealvrtice;deestemodo,aliniciocadavrticequedaasociadoaunsubrbol vaco. Al agregar un elemento cuyos dos vrtices no pertenezcan a ninguno de los subrboles se los marca pertenecientes a un rbol de la foresta; se emplea nmeros para identificar los rboles con enteros mayores que el nmero de vrtices. Despusdeagregarelelemento(1,4)elarregloforestaquedacomoseindicaenlaFigura 10.15a. 14 0123456 0723756 foresta Figura 10.15a. Creacin de primer rbol de la foresta. La condicin: (foresta[u] != foresta[w])toma valor verdadero si el elemento (u, w) no pertenece al rbol. Siseagregaelemento(1,5),elvrtice5 no pertenece aun subrbol y el vrtice 1 pertenece al subrbol 7,se marca el vrtice 5 como perteneciente al subrbol 7. Esto se ilustra en la Figura 10.15b. Grafos25 Profesor Leopoldo Silva Bijit20-01-2010 14 0123456 0723776 foresta 5 Figura 10.15b. Agrega elemento a subrbol de la foresta. Si se agrega el elemento (0, 3), se crea un nuevo subrbol con identificador 8. Resulta la Figura 10.15c. 14 0123456 8728776 foresta 5 0 3 Figura 10.15c. Agrega elemento a subrbol de la foresta. Si se desea agregar el elemento (3, 4), con la informacin de los subrboles de la foresta, ahora es posible efectuarlo. Sin embargo deben unirse los subrboles, esto puede efectuarse cambiado los identificadores de uno de los subrboles. Esto se muestra en la Figura 10.15d. 14 0123456 7727776 foresta 5 0 3 Figura 10.15d. Unin de subrboles de la foresta. int foresta[VERTICES]; static int cntf; void UneSubArboles(int p, int q) { int i, t; if ( (foresta[p]==p) && (foresta[q]==q) ) {foresta[p]=cntf; foresta[q]=cntf; cntf++;} //crea subrbol else if (foresta[p]adj = MATRIXfloat(V, V, maxWT); 30Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 return G; } void GRAPHinsertE(Graph G, Edge e)//Inserta elemento {if (G->adj[e.v][e.w] == maxWT) G->E++; G->adj[e.v][e.w] = e.wt; // Slo el elemento dirigido.} void GRAPHremoveE(Graph G, Edge e)//Remueve elemento { if (G->adj[e.v][e.w] != maxWT) G->E--; G->adj[e.v][e.w] = maxWT;} int GRAPHedges(Edge a[], Graph G)//Crea arreglo a de elementos a partir de G. { int v, w, E = 0; for (v = 0; v < G->V; v++) for (w = 0; w < G->V; w++) if ((G->adj[v][w] != maxWT)&&(G->adj[v][w] != 0)) a[E++] = EDGE(v, w, G->adj[v][w]);return E; } //muestra la matriz mediante listas de vrtices conectados a cada vrtice void GRAPHshowL(Graph G) { int i, j;printf("%d vrtices, %d elementos.\n", G->V, G->E); for (i = 0; i < G->V; i++) {printf("%d: ", i); for (j = 0; j < G->V; j++) if (G->adj[i][j] != maxWT) printf(" %2d-%0.2f", j, G->adj[i][j]);//dos decimales putchar('\n'); } } //Muestra Matriz de incidencia. void GRAPHshowM(Graph G) { int i, j;printf("%d vrtices, %d elementos.\n", G->V, G->E);printf(" "); for (j = 0; j < G->V; j++) printf(" %4d ", j);printf("\n"); for (i = 0; i < G->V; i++) { printf("%2d:", i); for (j = 0; j < G->V; j++) if (G->adj[i][j] != maxWT) printf(" %0.2f", G->adj[i][j]); else printf("* "); putchar('\n');} Grafos31 Profesor Leopoldo Silva Bijit20-01-2010 } Las siguientes definiciones, permiten crear un grafo de seis vrtices y 11 elementos. #define VERTICES 6 #define ELEMENTOS 11 //Variables Graph Grafo; Edge Elementos[ELEMENTOS]={{0,1,.41},{1,2,.51},{2,3,.50},{4,3,.36},\ {3,5,.38},{3,0,.45},{0,5,.29},{5,4,.21},\ {1,4,.32},{4,2,.32},{5,1,.29} }; Se inicia el grafo con: Grafo = GRAPHinit(VERTICES); Y la insercin de los elementos con sus pesos se logra con: for(i=0; iadj[e.v][e.w] void dfsR(Graph G, Edge e) { int t; pre[e.w] = cnt++; //orden en que recorre el rbol padre[e.w] = e.v; //se guarda el vrtice v padre de w. wt[e.w] = wt[e.v] + Pesoew; //se guarda el peso del elemento v-w ms el acumulado // desde la raz a v. for (t = 0; t < G->V; t++) if (G->adj[e.w][t] != maxWT) if (pre[t] == NoVisitado) {dfsR(G, EDGE(e.w, t, maxWT)); /*printf("%d-%d \n", e.w, t);*/ } } La rutina recursiva anterior es llamada por: void GRAPHsearchDFS(Graph G) { int v; cnt = 0; for (v = 0; v < G->V; v++) {pre[v] = NoVisitado; padre[v] = SinPadre; wt[v]=0.;} for (v = 0; v < G->V; v++) if (pre[v] == NoVisitado) dfsR(G, EDGE(v, v, maxWT));//Si el grafo no es conectado, obtiene foresta. } La cual genera el siguiente rbol de trayectorias, descrito por un arreglo de padres. Grafos33 Profesor Leopoldo Silva Bijit20-01-2010 0 1 2 3 4 5Vrtices. 0 0 1 2 5 3Padre del vrtice. 0.000.410.921.422.011.80Peso trayecto entre vrtice y la raz. 0 1 2 3 5 4Orden en que visita los vrtices. El rbol DFS generado no es un SPT mnimo. 0 0.41 1 5 2 0.51 4 3 0.50 0.38 0.21 0 0.41 1 5 0.29 2 0.51 4 0.32 3 0.50 0.45 0.38 0.32 0.36 0.29 0.21 Figura 10.19. rbol de trayectorias DFS. Elrboldebsquedaprimeroenextensinesunamejoraproximacin,perotampocoesun SPT. 012 3 45Vrtices. 001 2 10Padre del vrtice. 0.000.410.921.420.730.29Peso trayecto entre vrtice y la raz. 013 5 42Orden en que visita los vrtices. 0 0.41 1 5 0.29 2 0.51 4 0.32 3 0.50 0 0.41 1 5 0.29 2 0.51 4 0.32 3 0.50 0.45 0.38 0.32 0.36 0.29 0.21 Figura 10.19a. rbol de trayectorias BFS. 10.5.2. Algoritmo de Dijkstra. Determina un SPT, un rbol con las mnimas trayectorias, desde un vrtice a los dems. No se aceptan elementos en paralelo, ni elementos con pesos negativos. El algoritmo consiste inicialmente en colocar el vrtice fuente en el SPT. Luego, se agrega un elemento por vez, agregando un vrtice. Siempre tomando el elemento que tenga el trayecto ms corto entre la fuente y el vrtice que no est en el SPT. 34Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 SeimplementaunasolucinsimilaralalgoritmodePrim,perosevanagregandovrticesque estn a la menor distancia de la raz. Escoger raz. Repetir hasta agregar todos los vrtices: Encontrar un nodo (sea min) cuya distancia a la raz sea la menor entre todos los nodos no pertenecientes al SPT. Marcar ese nodo (sea v) como perteneciente al SPT. Repetir para cada w nodo no perteneciente al SPT: Si hay conexin entre v y w, y si la distancia del nodo raz a v ms la distancia de v a w es menor que la distancia actual de la raz a w: Actualizar la distancia de la raz a w como la distancia de la raz a v ms la distancia de v a w. Actualizar el nuevo padre de w Actualizar el vrtice que est a distancia mnima. raz v w wt[w] wt[v] Figura 10.20. Distancias en algoritmo de Dijkstra. Se requieren tres arreglos para implementar el algortimo: static int padre[VERTICES]; static int DistaMenosDe[VERTICES]; //vrtice que dista menos del vrtice del rbol. static float wt[VERTICES+1];//distancia menor de raz a vrtice. Requiere un espacio // adicional que se emplea como centinela. #define Peso G->adj[v][w]#define PesoRutawt[v] + Peso//distancia de raz a v, ms la del elemento v-w #define SinPadre -1 #define NoVisitado -1 void sptDijkstra(Graph G, int raiz) { //Inicio del espacio de variables int v, w, min=raiz, cnt;for (v = 0; v < G->V; v++) Grafos35 Profesor Leopoldo Silva Bijit20-01-2010 { padre[v] = SinPadre; //se inician como no visitados todos los vrtices DistaMenosDe[v] = v; //Al inicio cada vrtice dista menos de si mismo. wt[v] = VERTICES ;//Peso mximo de los trayectos = nmero de ramas + 1 } wt[raiz] = 0.; //raz a distancia cero wt[G->V] = VERTICES;//centinela. Requiere una posicin adicional con peso mximo. //El for externo agrega, uno a uno, los vrtices al SPT. for (cnt=0; cnt< G->V; cnt++) //agrega todos los vrtices.O(V2) { v = min; padre[min] = DistaMenosDe[min]; //agrega vrtice v al SPT //printf(" %d \n", min);//orden en que agrega los vrtices for (w = 0, min = G->V; w < G->V; w++) //Al inicio min es un vrtice que no existe. if (padre[w] == NoVisitado) //si w no est en el SPT { if ( (Peso!=maxWT) && (PesoRuta < wt[w]) ) //Si hay conexin desde v a w, y//Si la distancia del nodo raz a v ms la distancia de v a w es menor que// la distancia actual de la raz a w { wt[w] = PesoRuta; //actualiza distancia de la raz a w DistaMenosDe[w] = v; //salva al padre de w. }if (wt[w] < wt[min]) min = w; //actualiza el vrtice candidato al mnimo } //Al salir del for interno se tiene el nuevo vrtice que se agrega al SPT } } El siguiente llamado genera un shortest path tree, como un arreglo de padres, a partir del grafo G, con fuente o raz 2. sptDijkstra(Grafo, 2); 0 1 2 3 4 5Vrtices. 3 5 2 2 5 3Padre del vrtice. 0.951.170.000.501.090.88Peso trayecto entre vrtice y raz.wt[i] 3 5 2 2 5 3Vrtice que Dista Menos Del vrtice del rbol La raz 2 a distancia cero de s misma. 36Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 01 5 2 4 3 0.50 0.45 0.38 0.29 0.21 Figura 10.21. SPT, raz 2. El SPT con fuente en el vrtice 0 se genera con:sptDijkstra(Grafo, 0). 0 1 2 3 4 5Vrtices. 0 0 4 4 5 0Padre del vrtice. 0.000.410.820.860.500.29Peso trayecto entre vrtice y raz. 0 0 4 4 5 0Vrtice que dista menos del vrtice del rbol 0 0.41 1 5 0.29 2 0.51 4 0.32 3 0.50 0.45 0.38 0.32 0.36 0.29 0.21 Figura 10.22. SPT, raz 0. El SPT con fuente en el vrtice 1 se genera con: sptDijkstra(Grafo, 1); 0 1 2 3 4 5 Vrtices. 31 1 4 1 3Padre del vrtice. 1.130.000.510.680.321.06Peso trayecto entre vrtice y raz. sptDijkstra(Grafo, 5), produce: 0 1 2 3 4 5Vrtices. 3 5 4 4 5 5Padre del vrtice. 1.020.290.530.570.210.00Peso trayecto entre vrtice y raz. sptDijkstra(Grafo, 4), produce: 0 1 2 3 4 5 Vrtices. 3 5 4 4 4 3Padre del vrtice. 0.811.030.320.360.000.74 Peso trayecto entre vrtice y raz.

Grafos37 Profesor Leopoldo Silva Bijit20-01-2010 Referencias. Robert Sedgewick, "Algorithms in C", Third edition, Addison Wesley, 1998. 38Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 Problemas resueltos. P10.1. Para el siguiente grafo orientado: Determinarelarreglodepesosdeltrayectodepesomnimoentrecadavrticeylaraz,yel arreglo padres del vrtice. a) Para raz igual al vrtice 4.b) Para raz igual al vrtice 2.

Solucin: a) 0 1 2 3 4 Vrtices. 4 0 3 4 4 Padre del vrtice. 0.300.701.000.500.00 Peso trayecto entre vrtice y raz. b) 0 1 2 3 4 Vrtices. 4 2 2 1 1 Padre del vrtice. 0.900.500.000.800.60 Peso trayecto entre vrtice y raz. P10.2. Se tiene un grafo definido por un arreglo de elementos. Edge Elementos[ELEMENTOS]={{0,1,.4},{1,2,.5},{2,3,.5},{3,4,.5},\ {1,4,.1},{0,4,.3},{1,3,.3}}; a) Dibujar el grafo. b) Determinar el mnimo rbol de cobertura aplicando algoritmo de Kruskal. Indicando el orden en que se eligen las ramas. Dibujar el rbol. c) Determinar el mnimo rbol de cobertura aplicando algoritmo de Prim. Indicando el orden en queseagreganlosvrtices,ylosarreglosdepadresydepesosentreelvrticeysupadre. Dibujar el rbol. d) Modificar la funcin de Prim para imprimir el orden en que se eligen los vrtices. Solucin. 0 4 0,3 1 0,4 0,1 3 0,3 0,5 0,5 0,5 2 Grafos39 Profesor Leopoldo Silva Bijit20-01-2010 a) b) Se eligen en el orden: 1- 4 =0.10 1- 3 =0.30 0- 4 =0.30 2- 3 =0.50 c) Se agregan en orden: 0, 4, 1, 3, 2. 0 1 2 3 4 Vrtices. 0 4 1 1 0 Padre del vrtice. 1.000.100.500.300.30 Peso elemento entre vrtice y su Padre. d) Se intercala el printf, entre las lneas que se indican. .. v = min; st[min] = fr[min];//agrega vrtice v al MST printf(" %d \n", min); for (w = 0, min = G->V; w < G->V; w++) . Ejercicios propuestos. E10.1. Partiendo del nodo A, determinar arreglo de padres para: rbol de bsqueda primero en extensin (bfs)rbol de bsqueda primero en profundidad (dfs) rbol de cobertura mnima aplicando algoritmo de Prim. 0 4 0,3 1 0,4 0,1 3 0,3 0,5 0,5 0,5 2 0 4 0,3 1 0,1 3 0,3 0,5 2 0 4 0,3 1 0,1 3 0,3 0,5 2 40Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 ABCDEFGHIJK4722148104136182217513398 Grafos41 Profesor Leopoldo Silva Bijit20-01-2010 ndice general. CAPTULO 10 ........................................................................................................................................... 1 GRAFOS. .................................................................................................................................................... 1 10.1. DEFINICIONES. ................................................................................................................................. 1 10.2. REPRESENTACIONES. ....................................................................................................................... 2 10.2.1. Matriz de adyacencia de los elementos en los vrtices. .......................................................... 2 10.2.2. Matrices estticas en C. .......................................................................................................... 3 10.2.3. Matrices dinmicas en C. ........................................................................................................ 4 Declaracin de estructuras de datos para un grafo. .......................................................................................... 4 Definicin de variables. ................................................................................................................................... 4 10.2.4. Funciones para grafos descritos por su matriz de adyacencias. ............................................. 5 10.2.4.1. Creacin. ........................................................................................................................................... 5 10.2.4.2. Liberacin del espacio. ..................................................................................................................... 6 10.2.4.3. Definicin de un elemento. ............................................................................................................... 6 10.2.4.4. Insercin de elemento en un grafo. ................................................................................................... 6 10.2.4.5. Eliminacin de elemento. .................................................................................................................. 7 10.2.4.6. Creacin de los elementos. ................................................................................................................ 7 10.2.4.7. Despliegue de un grafo. Lista de vrtices. ......................................................................................... 8 10.2.4.8. Despliegue de la matriz de incidencias. ............................................................................................ 9 10.2.4.9. Generacin de los elementos a partir de la matriz de incidencias. .................................................... 9 10.3. TRAYECTORIAS EN GRAFOS. .......................................................................................................... 10 10.3.1. Bsqueda primero en profundidad. ....................................................................................... 11 10.3.1.1. Definicin de bsqueda primero en profundidad. ........................................................................... 11 10.3.1.2. Diseo de la operacin. ................................................................................................................... 12 10.3.1.3. Modificacin para entender la operacin. ....................................................................................... 12 10.3.1.4. Arreglo de padres. ........................................................................................................................... 13 10.3.1.5. Uso de stack en bsqueda en profundidad. ..................................................................................... 14 10.3.2. Bsqueda primero en extensin. ............................................................................................ 15 10.3.2.1. Definicin de la bsqueda primero en extensin............................................................................. 15 10.3.2.2. Diseo de la operacin. ................................................................................................................... 16 10.4. RBOLES CON PESO. ...................................................................................................................... 17 Modificacin de las funciones para tratar grafos con pesos............................................................. 17 10.5. MNIMO RBOL DE COBERTURA. .................................................................................................... 21 10.5.1. Algoritmo de Prim. ................................................................................................................ 22 10.5.2. Algoritmo de Kruskal. ........................................................................................................... 23 10.5. TRAYECTORIAS MS CORTAS EN GRAFOS ORIENTADOS. ................................................................ 28 10.5.1. Modificacin de las funciones para tratar grafos orientados con pesos. .............................. 29 10.5.2. Algoritmo de Dijkstra. ........................................................................................................... 33 REFERENCIAS. ........................................................................................................................................ 37 PROBLEMAS RESUELTOS. ........................................................................................................................ 38 P10.1. Para el siguiente grafo orientado: ......................................................................................... 38 P10.2. Se tiene un grafo definido por un arreglo de elementos. ....................................................... 38 Ejercicios propuestos. ....................................................................................................................... 39 E10.1. ................................................................................................................................................ 39 NDICE GENERAL. ................................................................................................................................... 41 42Estructuras de Datos y Algoritmos Profesor Leopoldo Silva Bijit20-01-2010 NDICE DE FIGURAS. ................................................................................................................................ 43 Grafos43 Profesor Leopoldo Silva Bijit20-01-2010 ndice de figuras. FIGURA 10.1. ELEMENTO, VRTICE, INCIDENCIA........................................................................................... 1 FIGURA 10.2. ELEMENTOS ORIENTADOS. ...................................................................................................... 2 FIGURA 10.3. MATRIZ DE ADYACENCIAS. ..................................................................................................... 3 FIGURA 10.4. MATRIZ DE 2 RENGLONES POR 4 COLUMNAS. .......................................................................... 3 FIGURA 10.5. FORMA DE ALMACENAMIENTO DE MATRICES. ......................................................................... 3 FIGURA 10.6. ESTRUCTURA PARA MATRIZ DE ADYACENCIAS. ...................................................................... 5 FIGURA 10.7. GRAFO DESCRITO POR SUS ELEMENTOS. .................................................................................. 7 FIGURA 10.8. GRAFO PARA ELEMENTOS DE LA FIGURA 10.7. ........................................................................ 8 FIGURA 10.9. GENERACIN DE LOS ELEMENTOS A PARTIR DE MATRIZ DE ADYACENCIAS. .......................... 10 FIGURA 10.10. ORDEN DE VISITAS, GENERACIN DE LLAMADOS. ............................................................... 11 FIGURA 10.11. VISUALIZACIN DE LOS LLAMADOS, EN PROFUNDIDAD....................................................... 14 FIGURA 10.12. EJEMPLO PARA BSQUEDA PRIMERO EN EXTENSIN. .......................................................... 15 FIGURA 10.13. ORDEN DE VISITAS, GENERACIN DE LLAMADOS. EN EXTENSIN. ...................................... 16 FIGURA 10.14. CONJUNTOS EN EL ALGORITMO DE PRIM. ............................................................................ 22 FIGURA 10.15. GENERACIN MST. ALGORITMO DE KRUSKAL. .................................................................. 24 FIGURA 10.15A. CREACIN DE PRIMER RBOL DE LA FORESTA. ................................................................. 24 FIGURA 10.15B. AGREGA ELEMENTO A SUBRBOL DE LA FORESTA. ........................................................... 25 FIGURA 10.15C. AGREGA ELEMENTO A SUBRBOL DE LA FORESTA. ........................................................... 25 FIGURA 10.15D. UNIN DE SUBRBOLES DE LA FORESTA. .......................................................................... 25 FIGURA 10.16. DESCRIPCIN DE CONJUNTOS, MEDIANTE ARREGLOS. ......................................................... 27 FIGURA 10.17. ELEMENTO ORIENTADO, CON PESO. ..................................................................................... 29 FIGURA 10.18. GRAFO ORIENTADO. ............................................................................................................ 32 FIGURA 10.19. RBOL DE TRAYECTORIAS DFS. ......................................................................................... 33 FIGURA 10.19A. RBOL DE TRAYECTORIAS BFS. ....................................................................................... 33 FIGURA 10.20. DISTANCIAS EN ALGORITMO DE DIJKSTRA. ......................................................................... 34 FIGURA 10.21. SPT, RAZ 2. ........................................................................................................................ 36 FIGURA 10.22. SPT, RAZ 0. ........................................................................................................................ 36