VISITEDIGRAFI_1_SvoltiACasa_Correggi

//ESERCIZI SU VISITE DI GRAFI PROVATI DA ME

GRAFO-CONNESSO(A){
for(i=0 to A.lenght-1)
    color[i] = 0;
BFS(A,v, color);
for(i=0 to A.lenght-1)
    if(coloro[i]==0);
        return FALSE
return TRUE
}
BFS(A,i, color)
    color[i] = 1
    x = A[i];
    while(x!=NULL)
        k = x.key;
        if(k==0)
            BFS(A,k, color);
        x = x.next;
    color[i] = 2;
____________________________________________________________________________________________________________________________
STESSA-COMPONENTE-FORTEMENTE-CONNESSA(A, u,v) ------------chiedi se giusta---------------
for(i=0 to A.lenght-1)
    color[i] =0;
for(i=0 to A.lenght-1){
    if(color[i]==0){
        cont++;
        BFS(A,k, color, cont);
        }
}
primoGiaTrovato=FALSE;
for(i=0 to color.lenght-1){
    if(i=u)
        Appartenente = color[i]
}
for(i=0 to color-lenght-1)
    if(i=v && color[i] = appartenente)
        return TRUE;
return FALSE;

________________________________________________________________________________________________________________________
COMPONENTI-CONNESSE(A)
    for(i=0 to A.lenght-1)
        color[i] = 0;
    cont = COMPONENTI-CONNESSE-RIC(A, v, color)
    return cont;

COMPONENTI-CONNESSE-RIC(A, v, color){
    for(i=0 to A.lenght-1){
        if(color[i]==0){
            cont++;
            DFS(A, i, color);
        }
    }
return cont;
/*si può fare più semplice ovviamente, senza sta cosa ricorsiva*/

/*se volessi calcolare le componenti connesse con una certa proprietà p, ad esempio il numero delle componenti connesse che hanno tre nodi, che sono dei cicli, che sono degli alberi, o che hanno tanti nodi quanti archi. il contatore viene incrementato prima del lancio della dfs, se in fondo gli passo anche cont alla dfs, posso modificare la dfs in modo che quando visita la prima volta marca tutto con 1, la seocnda visita marca con cont con 2, poi con 3 4, dentro color non solo ho l'infomrazione dei nodi, ma anche in quale visita li ho visitati, se li ho effettuati nella prima visita, faranno parte della prima componente connesse, o della seconda.

_______________________________________________________________________________________________________

GRAFO-CONNESSO-CONPROPRIETA'(A)
for(i=0 to A.lenght-1){
    color[i] =0;
// cont è una nuova variabile
for(i=0 to A.lenght-1)
    if(color[i]==0){
        cont++;
        DFS(A, i, color, cont)
    }
}

/*Stampo il numero medio di nodi di ogni componente connessa*/
// C è un array di dimensione cont
for i=0 to cont{
    for(i=0 to color.lenght-1){
        if(color[i] == cont)
            cont2++;
    }
    if(cont2==10)
        return TRUE;
}

DFS(A, v, color, cont)
    color[i] = cont;
    x = A[i]
    while(x!=NULL)
        k = x.info;
        if(color[k]==0)
            DFS(A, k, color, cont)

    }
}

_________________________________________________________________________________________________
ALBERO-RICOPRENTE(A, u)
    for(i=0 to A.lenght-1){
        color[i]=0;
        parent[i] = -1
    }
    DFS(A, u, color, u, parent)  //u è un qualsiasi indice di partenza
    return parent;
}

DFS(A, v, color, u, parent) //v è la nuovo indice del nodo, u è l'indice del nodo da cui provengo.
    parent[v] = u;
    color[v] = 1;
    x = A[v];
    while(x!=NULL)
        k = x.info;
        if(color[k] ==0)
            DFS(A, k, color, v, parent);
        x = x.next;
    color[v] = 2;

VARIANTE
//confronta il campo info di u con quello di k, se k è maggiore sistema il nodo a sinistra dell'albero, se ora setto l'albero con questo nuovo nodo, ed entro nella bfs con questo nodo.

ALBERO-RICOPRENTE-CON-ALBERO(A,u){-----------------------E' tutto sbagliato-------------------
    for(i=0 to A.lengh-1)
        color[i] = 0;
    ADD-NODO(T, A[u].info)
    BFS(A, u, color, T)
}

BFS-ALBERO(A, u, color, T){
    color[u] = 1
    x = A[u]
    while(x!=NULL)
        k = x.info;
        if(k==0){
            if(k>u){
                ADD-Nodo(T.sx, k, u);
                BFS-ALBERO(A, k, color, T.sx);
            }
            else{
                ADD-NODO(T.dx, k, u);
                BFS-ALBERO(A, k, color, T.dx)
            }
}

ADD-NODO(T, k, parent){
    //x è un nuovo nodo.
    x.left = NULL;
    x.right=NULL;
    x.info = k;
    T = x;
}

___________________________________________________________________________________________________________________

DFS(A,v)
for(i=0 to A.lenght-1)
    color[i]=0;
//Ordine è un nuovo array di dimensione A.lenght ------------------qui dovrei inizializzare l'array a valori -1
DFS-ORDINE(A, u, color, ordine, 0)
return ordine;

DFS-ORDINE(A, u, color, ordine, c)
    ordine[u] = c;
    color[i]=1;
    x = A[u];
    while(x!=NULL)
        k = x.key;
        if(k==0)
            DFS(A, k, color, ordine, c+1);
        x = x.next;
    color[u] = 2;