Composente connexes d'un graphe

Télécharger le projet
Commenter

Description

le programme cré un graphe modelisé sous une matrice de 1 et 0 en suite il separe les composentes connexes de ce graphe

Source / Exemple : 


#include<stdio.h>
#include<conio.h>
int i,j,n;
main()
{
int m[20][20],t[20],s,k,nb;
	 printf("    ===========================================================\n");
	 printf("                     UNIVERSITE DE BEJAIA\n ");
	 printf("                   DEPARTEMENT D'INFORMATIQUE \n ");
	 printf("            ETUDIANT : TOUATI MOHAMED  \n ");
	 printf("               MODULE DE RECHERCHE OPERATIONNELLE\n");
	 printf("   ===========================================================\n");
	 printf("                             ***bonjour***\n\n");
	  printf("ceTP permet de separer les composentes connexes d'un graphe\n");
	  printf("TAPPEZ SUR UNE TOUCHE POUR COMMENCER LES MANIPULATIONS :\n\n\n");
	  getch();
	  clrscr();
	 printf("    ===========================================================\n");

	 printf("                     UNIVERSITE DE BEJAIA\n ");
	 printf("                   DEPARTEMENT D'INFORMATIQUE \n ");
	 printf("            ETUDIANT : TOUATI MOHAMED \n ");
	 printf("               MODULE DE RECHERCHE OPERATIONNELLE\n");
	 printf("   ===========================================================\n\n");
printf("introduire n le nombre de sommets\n\n n=");
scanf("%d",&n);
printf("introduire la matrice\n\n");
		  for(i=1;i<=n;i++)
			  {
				for(j=1;j<=n;j++)
					{
						ref:
						printf("M(%d,%d)=",i,j);
						scanf("%d",&s);
						if (s!=0&&s!=1)
							{
							 printf("erroné!!\a\n\n");
							  goto ref;
							}
							else
							m[i][j]=s;
					}
			  }
			  //affichage de la matrice
		  printf("affichage de la matrice :\n");
	  for(i=1;i<=n;i++)
	  {
	  for(j=1;j<=n;j++)
	  {
	  printf("    %d        ",m[i][j]);

	  }
	  printf("\n\n\n");
	  }
	  ///intialiser le tableau T

	  for(i=1;i<=n;i++)
	  t[i]=0;

	  ///le marcage dans le tableaux
		k=0;
	  for(i=1;i<=n;i++)
	  {
			for(j=1;j<=n;j++)
			{
			if (t[i]==0)
				{
				 k=k+1;
				 t[i]=k;
				}

			if(m[i][j]==1||m[j][i]==1)
			t[j]=t[i];
			}

	  }
  for(i=1;i<=n;i++)
  printf("%d   ",t[i]);
  //le nembre de composente connexe
  nb=t[1];
  for(i=1;i<=n;i++)
  {
  if(t[i]>nb)
  nb=t[i];
  }
  /////////

  printf("\n\n");
  printf("le nembre de composnetes connexe est :  %d",nb);
 //affichage des compsente connexe
  printf("\n\n");
  for(i=1;i<=nb;i++)
		{
			printf("la composnete connexe N°%d ={",i);
			  for(j=1;j<=n;j++)
			 {
			 if(t[j]==i)
			 printf("%d,",j);

			 }
			 printf("\b}\n");
  }

}

Conclusion :


université de bejaia
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (mohtouati)