/* Un graphe peut être décrit par la liste de ses arêtes. Il peut aussi être décrit en donnant pour chaque sommet la liste de ses voisins. On peut facilement passer d'une représentation à l'autre, par l'algorithme suivant qui a un temps de calcul en O(a+n) où a est le nombre d'arêtes et n le nombre de sommets. pour chacun des sommets s du graphe faire l(s)={} fait pour chacune des arêtes {s,t} du graphe faire l(s)=l(s)u{t} l(t)=l(t)u{s} fait Cet algorithme peut s'écrire en C de la manière suivante : Pour simplifier on supposera que les n sommets sont représentés par les nombres 0, 1, 2, ... , n-1. La représentation des graphes par la liste des arêtes utilise trois variables: int n; // le nombre de sommets int a; // le nombre d'arêtes int ar[2*a]; // les arêtes sont {ar[0],ar[1]}, {ar[2],ar[3]}, ... La représentation des graphes par liste d'adjacence utilise deux variables: int n; // le nombre de sommets lsom voisin[n]; // voisin[s] est la liste chaînée des sommets voisins du sommet s */ #include #include typedef struct chainon *lsom; struct chainon {lsom suite; int s;}; void setvoisin(int n, int a, int ar[2*a], // données qui représentent un graphe lsom voisin[n]) // résultat { int s,i; for(s=0;ssuite=voisin[x]; p->s=y; voisin[x]=p; p=malloc(sizeof(*p)); p->suite=voisin[y]; p->s=x; voisin[y]=p; } } /* on peut faire une version qui évite d'écrire deux fois l'insertion d'un élément dans une liste : */ void setvoisin2(int n, int a, int ar[2*a], // données qui représentent un graphe lsom voisin[n]) // résultat { int s,i; for(s=0;ssuite=voisin[x]; p->s=ar[i^1]; // autre extrémité de l'arête 12^1==13 13^1==12 voisin[x]=p; } } /* comptage des sommets isolés d'un graphe */ int nbsomisole(int n,lsom voisin[]) { int c=0, s; for(s=0;ssuite) { int t=p->s; if(cc[t]==inconnu) visite(t), pere[t]=s; } } int s; for(s=0;st du graphe faire succ(s)=succ(s)u{t} pred(t)=pred(t)u{s} fait Cet algorithme peut s'écrire en C de la manière suivante : */ void setpredsucc(int n, int a, int ar[2*a], // données qui représentent un graphe lsom pred[n], lsom succ[n]) // résultat { int s,i; for(s=0;ssuite=pred[y]; p->s=x; pred[y]=p; p=malloc(sizeof(*p)); p->suite=succ[x]; p->s=y; succ[x]=p; } } /* On fait d'abord un parcours en profondeur d'abord de l'ensemble du graphe, en prenant les sommets de départ dans un ordre quelconque. Puis on fait un deuxième parcours en profondeur d'abord, en prenant les arcs en sens inverse, et en partant des sommets dans l'ordre inverse où on a fini de les visiter lors du premier parcours en profondeur d'abord. Lors de ce deuxième parcours en profondeur d'abord, les groupes de sommets visités ensemble sont les composantes fortement connexes. Pour chaque sommet S, CFC[S] vaudra d'abord 0 tant qu'il n'a pas été rencontré, puis INCONNU entre les deux parcours, et enfin un numéro de composante fortement connexe positif ou nul. procedure chercheCFC(n, succ[n], pred[n] // données : un graphe var cfc[n], var nbcfc) // résultats local finvisite[n], i procedure visite_avant(s) cfc[s]=inconnu pour chacun des successeurs t de s faire si cfc[t] est nul alors visite_avant(t) finsi fait finvisite[i++]=s fin procedure visite_avant procedure visite_arrière(s) cfc[s]=nbcfc pour chacun des prédécesseurs t de s faire si cfc[t] est inconnu alors visite_arrière(t) finsi fait fin procedure visite_arrière pour tout sommet s faire cfc[s]=0 fait i=0 pour tout sommet s faire si cfc[s] est nul alors visite_avant(s) finsi fait nbcfc=0 pour i=n-1...0 faire s=finvisite[i] si cfc[s] est inconnu alors visite_arriere(s) nbcfc++ finsi fait fin procedure chercheCFC On a fait un "tri topologique" des composantes fortement connexes car pour toute arête s->t on cfc[s]<=cfc[t]. On peut traduire cet algorithme en C gnu de la manière suivante : */ int cherchecfc(int n, lsom pred[], lsom succ[], int cfc[]) { int finvisite[n],nbcfc=0,i=0; void avant(int s) { lsom p; cfc[s]=inconnu; for(p=succ[s];p;p=p->suite) if(!cfc[p->s]) avant(p->s); finvisite[i++]=s; } void arriere(int s) { lsom p; cfc[s]=nbcfc; for(p=pred[s];p;p=p->suite) if(cfc[p->s]==inconnu) arriere(p->s); } int s; for(s=0;s0) printf(" %d",*t++); } #define Aff(t,n) printf(#t" :"),afftint(t,n),printf("\n") /* Pour chercher un cycle dans un graphe on part d'un sommet qui a un successeur dans la même composante fortement connexe que lui, puis on avance dans le graphe en suivant les arcs du graphe mais en restant dans la même composante fortement connexe, jusqu'à ce qu'on repasse par un sommet déjà visité. */ void affboucle(int n, lsom succ[], int cfc[]) { int succmmcfc(int s) { lsom p; for(p=succ[s];p;p=p->suite) if(cfc[p->s]==cfc[s]) return p->s; return -1; } int vu[n], s,t; for(s=0;s",s),s=vu[s]; while(s!=t); printf("%d\n",s); } /* Au lieu de représenter les listes chaînées de sommets avec des pointeurs, on peut utiliser des tableaux. Un parcours de liste comme lsom p; for(p=succ[s];p;p=p->suite) if(!vu[p->s]) ... deviendra int p; for(p=succ[s];~p;p=suite[p]) if(!vu[ar[p]]) ... */ void setvoisinsuite(int n, int a, int ar [2*a], // données qui représentent un graphe int voisin[n],int suite[2*a]) // résultat { int s,i; for(s=0;sjp) for(p=succ[t=file[jp++]];~p;p=suite[p]) if(pere[u=ar[p]]<0) pere[file[ip++]=u]=t, dist[u]=dist[t]+1; } typedef struct{int n,a,*ar;} graphe; graphe g1(int n,int a) { int *ar=malloc(2*a*sizeof(int)), i,h,na=0; graphe g={n,a,ar}; for(h=1;h>1, ar[k++]=i+1, ar[k++]=i>>1; for(i=1;iy ssi x divise 3y+1 { int n=901, a=1442, *ar=malloc(2*a*sizeof(int)), x,xx,k=0; graphe g={n,a,ar}; for(x=100;x<=1000;++x) for(xx=x;xx<=3001;xx+=x) if(xx%3==1 && xx>300) ar[k++]=x-100, ar[k++]=xx/3-100; printf("a=%d k=%d\n",a,k); if(k!=2*a) exit(1); return g; } graphe g4() // x->y ssi 231 divise x^y { int n=2000, a=7808, *ar=malloc(2*a*sizeof(int)), x,xx,k=0; graphe g={n,a,ar}; for(x=0;x