begin process at 2012 05 27 14:46:30
  Trouver un code source :
 
dans
 
Accueil > 

Code

 > 

Maths & Algorithmes

 > COMPOSENTE CONNEXES D'UN GRAPHE

COMPOSENTE CONNEXES D'UN GRAPHE


 Information sur la source

Note :
Aucune note
Catégorie :Maths & Algorithmes Classé sous :recherche operationnelle, theorie graphe, composante connexe Niveau :Débutant Date de création :22/07/2008 Date de mise à jour :22/07/2008 10:45:14 Vu / téléchargé :7 189 / 418

Auteur : mohtouati

Ecrire un message privé
Commentaire sur cette source (2)
Ajouter un commentaire et/ou une note

 Description

Cliquez pour voir la capture en taille normale
le programme cré un graphe modelisé sous une matrice de 1 et 0 en suite il separe les composentes connexes de ce graphe

Source

  • #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");
  • }
  • }
#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

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Sources du même auteur

Source avec Zip ANALYSEUR LEXICAL POUR UN COMPILATEUR ALGORITHMIQUE
Source avec Zip ALGORITHME DE DJIKSTRA
Source avec Zip Source avec une capture LA FERMETURE TRANSITIVE
Source avec Zip LES ENCHÈRES

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel

 Sources en rapport avec celle ci

Source avec Zip ALGORITHME DE DJIKSTRA par mohtouati
Source avec Zip Source avec une capture LA FERMETURE TRANSITIVE par mohtouati

Commentaires et avis

Commentaire de sidouo le 11/12/2008 22:28:33

peux tu m'expliqué la methode ??

Commentaire de albert110 le 29/03/2010 13:41:24

ce programme ne marche pas, prenez des exo et vous verrez

 Ajouter un commentaire




Nos sponsors


Sondage...

Comparez les prix

CalendriCode

Mai 2012
LMMJVSD
 123456
78910111213
14151617181920
21222324252627
28293031   

Consulter la suite du CalendriCode

A découvrir



 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,640 sec (4)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales