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

vettoreAdiacenza.c

 Caricato da: Bonny
Scarica il programma completo

  1. /*implementazione di un grafo mediante vettore di adiacenza*/
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include "myLib.h"
  5. #define N 6
  6. #define A 18   
  7. #define BIANCO 0
  8. #define ROSSO 1
  9. #define VERDE 2
  10. typedef struct grafo_struct *grafo;
  11. typedef int nodo;
  12.  
  13. struct grafo_struct {
  14.     int nodi[N + 1];
  15.     int archi[A];
  16.     int visit[N];
  17.     int comp[N];
  18.     int inCoda[N];
  19.     int colore[N];
  20. };
  21. void BFS(grafo, nodo);
  22. void DFS(grafo, nodo);
  23. int COMP_CONNESSE(grafo, int);
  24. void DFS_CONNESSE(grafo, nodo, int);
  25. void stampa(grafo);
  26. void reset(grafo);
  27. void adiacenza(grafo, nodo);
  28. int BIPARTITO(grafo, nodo);
  29.  
  30. int main() {
  31.  
  32.     grafo G = malloc(sizeof (struct grafo_struct));
  33.  
  34.     int n[] = {0, 2, 6, 10, 13, 16, 18};
  35.     int a[] = {3, 1, 2, 5, 4, 0, 1, 5, 3, 4, 4, 0, 2, 1, 0, 3, 2, 1};
  36.     int i;
  37. // init to graph
  38.     for (i = 0; i < N + 1; i++) {
  39.         G->nodi[i] = n[i];
  40.     }
  41.     for (i = 0; i < A; i++) {
  42.         G->archi[i] = a[i];
  43.     }
  44.     for (i = 0; i < N; i++) {
  45.         G->visit[i] = 0;
  46.         G->inCoda[i] = 0;
  47.         G->colore[i] = BIANCO;
  48.     }
  49. //***********
  50.     stampa(G);
  51.     printf("\n visita DFS partendo dal nodo 2:\n");
  52.     DFS(G,2);
  53.     reset(G);
  54.     printf("\n visita DFS partendo dal nodo 1:\n");
  55.     BFS(G,1);
  56.     reset(G);
  57.     if(BIPARTITO(G,1))printf("\nIl grafo è bipartito");
  58.     else printf("\nIl grafo non è bipartito");
  59.  
  60.     printf("\nIl grafo ha %d componenti connesse\n",COMP_CONNESSE(G,N));
  61.     return 0;
  62. }
  63.  
  64. int BIPARTITO(grafo G, nodo r) {
  65.     nodo v, u;
  66.     int bipartito = 1;
  67.     int i;
  68.     coda Q = CREACODA();
  69.     INCODA(r, Q);
  70.     G->colore[r] = ROSSO;
  71.     while (!CODAVUOTA(Q) && bipartito) {
  72.         u = LEGGICODA(Q);
  73.         FUORICODA(Q);
  74.         for (i = G->nodi[u]; i < G->nodi[u + 1]; i++) {
  75.             v = G->archi[i];
  76.             if (G->colore[v] == BIANCO) {
  77.                 G->colore[v] = (G->colore[u] == ROSSO) ? VERDE : ROSSO;
  78.                 INCODA(v, Q);
  79.             } else {
  80.                 if (G->colore[u] == G->colore[v]) {
  81.                     bipartito = 0;
  82.                 }
  83.             }
  84.         }
  85.     }
  86.     return bipartito;
  87. }
  88.  
  89. /*calcola il numero di componenti connesse del grafo*/
  90. int COMP_CONNESSE(grafo G, int n) {
  91.     int i;
  92.     int numComp = 0;
  93.     for (i = 0; i < n; i++) {
  94.         G->comp[i] = 0;
  95.     }
  96.     for (i = 0; i < n; i++) {
  97.  
  98.         if (G->comp[i] == 0) {
  99.             numComp++;
  100.             DFS_CONNESSE(G, i, numComp);
  101.         }
  102.     }
  103.     return numComp;
  104. }
  105.  
  106. /*visita DFS per la ricerca delle componenti connesse*/
  107. void DFS_CONNESSE(grafo G, nodo u, int numComp) {
  108.     nodo v;
  109.     G->comp[u] = numComp;
  110.     int i;
  111.     for (i = G->nodi[u]; i < G->nodi[u + 1]; i++) {
  112.         v = G->archi[i];
  113.         if (G->comp[v] == 0) {
  114.             numComp++;
  115.             DFS_CONNESSE(G, v, numComp);
  116.         }
  117.     }
  118. }
  119.  
  120. void DFS(grafo G, nodo u) {
  121.     nodo v;
  122.     G->visit[u] = 1;
  123.     printf("(%d)\t", u);
  124.     int i;
  125.     for (i = G->nodi[u]; i < G->nodi[u + 1]; i++) {
  126.         v = G->archi[i];
  127.         if (!G->visit[v]) {
  128.             DFS(G, v);
  129.         }
  130.     }
  131. }
  132.  
  133. void BFS(grafo G, nodo r) {
  134.     nodo v, u;
  135.     int i;
  136.     coda Q = CREACODA();
  137.     INCODA(r, Q);
  138.     G->visit[r] = 1;
  139.     while (!CODAVUOTA(Q)) {
  140.         u = LEGGICODA(Q);
  141.         FUORICODA(Q);
  142.         G->visit[u] = 1;
  143.         printf("%d\t", u);
  144.         for (i = G->nodi[u]; i < G->nodi[u + 1]; i++) {
  145.             v = G->archi[i];
  146.             if (!G->visit[v] && !APPARTCODA(v, Q)) {
  147.                 INCODA(v, Q);
  148.             }
  149.         }
  150.     }
  151. }
  152.  
  153. void adiacenza(grafo G, nodo u) {
  154.     int i;
  155.     nodo v;
  156.     for (i = G->nodi[u]; i < G->nodi[u + 1]; i++) {
  157.         v = G->archi[i];
  158.         printf("(%d)---->(%d)\n", u, v);
  159.     }
  160. }
  161. //inizializza G->visit[i] = 0 dipo una visita(DFS/BFS) del grafo
  162.  
  163. void reset(grafo G) {
  164.     int i;
  165.     for (i = 0; i < N; i++) {
  166.         G->visit[i] = 0;
  167.     }
  168.     for (i = 0; i < N; i++) {
  169.         G->inCoda[i] = 0;
  170.     }
  171. }
  172.  
  173. void stampa(grafo G) {
  174.     int i;
  175.     printf("\n\n******** GRAFO ********\n\n* vettore nodi:\n\n");
  176.     for (i = 0; i < N + 1; i++) {
  177.         printf("%d\t", G->nodi[i]);
  178.     }
  179.     printf("\n\n* vettore archi:\n\n");
  180.     for (i = 0; i < A; i++) {
  181.         printf("%d\t", G->archi[i]);
  182.     }
  183.     printf("\n\n* vettore visit:\n\n");
  184.     for (i = 0; i < N; i++) {
  185.         printf("%d\t", G->visit[i]);
  186.     }
  187.     printf("\n\n* vettore inCoda:\n\n");
  188.     for (i = 0; i < N; i++) {
  189.         printf("%d\t", G->inCoda[i]);
  190.     }
  191.     printf("\n\n***********************\n");
  192. }