Discussion :

[nono9196]

Bonjour,

Voila je suis entrain de travailler sur un programme de BFS en python mais mon problème est que j'ai réussi à trouvers des programmes en python comme celui-là :

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
def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited
 
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}
 
print(dfs(graph, 'A')) # # {'E', 'D', 'F', 'A', 'C', 'B'}

Je voudrai pouvoir utiliser ce programme avec une matrice d'adjacence, donc une liste de liste composé de 1 et de 0, et non un dictionnaire pour pouvoir au lieu de retourner l'ordre des sommets visités retourner leur distance au sommet de départ et s'il n'a pas été visités -1:

Code :

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

assert BFS([[0, 1, 1, 0, 0], [0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0], [1, 0, 1, 0, 0]],0) == [0, 1, 1, 2, -1]

Merci de votre aide

[wiztricks]

Salut,

Soit vous convertissez la matrice en graphe, soit vous utilisez le code que vous aviez posté dans les posts précédents.

- W

[nono9196]

Merci de votre réponse,

Mais dans les post précédents c'étaient pour un parcours en profondeur et non en largeur.
J'ai essayer de faire cela mais je n'ai pas une valeur cohérente de la distance :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
def bfs2(mat, start):
    visited = set()
    distance = [-1 for i in range(len(mat))]
    distance[start] = 0
    temp = 1
    visited.add(start)
    for i in range(len(mat)):
        for j in range(len(mat)):
            if mat[i][j] == 1 and j not in visited:
                distance[j] = temp
                visited.add(j)
        temp = temp + 1
    return distance

Cela me donne :

Code :

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

1
2
mat1 = [[0,1,1,0], [1,0,1,0], [1,1,0,1], [0,0,1,0]]
print(bfs2(mat1, 0)) #[0, 1, 1, 3] au lieu de [0, 1, 1, 2]

Si quelqu'un a une idée ....

[wiztricks]

Salut,
Essayez avec çà:

Code :

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

1
2
3
4
5
6
7
8
9
def dfs2(matrix, start):
    visited, stack = [], [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.append(vertex)
            adjency = [ x for x, e in enumerate(matrix[vertex]) if e and x not in visited ]
            stack.extend(adjency)
    return visited

[nono9196]

Merci pour la fonction mon problème est que j'ai besoin d'afficher la distance de chaque point au point de départ et je n'arrive pas à avoir une distance qui soit cohérente comme sur mon poste au - dessus.

[wiztricks]

Merci pour la fonction mon problème est que j'ai besoin d'afficher la distance de chaque point au point de départ et je n'arrive pas à avoir une distance qui soit cohérente comme sur mon poste au - dessus.

Mouais, çà serait mieux de déjà vérifier que votre code est un BFS: pas de stack et pas d'ajout à la fin, pour moi, c'est autre chose. Après les distances, c'est encore autre chose.

- W

[nono9196]

En faite je ne connais pas trop c'est fonction que sont pop et extend du coup j'ai voulu le faire seulement avec ce que je connaissais mais je crois que l'essai n'est pas concluant.

[lg_53]

Code :

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

1
2
list1.extend(list2)  <=>  list1 = list1 + list2
a = list1.pop()       <=>  a = list1[-1]; del list1[-1]  ### Efface le dernier élément de la liste

Et si vous ne connaissez pas la fonction del vous pouvez très bien remplacer :

Code :

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

del a[-1]   <=>   a=a[:-1]

Donc tout est faisable avec les fonctions dont vous avez connaissances.

Sinon une petite lecture de la documentation Python sur les listes permettera de faire le point sur les méthodes sur les listes :
https://docs.python.org/3/tutorial/datastructures.html