#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void distance(int matriceD[5][5],int s,int r){
s--;
int j;
if (s>4 || s<0){
printf("Il n'y a que 5 sommets dans le graphe et ils sont numérotés de 1 a 5 \n");
return;
}
for (j=0;j<5;j++){
if (matriceD[j] <= r && matriceD[j] != 0) printf("%d ",j+1);
}
}
void clear(bool visited[5]){
int i = 0;
for (i=0;i<5;i++){
visited = false;
}
}
bool parcours(int matrice[5][5],int s, bool visited[5]){
s--;
visited = true;
int j = 0;
if (s>4 || s<0){
printf("Il n'y a que 5 sommets dans le graphe et ils sont numérotés de 1 a 5 \n");
return false;
}
for (j=0;j<5;j++){
if (matrice[j] != 0 ){
if (!visited[j]){
visited[j] = true;
parcours(matrice,j+1,visited);
}
}
}
printf("%d ",s+1);
return false;
}
bool sourceInactive(int matriceD[5][5],int s){
int i = 0;
for (i=0;i<5;i++){
if (matriceD != 0) return false;
}
return true;
}
bool isUnreachable(int matrice[5][5],int s){
int i = 0;
for (i=0;i<5;i++){
if (matrice != 0) return false;
}
return true;
}
bool allVisited(int matrice[5][5], bool visited[5]){
int i = 0;
for (i=0;i<5;i++){
if (isUnreachable(matrice,i)) visited = true;
if (visited != true) return false;
}
return true;
}
bool chemin(int matrice[5][5],int s,int e,bool affichage,bool visited[5]){
// if (s == e){
//
// if (affichage){
// printf("%d",e);
// return true;
// }
//
// else return false;
// }
int temp = 0;
int i = 0;
s--;
e--;
if (s == e){
for (i=0;i<5;i++){
if (matrice != 0){
clear(visited);
temp = matrice;
matrice = 0;
if (chemin(matrice,i+1,s+1,0,visited)){
if (affichage) printf("%d ",s+1);
clear(visited);
if (affichage) chemin(matrice,i+1,s+1,1,visited);
return true;
}
else matrice = temp;
}
}
if (affichage) printf("Meme sommet de depart et d arrivee et aucun cyle partant du noeud : pas de chemin");
return false;
}
visited = true;
int k = 1;
int chemin[5] = {s+1,0,0,0,0};
if (s>4 || e>4 || e<0 || s<0){
if (affichage) printf("Il n'y a que 5 sommets dans le graphe et ils sont numérotés de 1 a 5 \n");
return false;
}
if (isUnreachable(matrice,e)){
if (affichage) printf("Pas de chemin : le noeud arrive est isole des autres noeuds du graphe\n");
return false;
}
if (sourceInactive(matrice,s)){
if (affichage) printf("Pas de chemin : la source n'est connectée à aucun noeud du graphe\n");
return false;
}
while (s != e){
if (matrice == 0 && i == 4){
s = chemin[k-2]-1;
i = chemin[k-1];
chemin[k-1] = 0;
k--;
visited[e] = true;
if (allVisited(matrice,visited)){
if (affichage) printf("Pas de chemin : tous les traces potentiels ont echoue ! \n");
return false;
}
else visited[e] = false;
}
if (matrice > 0 && visited == false){
chemin[k] = i+1;
k++;
s = i;
visited = true;
i = -1;
}
i++;
}
if (affichage){
k = 0;
while(k < 5 && chemin[k] != 0){
printf("%d ",chemin[k]);
k++;
}
}
return true;
}
bool hasCycle(int matriceND[5][5], bool visited[5]){
int nmbAretes = 0;
int i,j = 0;
for (i=0;i<5;i++){
for (j=0;j<5;j++){
if (matriceND[j] != 0)nmbAretes++;
}
}
nmbAretes = nmbAretes/2;
if (nmbAretes >= 5){
return true;
}
else {
for (i=0;i<5;i++){
if (chemin(matriceND,i+1,i+1,0,visited)){
return true;
}
}
}
return false;
}
void connexe(int matriceND[5][5], bool visited[5]){
bool chemins[5][5] = {{false}};
int max = 0;
bool posMax[5] = {0};
int temp = 0;
bool posTemp[5] = {0};
int i,j = 0;
for (i=0;i<5;i++){
for (j=0;j<5;j++){
if (i != j){
if (matriceND[j] != 0) chemins[j] = true;
else {
clear(visited);
if (chemin(matriceND,i+1,j+1,0,visited)){
chemins[j] = true;
}
}
}
}
}
for (i=0;i<5;i++){
for (j=0;j<5;j++){
if (chemins[j] !=0){
temp++;
posTemp[j] = true;
}
}
if (temp > max){
max = temp;
for (j=0;j<5;j++){
posMax[j] = posTemp[j];
}
}
temp = 0;
for (j=0;j<5;j++){
posTemp[j] = false;
}
}
printf("Le nombre de composantes connexe maximal est de %d \n",max);
printf("Et les sommets qui les composes en sont : ");
for (j=0;j<5;j++){
if (posMax[j]) printf("%d ",j+1);
}
}
int main() {
int matriceD [5][5] = {{0,0,0,0,0},
{0,0,0,5,0},
{0,4,0,9,0},
{0,0,0,0,0},
{0,0,0,0,0}};
int matriceND2 [5][5] = {{0,6,0,0,0},
{6,0,4,0,0},
{0,4,0,9,0},
{0,0,9,0,0},
{0,0,0,0,0}};
int matriceND [5][5] = {{0,6,0,1,0},
{6,0,4,0,0},
{0,4,0,9,0},
{1,0,9,0,0},
{0,0,0,0,0}};
int matriceND3 [5][5] = {{0,6,0,0,2},
{6,0,4,0,3},
{0,4,0,9,0},
{0,0,9,0,10},
{2,3,0,10,0}};
bool visited[5] = {false};
distance(matriceD,2,5);
printf("\n");
clear(visited);
parcours(matriceD,3,visited);
printf("\n");
clear(visited);
chemin(matriceND,2,2,1,visited);
printf("\n");
if (hasCycle(matriceND,visited)) printf("Le graphe contient au moins un cycle");
else printf("Le graphe ne contient pas de cycle");
printf("\n");
clear(visited);
connexe(matriceND2,visited);
printf("\n");
return 0;
}
NB : matriceD c'est pour matrice digérée, autrement dit on ne peut parcourir les aretes que dans un sens, c'est pour les questions distance, et parcours et plus petit chemin.
ND, bah forcément c'est le contraire, et c'est pour les autres questions.
