Discussion :

[zeine77]

Salut;
J'ai voulu faire un programme en Pascal qui détermine les composantes fortement connexes d'un graphe donné.

J'ai fait tout: ajout et suppression des noeuds, des arcs , les successeurs, les prédecesseurs ... et ceci en utilisant une représentation par matrice d'adjacence, mais il me reste l'important : la procedure qui détermine la composante fortement connexe (CFC) contenant un sommet donné j'ai essayé plusieurs fois d'implementer l'algo de détermination des CFC, mais ça ne sort pas correctement.

donc, BESOIN de votre aide.

L'algorithme est le suivant :

Titre: ComposanteFortementConnexe

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
Entrées: G = (X;U) un graphe, a un sommet.
Sortie: X’ un sous-ensemble de sommets.
Variables intermédiaires: X1 et X2 deux sous-ensemble de sommets, examiné() une fonction,
x un noeud.
Début
   X1:={a};
   pour tout x appartient à X faire 
           examiné(x):= faux;
   tant que x appartient à X1 | non examiné(x) faire
           examiné(x):= vrai;
           pour tout u = (x;y) U | y n''appartient pas à X1 faire X1:= X1 union   {y};
   fin tant que;
   X2:={a};
   pour tout x appartient à X1 faire 
          examiné(x):=faux;
   tant que x appartient à X2 | non examiné(x) faire
          examiné(x) :=vrai;
          pour tout u = (y;x) U | y X2 faire X2:= X2 union {y};
   fin tant que;
   X’:= X1 intersection  X2;
Fin

[info_amel]

salut
le code que tu as écris est correcte et il peut etre implementer pour faire ton tp ...
ben moi j'ai déja fait le meme tp et je peux t'aider pour réaliser ton tp mais il faut que tu précise ce que tu n'as pas compris...
1-> tu pose tous les noeuds dans X
2-> tanque X <> vide
3-> choisir un noeud "n"
4-> commencer avec ce noeuds et parcourir le graphe en posant les noeuds visités dans X1
5-> posaer les noeuds qui menent à le noeud "n" dans X2
6-> dans "resultat" on pose les noeuds qui se trouvent dans X1 et X2.
7->on affiche la premiere composante fortement connexe qui est l'ensemble resultat
8->on supprime les noeuds de la composante fortement connexe trouvée de l'ensemble X
9-> on revient à l'étape 1

bon courage

[Amine_sas]

Salut,
La programmation est quelque chose de très abstrait. L'implémentation de l'algorithme que tu as donné peut être réalisée de différentes façons et elle est étroitement liée aux structures de données choisies. Par exemple X1 peut être un tableau ou une liste liée ..etc (idem pour X2).
Si j'étais à ta place j'utiliserais les éléments suivants:
- Un tableau de 2 lignes et a colonnes pour la liste des arcs [i](si arcs[i][1] = x et arcs[2] = y cela veut dire qu'il existe un arc entre x et y).
- Un tableau de n éléments pour les composantes fortement connexes (l'indice du tableau étant le noeud et le contenu de la case est la cfc du noeud, autrement dit: si noeuds[x] = c alors x appartient à cfc n° c). Le tableau est initialisé a 0.
- Une variable c initialisé à 1pour compter les cfc.
- Une fonction booléenne pour déterminer s'il existe un arc entre deux noeuds. La fonction va chercher dans le tableau arcs, en voici un exemple en pseudo C:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
boolean existeUnArcEntre(x , y){
   for ( i = 1; i <= a; i++){
   // pour chaque arc du tableau
   if (arcs[i][1] == x AND arcs[i][2] == y)     OR (arcs[i][1] == y AND arcs[i][2] == x)
     return true;
 }
 
return false;
}

- Une fonction récursive (qui s'appelle à elle même) pour parcourir tous les noueuds:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
parcourir(x){
 ccf[x] = c;
 // pour tout noeud différent de x
pour y = 1 jusqu'à n faire:
// si y n'a pas été visité et il existe un arc entre x et y:
if ccf[y] == 0 AND    (existeUnArcEntre(x, y) == true
 parcourir(y);

c++; // c := c + 1 si tu es trop Pascal.

}

- Dans le programme principal, parés avoir lu la liste des arcs et initialisé les variables, choisir le premier noeud et lancer la procédure parcourir:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
parcourir(x); // appelée une seul fois dans le programme principal 
écrire("le nombre de cfc est", c - 1);

Bon code.

[benDelphic]

Rappelons qu'en théorie des graphes, une composante fortement connexe est un sous graphe engendré connexe en plus clair un ensemble de sommet tel que quel que soit deux sommets distincts il existe un chemin reliant l'un à l'autre.
le procédé que tu veux implémenter est une coloration de sommet . en clair pour trouver une cfc :
-a partir d'un sommet on colorie tout les sommets voisin et on propage cette propriétés
-a partir d'un sommet coloré 1 (on modifie la couleur en 2) on refait le même travail.
la cfc est donc donnée par les sommets de couleurs 2.En supprimant cet ensemble on reitère.
en clair , sur une matrice adjacence on peut écrire une fonction récursive de coloration à partir d'un sommet .

[taktouk1986]

Salut,
La programmation est quelque chose de très abstrait. L'implémentation de l'algorithme que tu as donné peut être réalisée de différentes façons et elle est étroitement liée aux structures de données choisies. Par exemple X1 peut être un tableau ou une liste liée ..etc (idem pour X2).
Si j'étais à ta place j'utiliserais les éléments suivants:
- Un tableau de 2 lignes et a colonnes pour la liste des arcs [i](si arcs[i][1] = x et arcs[2] = y cela veut dire qu'il existe un arc entre x et y).
- Un tableau de n éléments pour les composantes fortement connexes (l'indice du tableau étant le noeud et le contenu de la case est la cfc du noeud, autrement dit: si noeuds[x] = c alors x appartient à cfc n° c). Le tableau est initialisé a 0.
- Une variable c initialisé à 1pour compter les cfc.
- Une fonction booléenne pour déterminer s'il existe un arc entre deux noeuds. La fonction va chercher dans le tableau arcs, en voici un exemple en pseudo C:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
boolean existeUnArcEntre(x , y){
   for ( i = 1; i <= a; i++){
   // pour chaque arc du tableau
   if (arcs[i][1] == x AND arcs[i][2] == y)     OR (arcs[i][1] == y AND arcs[i][2] == x)
     return true;
 }
 
return false;
}

- Une fonction récursive (qui s'appelle à elle même) pour parcourir tous les noueuds:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
parcourir(x){
 ccf[x] = c;
 // pour tout noeud différent de x
pour y = 1 jusqu'à n faire:
// si y n'a pas été visité et il existe un arc entre x et y:
if ccf[y] == 0 AND    (existeUnArcEntre(x, y) == true
 parcourir(y);

c++; // c := c + 1 si tu es trop Pascal.

}

- Dans le programme principal, parés avoir lu la liste des arcs et initialisé les variables, choisir le premier noeud et lancer la procédure parcourir:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
parcourir(x); // appelée une seul fois dans le programme principal 
écrire("le nombre de cfc est", c - 1);

Bon code.

merci pour l'algorithme mais j'aime savoir si cet algorithme permet de connaitre si le graphe est fortement connexe ou nn? merci ...

[Amine_sas]

Salut,

merci pour l'algorithme mais j'aime savoir si cet algorithme permet de connaitre si le graphe est fortement connexe ou nn? merci ...

Si, après l'execution, le nombre des cfc sera de 1 alors le graphe est fortement connexe que ce soit un graphe de 1 ou d'un nombre infini de noeuds (théoriquement).