Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Collezione esempi Grafi - listeAdiacenza.c

listeAdiacenza.c

 Caricato da: Bonny
Scarica il programma completo

  1. /*implementazione di un grafo mediante liste di adiacenza*/
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include "myLib.h"
  5. #define dim 6
  6. #define BIANCO 0
  7. #define ROSSO 1
  8. #define VERDE 2
  9. typedef int nodo;
  10. typedef struct struct_grafo *grafo;
  11.  
  12. struct struct_grafo {
  13.     lista A[dim];
  14.     nodo visit[dim];
  15.     int comp[dim];
  16.     int colore[dim];
  17. };
  18. typedef int tree[dim];
  19.  
  20. void BFS(grafo, nodo);
  21. void DFS(grafo, nodo);
  22. int COMP_CONNESSE(grafo, int);
  23. void DFS_CONNESSE(grafo, nodo, int);
  24. void ALBERO_DFS(grafo, nodo, tree, nodo);
  25. void adiacenza(grafo, nodo);
  26. grafo creaGrafo();
  27. void addArco(grafo, nodo, nodo);
  28. void reset(grafo);
  29. int BIPARTITO(grafo, nodo);
  30.  
  31. int main() {
  32.  
  33.     grafo g = creaGrafo();
  34.  
  35.     addArco(g, 0, 1);
  36.     addArco(g, 0, 3);
  37.  
  38.     addArco(g, 1, 0);
  39.     addArco(g, 1, 4);
  40.     addArco(g, 1, 5);
  41.     addArco(g, 1, 2);
  42.  
  43.     addArco(g, 2, 4);
  44.     addArco(g, 2, 3);
  45.     addArco(g, 2, 5);
  46.     addArco(g, 2, 1);
  47.  
  48.     addArco(g, 3, 2);
  49.     addArco(g, 3, 0);
  50.     addArco(g, 3, 4);
  51.  
  52.     addArco(g, 4, 3);
  53.     addArco(g, 4, 0);
  54.     addArco(g, 4, 1);
  55.  
  56.     addArco(g, 5, 1);
  57.     addArco(g, 5, 2);
  58.     reset(g);
  59.     tree T;
  60.     ALBERO_DFS(g, 3, T, -1);
  61.     int i;
  62.     printf("Albero di copertura del grafo:\n");
  63.     for (i = 0; i < dim; i++)printf("%d\t", T[i]);
  64.     reset(g);
  65.     printf("\n visita DFS partendo dal nodo 2:\n");
  66.     DFS(g,2);
  67.     reset(g);
  68.     printf("\n visita DFS partendo dal nodo 1:\n");
  69.     BFS(g,1);
  70.     reset(g);
  71.     if(BIPARTITO(g,1))printf("\nIl grafo è bipartito");
  72.     else printf("\nIl grafo non è bipartito");
  73.  
  74.     printf("\nIl grafo ha %d componenti connesse\n",COMP_CONNESSE(g,dim));
  75.  
  76.     return 0;
  77. }
  78.  
  79. int BIPARTITO(grafo G, nodo r) {
  80.     nodo v, u;
  81.     int bipartito = 1;
  82.     lista L;
  83.     posizione p;
  84.     coda Q = CREACODA();
  85.     INCODA(r, Q);
  86.     G->colore[r] = ROSSO;
  87.     while (!CODAVUOTA(Q) && bipartito) {
  88.         u = LEGGICODA(Q);
  89.         FUORICODA(Q);
  90.         L = G->A[u];
  91.         p = PRIMOLISTA(L);
  92.         while (!FINELISTA(p, L)) {
  93.             v = LEGGILISTA(p);
  94.             if (G->colore[v] == BIANCO) {
  95.                 G->colore[v] = (G->colore[u] == ROSSO) ? VERDE : ROSSO;
  96.                 INCODA(v, Q);
  97.             } else {
  98.                 if (G->colore[u] == G->colore[v]) {
  99.                     bipartito = 0;
  100.                 }
  101.             }
  102.             p = SUCCLISTA(p);
  103.         }
  104.     }
  105.     return bipartito;
  106. }
  107. /*traminte una visita DFS del grafo si crea l'albero di copertura del grafo
  108.  albero implementato tramite vettore dei padri
  109.  */
  110. void ALBERO_DFS(grafo G, nodo u, tree T, nodo padre) {
  111.     nodo v;
  112.     /*marca u come visitato*/
  113.     G->visit[u] = 1;
  114.     T[u] = padre;
  115.     lista L = G->A[u];
  116.     posizione p = PRIMOLISTA(L);
  117.     /*per ogni v appartenente a A(u) */
  118.     while (!FINELISTA(p, L)) {
  119.         v = LEGGILISTA(p);
  120.         /*se v non è stato visitato */
  121.         if (!G->visit[v]) {
  122.             ALBERO_DFS(G, v, T, u);
  123.         }
  124.         p = SUCCLISTA(p);
  125.     }
  126. }
  127.  
  128. /*calcola il numero di componenti connesse del grafo*/
  129. int COMP_CONNESSE(grafo G, int n) {
  130.     int i;
  131.     int numComp = 0;
  132.     for (i = 0; i < n; i++) {
  133.         G->comp[i] = 0;
  134.     }
  135.     for (i = 0; i < n; i++) {
  136.         if (G->comp[i] == 0) {
  137.             numComp++;
  138.             DFS_CONNESSE(G, i, numComp);
  139.         }
  140.     }
  141.     return numComp;
  142. }
  143.  
  144. /*visita DFS per la ricerca delle componenti connesse*/
  145. void DFS_CONNESSE(grafo G, nodo u, int numComp) {
  146.     nodo v;
  147.     G->comp[u] = numComp;
  148.     lista L = G->A[u];
  149.     posizione p = PRIMOLISTA(L);
  150.     while (!FINELISTA(p, L)) {
  151.         v = LEGGILISTA(p);
  152.         if (G->comp[v] == 0) {
  153.             DFS_CONNESSE(G, v, numComp);
  154.         }
  155.         p = SUCCLISTA(p);
  156.     }
  157. }
  158.  
  159. /* visita DFS */
  160. void DFS(grafo G, nodo u) {
  161.     nodo v;
  162.     G->visit[u] = 1; /*marca u come visitato*/
  163.     printf("(%d)\t", u);
  164.     lista L = G->A[u];
  165.     posizione p = PRIMOLISTA(L);
  166.     while (!FINELISTA(p, L)) {/*per ogni v appartenente a A(u) */
  167.         v = LEGGILISTA(p);
  168.         /*se v non è stato visitato */
  169.         if (!G->visit[v]) {
  170.             DFS(G, v);
  171.         }
  172.         p = SUCCLISTA(p);
  173.     }
  174. }
  175.  
  176. /* visita BFS */
  177. void BFS(grafo G, nodo r) {
  178.     lista L;
  179.     posizione p;
  180.     nodo v;
  181.     nodo u;
  182.     coda Q = CREACODA();
  183.     INCODA(r, Q);
  184.     while (!CODAVUOTA(Q)) {
  185.         v = LEGGICODA(Q);
  186.         FUORICODA(Q);
  187.         G->visit[v] = 1;
  188.         printf("%d\t", v);
  189.         L = G->A[v];
  190.         p = PRIMOLISTA(L);
  191.         while (!FINELISTA(p, L)) {
  192.             u = LEGGILISTA(p);
  193.             if (!G->visit[u] && !APPARTCODA(u, Q)) {
  194.                 INCODA(u, Q);
  195.             }
  196.             p = SUCCLISTA(p);
  197.         }
  198.     }
  199. }
  200.  
  201. void addArco(grafo G, nodo par, nodo arr) {
  202.     lista L = G->A[par];
  203.     posizione p = PRIMOLISTA(L);
  204.     INLISTA(arr, &p);
  205. }
  206.  
  207. /* visualizza insieme di adiacenza di un nodo */
  208. void adiacenza(grafo G, nodo u) {
  209.     lista L;
  210.     posizione p;
  211.     nodo v;
  212.     L = G->A[u];
  213.     p = PRIMOLISTA(L);
  214.     while (!FINELISTA(p, L)) {
  215.         v = LEGGILISTA(p);
  216.         printf("(%d)---->(%d)\n", u, v);
  217.         p = SUCCLISTA(p);
  218.     }
  219. }
  220.  
  221. grafo creaGrafo() {
  222.     grafo G = malloc(sizeof (struct struct_grafo));
  223.     nodo i;
  224.     for (i = 0; i < dim; i++) {
  225.         G->A[i] = CREALISTA();
  226.         G->visit[i] = 0;
  227.         G->colore[i] = BIANCO;
  228.         G->comp[i] = 0;
  229.     }
  230. }
  231.  
  232. void reset(grafo G) {
  233.     nodo i;
  234.     for (i = 0; i < dim; i++) {
  235.         G->visit[i] = 0;
  236.         G->colore[i] = BIANCO;
  237.         G->comp[i] = 0;
  238.     }
  239. }