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 - matAdiacenza.c

matAdiacenza.c

 Caricato da: Bonny
Scarica il programma completo

  1. /*implementazione di un grafo mediante matrice di adiacenza*/
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include "myLib.h"
  5. #define BIANCO 0
  6. #define ROSSO 1
  7. #define VERDE 2
  8. #define row 7
  9. #define col 7 /* matrice quadrata */
  10. typedef int matrice_adiacenza[row][col];
  11. typedef matrice_adiacenza grafo;
  12. typedef int nodo;
  13.  
  14. int BIPARTITO(grafo, nodo, int[]);
  15. void BFS(grafo, nodo, int[]);
  16. void DFS(grafo, nodo, int[]);
  17. int COMP_CONNESSE(grafo, int);
  18. void DFS_CONNESSE(grafo, nodo, int, int[]);
  19. void adiacenza(grafo, nodo);
  20. void stampa(matrice_adiacenza);
  21. void reset(int[]);
  22.  
  23. int main() {
  24.  
  25.     grafo g = {
  26.            /* 0  1  2  3  4  5  6 */
  27.         /*0*/{0, 1, 0, 1, 0, 0, 0},
  28.         /*1*/{1, 0, 1, 0, 1, 1, 0},
  29.         /*2*/{0, 1, 0, 1, 1, 1, 0},
  30.         /*3*/{1, 0, 1, 0, 1, 0, 0},
  31.         /*4*/{0, 1, 1, 1, 0, 0, 0},
  32.         /*5*/{0, 1, 1, 0, 0, 0, 0},
  33.         /*6*/{0, 0, 0, 0, 0, 0, 0} /* 6 componente non connessa*/
  34.     };
  35.  
  36.     stampa(g);
  37.  
  38.     int vivitato[row], colore[row];
  39.  
  40.     printf("\n\n visita DFS partendo dal nodo 2:\n");
  41.     DFS(g,2,vivitato);
  42.     reset(vivitato);
  43.     printf("\n visita DFS partendo dal nodo 1:\n");
  44.     BFS(g,1,vivitato);
  45.     reset(colore);
  46.     if(BIPARTITO(g,1,colore))printf("\nIl grafo è bipartito");
  47.     else printf("\nIl grafo non è bipartito");
  48.  
  49.     printf("\nIl grafo ha %d componenti connesse\n",COMP_CONNESSE(g,row));
  50.     return 0;
  51. }
  52.  
  53. int BIPARTITO(grafo G, nodo r, int colore[]) {
  54.     nodo v, u;
  55.     int bipartito = 1;
  56.     coda Q = CREACODA();
  57.     INCODA(r, Q);
  58.     colore[r] = ROSSO;
  59.     while (!CODAVUOTA(Q) && bipartito) {
  60.         u = LEGGICODA(Q);
  61.         FUORICODA(Q);
  62.         for (v = 0; v < col; v++) {
  63.             if (G[u][v] == 1) {
  64.                 if (colore[v] == BIANCO) {
  65.                     colore[v] = (colore[u] == ROSSO) ? VERDE : ROSSO;
  66.                     INCODA(v, Q);
  67.                 } else {
  68.                     if (colore[u] == colore[v]) {
  69.                         bipartito = 0;
  70.                     }
  71.                 }
  72.             }
  73.         }
  74.     }
  75.     return bipartito;
  76. }
  77.  
  78. int COMP_CONNESSE(grafo G, int n) {
  79.     int i;
  80.     int numComp = 0;
  81.     int comp[n];
  82.     for (i = 0; i < n; i++) {
  83.         comp[i] = 0;
  84.     }
  85.     for (i = 0; i < n; i++) {
  86.  
  87.         if (comp[i] == 0) {
  88.             numComp++;
  89.             DFS_CONNESSE(G, i, numComp, comp);
  90.         }
  91.     }
  92.     return numComp;
  93. }
  94.  
  95. void DFS_CONNESSE(grafo G, nodo u, int numComp, int comp[]) {
  96.     nodo v;
  97.     comp[u] = numComp;
  98.     for (v = 0; v < col; v++) {
  99.         if (G[u][v] == 1) {
  100.             if (comp[v] == 0) {
  101.                 DFS_CONNESSE(G, v, numComp, comp);
  102.             }
  103.         }
  104.     }
  105. }
  106.  
  107. void DFS(grafo G, nodo u, int visitati[]) {
  108.     nodo v;
  109.     visitati[u] = 1;
  110.     printf("%d\t", u);
  111.     for (v = 0; v < col; v++) {
  112.         if (G[u][v] == 1) {
  113.             if (!visitati[v]) {
  114.                 DFS(G, v, visitati);
  115.             }
  116.         }
  117.     }
  118. }
  119.  
  120. void BFS(grafo G, nodo r, int visitati[]) {
  121.     nodo v;
  122.     nodo u;
  123.     coda Q = CREACODA();
  124.     INCODA(r, Q);
  125.     while (!CODAVUOTA(Q)) {
  126.         u = LEGGICODA(Q);
  127.         FUORICODA(Q);
  128.         visitati[u] = 1;
  129.         printf("%d\t", u);
  130.         for (v = 0; v < col; v++) {
  131.             if (G[u][v] == 1) {
  132.                 if (!visitati[v] && !APPARTCODA(v, Q)) {
  133.                     INCODA(v, Q);
  134.                 }
  135.             }
  136.         }
  137.     }
  138. }
  139.  
  140. void adiacenza(grafo G, nodo u) {
  141.     nodo v;
  142.     for (v = 0; v < col; v++) {
  143.         if (G[u][v] == 1) {
  144.             printf("(%d)---->(%d)\n", u, v);
  145.         }
  146.     }
  147. }
  148.  
  149. void stampa(matrice_adiacenza M) {
  150.     int i, j;
  151.     for (i = 0; i < row; i++) {
  152.         for (j = 0; j < col; j++) {
  153.             printf("%d\t", M[i][j]);
  154.             if (j == col - 1)printf("\n");
  155.         }
  156.     }
  157. }
  158.  
  159. void reset(int v[]) {
  160.     int i;
  161.     for (i = 0; i < row; i++) {
  162.         v[i] = 0;
  163.     }
  164. }