Discussion :

[nono9196]

Bonjour,
J'ai besoin d'utiliser l'algorithme de DFS mais je n'arrive pas à le programmer de façon récursive pourriez-vous m'aidez ?
Mon programme prend en entrer une liste de liste et le sommet de départ et renvoie la liste des sommets parcourus

Voici mon code :

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
def DFS(mat,src):
	"""
        Retourne la liste des sommets rencontrés lors
        d'un parcours en profondeur issu du sommet <src>.
 
        Arguments:
        mat -- matrice d'adjacence du graphe
        src -- un sommet du graphe, départ du parcours
        """
	visite = []
	visite.append(src)
	for j in range(0, len(mat)):
		if visite[j]==0 and mat[src][j] == 1:
			DFS(mat, j)
	return visite

Exemple :
>>> DFS([[0, 0, 1, 1, 0], [1, 0, 0, 0, 0], [0, 1, 0, 1, 0], [0, 1, 1, 0, 0], [1, 0, 1, 0, 0]],0)
[0, 2, 1, 3]

Merci d'avance

[wiztricks]

Salut,

Que veut dire DFS dans "algorithme de DFS"? Deep First Search? autre chose.

- W

[nono9196]

Merci de ta réponse oui c'est exactement cet algorithme pour parcourir un graph dans un ordre et retourner l'ordre.
Merci d'avance de ton aide.

[wiztricks]

c'est exactement cet algorithme pour parcourir un graph dans un ordre et retourner l'ordre.

Avec un peu de recherche sur Internet, vous avez déjà des codes tout faits.
Mais si vous voulez réfléchir au code que vous avez écrit:

Code :

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

1
2
3
4
5
6
7
def DFS(mat,src):
	visite = []
	visite.append(src)
	for j in range(0, len(mat)):
		if visite[j]==0 and mat[src][j] == 1:
			DFS(mat, j)
	return visite

La liste visite est initialisé à vide à chaque appel de DFS: impossible de savoir par où on est déjà passé. La solution est d'utiliser une variable globale ou de la passer en argument. Cela fait, çà va péter à cause de visite[j]==0 mais çà devrait être facile à corriger en réfléchissant un peu au message d'erreur (un IndexError je suppose).

- W

[nono9196]

Ok merci je vais faire cela et donner des nouvelles ensuite

[nono9196]

Après de multiples essais, je n'arrive pas à me débarasser de mon erreur Indexerror car je ne vois pas ce que je pourrais mettre à la place du

Code :

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

visite[j]==0

J'ai essayer cela :

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
visite = []
 
def DFS(mat,src):
	"""
        Retourne la liste des sommets rencontrés lors
        d'un parcours en profondeur issu du sommet <src>.
 
        Arguments:
        mat -- matrice d'adjacence du graphe
        src -- un sommet du graphe, départ du parcours
 
        >>> DFS([[0, 0, 1, 1, 0], [1, 0, 0, 0, 0], [0, 1, 0, 1, 0], [0, 1, 1, 0, 0], [1, 0, 1, 0, 0]],0)
        {0, 2, 1, 3}
        """
	### TODO : EXO 2 QUESTION 1 ###
	global visite
	visite.append(src)
	test = True
	for j in range(0, len(visite)):
		if visite[j]==src and mat[src][j] == 1:
			DFS(mat, j)
	return visite

Mais je ne rentre pas dans ma boucle.
Merci de votre réponse.