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

matIncidenza.c

 Caricato da: Bonny
Scarica il programma completo

  1. /*implementazione di un grafo mediante matrice di incidenza*/
  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 5
  9. #define col 8
  10.  
  11. typedef int matrice_incidenza[row][col];
  12. typedef matrice_incidenza grafo;
  13. typedef int nodo;
  14. typedef int arco;
  15.  
  16. void BFS(grafo, nodo, int[]);
  17. void DFS(grafo, nodo, int[]);
  18. void adiacenza(grafo, nodo);
  19. int BIPARTITO(grafo, nodo, int[]);
  20. int COMP_CONNESSE(grafo, int);
  21. int BIPARTITO(grafo, nodo, int[]);
  22. void DFS_CONNESSE(grafo, nodo, int, int[]);
  23. void reset(int[]);
  24.  
  25. int main() {
  26.  
  27.     grafo g = {
  28.         /*    0     1     2     3     4     5     6     7*/
  29.         /*  (0,1) (0,2) (1,2) (1,3) (2,4) (3,0) (3,4) (4,1) */
  30.         /*0*/{-1,  -1,    0,    0,    0,    1,    0,    0},
  31.         /*1*/{1,    0,   -1,   -1,    0,    0,    0,    1},
  32.         /*2*/{0,    1,    1,    0,   -1,    0,    0,    0},
  33.         /*3*/{0,    0,    0,    1,    0,   -1,   -1,    0},
  34.         /*4*/{0,    0,    0,    0,    1,    0,    1,   -1}
  35.     };
  36.  
  37.     int vivitato[row], colore[row];
  38.     reset(vivitato);
  39.     printf("\n\n visita DFS partendo dal nodo 2:\n");
  40.     DFS(g,2,vivitato);
  41.     reset(vivitato);
  42.     printf("\n visita DFS partendo dal nodo 1:\n");
  43.     BFS(g,1,vivitato);
  44.     reset(colore);
  45.     if(BIPARTITO(g,1,colore))printf("\nIl grafo è bipartito");
  46.     else printf("\nIl grafo non è bipartito");
  47.  
  48.     printf("\nIl grafo ha %d componenti connesse\n",COMP_CONNESSE(g,row));
  49.     return 0;
  50. }
  51.  
  52. int BIPARTITO(grafo G, nodo r, int colore[]) {
  53.     int flag, bipartito = 1;
  54.     arco e;
  55.     nodo u, v;
  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.         /* per ogni arco */
  63.         for (e = 0; e < col; e++) {
  64.             /* uscente da u */
  65.             if (G[u][e] == -1) {
  66.                 v = 0;
  67.                 flag = 0;
  68.                 while (v < row && !flag) {
  69.                     /*se v appartiene a A(u) e non è stato visitato*/
  70.                     if (G[v][e] == 1) {
  71.                         if (colore[v] == BIANCO) {
  72.                             colore[v] = (colore[u] == ROSSO) ? VERDE : ROSSO;
  73.                             INCODA(v, Q);
  74.                         } else {
  75.                             if (colore[u] == colore[v]) {
  76.                                 bipartito = 0;
  77.                             }
  78.                         }
  79.                     }
  80.                     v++;
  81.                 }
  82.             }
  83.         }
  84.     }
  85.     return bipartito;
  86. }
  87.  
  88. int COMP_CONNESSE(grafo G, int n) {
  89.     int i;
  90.     int numComp = 0;
  91.     int comp[n];
  92.     for (i = 0; i < row; i++) {
  93.         comp[i] = 0;
  94.     }
  95.     for (i = 0; i < n; i++) {
  96.         if (comp[i] == 0) {
  97.             numComp++;
  98.             DFS_CONNESSE(G, i, numComp, comp);
  99.         }
  100.     }
  101.     return numComp;
  102. }
  103.  
  104. void DFS_CONNESSE(grafo G, nodo u, int numComp, int comp[]) {
  105.     arco e;
  106.     nodo v;
  107.     int flag;
  108.     comp[u] = numComp;
  109.     /* per ogni arco */
  110.     for (e = 0; e < col; e++) {
  111.         /* uscente da u */
  112.         if (G[u][e] == -1) {
  113.             v = 0;
  114.             flag = 0;
  115.             while (v < row && !flag) {
  116.                 /*se v appartiene a A(u) e non è stato visitato*/
  117.                 if (G[v][e] == 1) {
  118.                     if (comp[v] == 0) {
  119.                         DFS_CONNESSE(G, v, numComp, comp);
  120.                         flag = 1;
  121.                     }
  122.                 }
  123.                 v++;
  124.             }
  125.         }
  126.     }
  127. }
  128.  
  129. void DFS(grafo G, nodo u, int visitato[]) {
  130.     arco e;
  131.     nodo v;
  132.     int flag;
  133.     visitato[u] = 1;
  134.     printf("%d\t", u);
  135.     /* per ogni arco */
  136.     for (e = 0; e < col; e++) {
  137.         /* uscente da u */
  138.         if (G[u][e] == -1) {
  139.             v = 0;
  140.             flag = 0;
  141.             while (v < row && !flag) {
  142.                 /*se v appartiene a A(u) e non è stato visitato*/
  143.                 if (G[v][e] == 1) {
  144.                     if (!visitato[v]) {
  145.                         DFS(G, v, visitato);
  146.                         flag = 1;
  147.                     }
  148.                 }
  149.                 v++;
  150.             }
  151.         }
  152.     }
  153. }
  154.  
  155. void BFS(grafo G, nodo r, int visitati[]) {
  156.     int flag;
  157.     arco e;
  158.     nodo u, v;
  159.     coda Q = CREACODA();
  160.     INCODA(r, Q);
  161.     while (!CODAVUOTA(Q)) {
  162.         u = LEGGICODA(Q);
  163.         FUORICODA(Q);
  164.         visitati[u] = 1;
  165.         printf("%d\t", u);
  166.         /* per ogni arco */
  167.         for (e = 0; e < col; e++) {
  168.             /* uscente da u */
  169.             if (G[u][e] == -1) {
  170.                 v = 0;
  171.                 flag = 0;
  172.                 while (v < row && !flag) {
  173.                     /*se v appartiene a A(u) e non è stato visitato*/
  174.                     if (G[v][e] == 1) {
  175.                         if (!visitati[v] && !APPARTCODA(v, Q)) {
  176.                             INCODA(v, Q);
  177.                             flag = 1;
  178.                         }
  179.                     }
  180.                     v++;
  181.                 }
  182.             }
  183.         }
  184.     }
  185. }
  186.  
  187. void adiacenza(grafo G, nodo u) {
  188.     int flag;
  189.     arco e;
  190.     nodo v;
  191.     for (e = 0; e < col; e++) {
  192.         if (G[u][e] == -1) {
  193.             v = 0;
  194.             flag = 0;
  195.             while (v < row && !flag) {
  196.                 if (G[v][e] == 1) {
  197.                     printf("(%d)---%d--->(%d)\n", u, e, v);
  198.                     flag = 1;
  199.                 }
  200.                 v++;
  201.             }
  202.         }
  203.     }
  204. }
  205.  
  206. void reset(int v[]) {
  207.     int i;
  208.     for (i = 0; i < row; i++) {
  209.         v[i] = 0;
  210.     }
  211. }