C/C++ - inserire valori matrice in un grafo per verificare componente connessa

Forum - C/C++ - inserire valori matrice in un grafo per verificare componente connessa

garfa (Normal User)
Newbie

Messaggi: 1
Iscritto: 07/07/2009

Postato alle 15:57
Martedì, 07/07/2009

Io ho una matrice allocata dinamicamente in cui inserisco i valori letti in input:

Codice sorgente - presumibilmente C++

/* struttura per il valore della matrice */
typedef struct CELLA{
  int valore;      /* contiene il valore della cella */
  int marcatura;   /* colore che assume la cella :assume il valore 0=non si sa ancora;   1=non annerito;   2=annerito */
  int key;
  struct CELLA *next; 
}CELLA;
 
/*
  Alloca la memoria per una matrice di struct CELLA di dimensione n e ne restituisce
  un puntatore.
 */
CELLA** alloca_matrice(int n)
{
  CELLA **matrice;
  int i;
 
  /* alloco un array di n puntatori alla struttra CELLA e assegno il puntatore a una varibile matrice di tipo CELLA **  */
  if(!(matrice = (CELLA **) malloc (n * sizeof(CELLA*)))) {
                fprintf(stderr,"Errore di allocazione per la matrice\n");
                return 0;
        }
 
 /* per ogni elemento matrice[i] dell'array si alloca un array di n elementi di tipo CELLA il cui indirizzo viene posto in matrice[i] */
  for(i=0; i<n; i++) {
    if(!(matrice[i] = (CELLA*) malloc (n * sizeof(CELLA)))) {
                fprintf(stderr,"Errore di allocazione per la i-esima posizione \"%d\"\n",i);
                return 0;
                }
   }
  return matrice;
}

esempio inserisco questi valori

1 1 1 2 3
5 4 2 3 1
1 5 3 4 3
2 4 4 1 4
1 2 1 5 4

se a un certo punto sò che i due 1 in grassetto sarebbero anneriti
devo fare in modo di riconoscere che il 4 sottolineato non può essere annerito perchè devo rispettare la regola di non chiudere dei valori con celle in grassetto(cioè annerite), infatti l'1 sottolineato rimarebbe chiuso

devo utilizzare un grafo con una visita in ampiezza o ci sono altri metodi???

Codice sorgente - presumibilmente Plain Text