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:)
Version imprimable
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:)
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
meric de ton Compréhension
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:
2
3
4
5
6
7
8
9
10
11
Pas indispensables, on peut rendre dérecursiver tous les algorithmes recursifs.Citation:
des fonctions recursives sont fortement utiles (voir indispensables parfois)
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).
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.Citation:
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,
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.Code:chercher dans le tableau l'existence d'une arete entre x et un sommet quelquonque
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
Je dirais même : Une fonction récursive est une fonction récursive.Citation:
(une fonction recursive est une fonction qui s'appelle a elle-meme).
Avec une matrice d'adjacence, ça se fait en O(1)Citation:
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.
Trop facile car utilisable même pour les fonctions non récursive. (mais bien tenté)Citation:
Je dirais même : Une fonction récursive est une fonction récursive.
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é.Citation:
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).
Non, ça n'est pas 2 lignes et n colonnes mais n lignes et n colonnes (ton graphe est orienté, ne l'oublie pas.)Citation:
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,