Enumération de tous les chemins dans un graphe

Commenter

Contenu du snippet

Voici un code en C permettant d'énumérer tous les chemins dans un graphe que certains pouuraient en avoir besoin pour leur manipulation en théorie des graphes.

Je n'en ai pas trouvé sur Internet, c'est pourquoi j'ai jugé opprtun de le mettre. Ilpourrait êyre utile en cas de génération de tous les plus courts chemins. Dans ce casd il suffit d'ajouter à la ligne de détrmination des successeurs d'un sommet la condition de DJXTRA.

Source / Exemple : 


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int i,k,g,f,adj[10][10];
FILE *fich;

roadmap(char chem[10],int ext,int destination)
{
	char s[10],m[1];
	int nod,j,suc[10];
	if (ext == destination) 
		fprintf(fich,"%s\n",chem);
	else
	{ 
		j=1;
		for (k=1;k<8;k++)
		{
			if (adj[ext][k]==1)
			{
				suc[j]= k;
				j++;
			}
		}
		for (nod=1;nod<j;nod++)
		{
			strcpy(s,chem);
			_itoa(suc[nod],m,10);
			strcat(s,m);
			roadmap(s, suc[nod], destination);
		}   
	}
}

main()
{	
	for (f=1;f<8;f++)
		for (g=1;g<8;g++)
			adj[f][g]=0;
	adj[1][2]=1;
	adj[1][7]=1;
	adj[2][3]=1;
	adj[3][4]=1;
	adj[2][4]=1;
	adj[2][6]=1;
	adj[4][5]=1;
	adj[5][6]=1;
	adj[7][6]=1;
	fich=fopen("c:\\phd\\roadmap.txt","w");
	roadmap("1",1,5);
	fclose(fich);
	return 0;
}

Conclusion :


J'ai pris un exemple d'un graphe à 7 noeuds numérotés de 1 à 7. adj[i][j] définit la matrice d'adjacence

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 (cs_osta)