Composente connexes d'un graphe

Soyez le premier à donner votre avis sur cette source.

Vue 9 986 fois - Téléchargée 572 fois

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

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
4
Date d'inscription
dimanche 17 mars 2013
Statut
Membre
Dernière intervention
27 mars 2013

merci
Messages postés
1
Date d'inscription
jeudi 3 janvier 2013
Statut
Membre
Dernière intervention
3 janvier 2013

merci
Messages postés
1
Date d'inscription
samedi 27 mars 2010
Statut
Membre
Dernière intervention
29 mars 2010

ce programme ne marche pas, prenez des exo et vous verrez
Messages postés
15
Date d'inscription
mercredi 11 juin 2008
Statut
Membre
Dernière intervention
31 mars 2010

peux tu m'expliqué la methode ??

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.