Discussion :

[wedoud]

SVP est ce que vous avez plus des Explications sur les graphes, et la recherche par contagion dans un graphe pour determiner est ce qu 'il existe un chemain entre deux sommets
merci .
JAZAKOUM LAHOU KHAYRAN

[millie]

Ce n'est pas la peine de poster le message en double, tu peux voir sur:
http://www.developpez.net/forums/sho...d.php?t=181981

[wedoud]

meric de ton Compréhension

[Amine_sas]

Un graphe orienté peut etre representer par un tableau de 2 lignes et n colonnes (n: le nombre d'aretes) ou par liste chainée, il peut egalement etre lu a partir d'un fichier...

Lorsque on manipule un graphe pour tester sa connexité ou sa forte-connexité...., des fonctions recursives sont fortement utiles (voir indispensables parfois).

(une fonction recursive est une fonction qui s'appelle a elle-meme).

exemple pour tester l'existence d'un chemin entre les sommets x et y

Code :

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

1
2
3
4
5
6
7
8
9
10
11
int chemin_existant(x,y)
{
   chercher dans le tableau l'existence d'une arete entre x et un sommet quelquonque z ;
 
 si ce sommet z == y alors return OUI
 sinon chemin_existant(z,y);
 
 si la recherche a atteint la fin du tableau sans trouver un chemin alors
  return NON;
 
}

[millie]

des fonctions recursives sont fortement utiles (voir indispensables parfois)

Pas indispensables, on peut rendre dérecursiver tous les algorithmes recursifs.

De plus, il est parfois meilleur de réaliser des algorithmes non récursifs en C, car il peut vite y avoir des dépassements de pile lors des appels.(un gros graphe avec plusieurs milliers de sommets par exemple).

Un graphe orienté peut etre representer par un tableau de 2 lignes et n colonnes (n: le nombre d'aretes) ou par liste chainée,

En fait, ça dépend de ce que tu comptes faire wedoud, si tu comptes ajouter en cours de route des arêtes, il vaut mieux la liste chaînée (ou une pile, pas forcement chaînée car dans un graphe simple, tu peux majorer le nombre d'arêtes). Si par contre, ton graphe est défini une fois pour toute, un tableau rendra les algorithmes plus rapides.

Code :

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

chercher dans le tableau l'existence d'une arete entre x et un sommet quelquonque

Tu peux créer une implémentation de ton type graphe qui réalise cette opération en temps constant. Genre, un tableau de pointeur sur des listes de successeurs des sommets. Quand le pointeur est nul, bah, le sommet x n'a pas de successeur.


Sinon, l'algorithme n'est pas bon.

Si tu disposes des sommets 1 2 3 et des arêtes (1,2), (2,1) et (2,3).
Tu cherches l'existence d'un sommet entre 1 et 3. Tu peux boucler toujours entre 1 et 2 et ne jamais atteindre trois. Il faut un algorithme avec des colorations comme je t'ai écrit dans:
http://www.developpez.net/forums/sho...d.php?t=181981

[panda31]

(une fonction recursive est une fonction qui s'appelle a elle-meme).

Je dirais même : Une fonction récursive est une fonction récursive.

[PRomu@ld]

Code :
chercher dans le tableau l'existence d'une arete entre x et un sommet quelquonque

Tu peux créer une implémentation de ton type graphe qui réalise cette opération en temps constant. Genre, un tableau de pointeur sur des listes de successeurs des sommets. Quand le pointeur est nul, bah, le sommet x n'a pas de successeur.

Avec une matrice d'adjacence, ça se fait en O(1)

Je dirais même : Une fonction récursive est une fonction récursive.

Trop facile car utilisable même pour les fonctions non récursive. (mais bien tenté)

De plus, il est parfois meilleur de réaliser des algorithmes non récursifs en C, car il peut vite y avoir des dépassements de pile lors des appels.(un gros graphe avec plusieurs milliers de sommets par exemple).

C'est d'ailleur le seul cas ou la dérécursification a une utilité (d'ailleurs il faut faire attention car cette opération utilise une pile, qui donc peut déborder !). Parce qu'algorithmiquement parlant, il n'y a aucune incidence sur la rapidité.

Un graphe orienté peut etre representer par un tableau de 2 lignes et n colonnes (n: le nombre d'aretes) ou par liste chainée,

Non, ça n'est pas 2 lignes et n colonnes mais n lignes et n colonnes (ton graphe est orienté, ne l'oublie pas.)