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.

[wiztricks]

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]visite = []

Ca sert à rien d'essayer n'importe quoi en espérant que çà va le faire, il faut d'abord faire fonctionner son cerveau. Dans la boucle, vous parcourez la liste des nœuds pour savoir ceux qui sont adjacents au nœud courant. Donc çà ne peut pas être autre chose que for j in range(0, len(mat)):.
Après à quelles conditions "entrer" dans la récursion? Si le nœud j n'a pas été visité et qu'il existe un chemin entre j et src.
Et la condition "j a été visité" se traduit par "j est dans la liste visite".

- W

[nono9196]

J'ai fait cela pour corriger le problème grâce à vous cela marche.
Que pensez-vous de cette solution :

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
visite = []
test = set()
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.append(src)
	test.add(src)
	for j in range(0, len(mat)):
		if j not in test and mat[src][j] == 1:
			DFS(mat, j)
	return visite
 
assert 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 encore pour votre aide.