from collections import deque
F = deque()
for i in range(3):
F.append(i)
print(F)
for i in range(10):
if len(F) != 0:
print(F.popleft())
deque([0, 1, 2]) 0 1 2
from time import time
from collections import deque
N = 10000000
L = deque()
t1 = time()
for i in range(N):
L.appendleft(1)
t2 = time()
print(t2-t1, 'secondes)')
0.6295335292816162 secondes)
from collections import deque
LA = {1:[2,3,7],2:[6,5],3:[4],4:[],5:[6],6:[5],7:[1,2,4]}
def parcours(listeAdj,s):
""" parcours du graphe à partir du sommet s"""
# création du dictionnaire vu
vu = {}
for sommet in listeAdj:
vu[sommet] = False
# création de la pile ou de la file aTraiter
aTraiter = deque()
aTraiter.append(s)
while len(aTraiter)>0:
sommet = aTraiter.popleft()
vu[sommet] = True
for voisin in listeAdj[sommet]:
if not vu[voisin]:
aTraiter.append(voisin)
vu[voisin] = True
parcours(LA,1)
from collections import deque
import matplotlib.pyplot as plt
#Création du graphe (liste d'adjacence)
N = 30
S = [(i,j) for i in range(N) for j in range(N)]
listeAdj = {}
for i in range(N):
for j in range(N):
L = []
for a in (i-1,i+1):
if 0 <= a <= N-1:
L.append((a,j))
for b in (j-1,j+1):
if 0 <= b <= N-1:
L.append((i,b))
listeAdj[(i,j)] = L
# création des variables et initialisation
vu={}
for s in S:
vu[s] = False
aTraiter = deque()
aTraiter.append((N//2,0))
# affichage des sommets du graphe
for s in S:
plt.plot([s[0]],[s[1]],'.r')
#Parcours du graphe en largeur
for i in range((N**2)//2):
s = aTraiter.popleft() # on utilise une file
vu[s] = True
plt.plot([s[0]],[s[1]],'.k')
for v in listeAdj[s]:
if not vu[v]:
aTraiter.append(v)
vu[v] = True
plt.plot([s[0]],[s[1]],'.k')
from collections import deque
import matplotlib.pyplot as plt
#Création du graphe (liste d'adjacence)
N = 30
S = [(i,j) for i in range(N) for j in range(N)]
listeAdj = {}
for i in range(N):
for j in range(N):
L = []
for a in (i-1,i+1):
if 0 <= a <= N-1:
L.append((a,j))
for b in (j-1,j+1):
if 0 <= b <= N-1:
L.append((i,b))
listeAdj[(i,j)] = L
# création des variables et initialisation
vu={}
for s in S:
vu[s] = False
aTraiter = deque()
aTraiter.append((N//2,0))
# affichage des sommets du graphe
for s in S:
plt.plot([s[0]],[s[1]],'.r')
#Parcours du graphe en profondeur
for i in range((N**2)//2):
s = aTraiter.pop() # on utilise une pile
vu[s] = True
plt.plot([s[0]],[s[1]],'.k')
for v in listeAdj[s]:
if not vu[v]:
aTraiter.append(v)
vu[v] = True
plt.plot([s[0]],[s[1]],'.k')
plt.show()
from collections import deque
L1 = {1:[2,3,7],2:[1,7],3:[1],4:[7],5:[6],6:[5],7:[1,2,4]}
L2 = {1:[2,3,7],2:[1,5,6,7],3:[1],4:[7],5:[2,6],6:[2,5],7:[1,2,4]}
def estConnexe(listeAdj):
"""retourne True si le graphe est connexe et False sinon"""
# liste des sommets du graphe
S = list(listeAdj.keys())
# création du dictionnaire vu
vu = {}
for sommet in S:
vu[sommet] = False
# création de la pile ou de la file aTraiter
aTraiter = deque()
aTraiter.append(S[0])
vu[S[0]] = True
while len(aTraiter) > 0:
sommet = aTraiter.pop()
vu[sommet] = True
for voisin in listeAdj[sommet]:
if not vu[voisin]:
aTraiter.append(voisin)
vu[voisin] = True
for x in S:
if not vu[x]:
return False
return True
print(estConnexe(L1))
print(estConnexe(L2))
False True
from collections import deque
LA = {1:[2,3,4,7],2:[5,6,7],3:[4],4:[7],5:[6],6:[5],7:[1,2,4,6]}
def distances(listeAdj,s):
""" détermine les distances minimum de chaque sommet au sommet s
retourne un dictionnaire qui à chaque sommet associe sa distance à s"""
# création du dictionnaire vu
vu = {}
for sommet in listeAdj:
vu[sommet] = False
# création du dictionnaire des distances
dist = {}
for sommet in listeAdj:
dist[sommet] = float('inf') # flottant de valeur +infini
dist[s] = 0
# création de la pile ou de la file aTraiter
aTraiter = deque()
aTraiter.append(s)
vu[s] = True
while len(aTraiter)>0:
sommet = aTraiter.popleft()
for voisin in listeAdj[sommet]:
if not vu[voisin]:
aTraiter.append(voisin)
vu[voisin] = True
dist[voisin] = dist[sommet]+1
return dist
distances(LA,1)
{1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 2, 7: 1}
LA = {1:[(2,3),(7,5)], 2:[(5,7)], 3:[(1,3)], 4:[], 5:[(6,2)], 6:[(5,5),(2,7)],
7:[ (1,2),(2,6),(4,1),(6,4)]}
def minDist(L):
""" L est une liste de couples (s,dist)
la fonction retourne un élément pour lequel dist est le plus petit possible"""
xmin = L[0]
min = xmin[1]
for x in L:
if x[1]<min:
xmin = x
min = xmin[1]
return xmin
L = [(1,5),(6,6),(4,2),(2,5),(5,4)]
minDist(L)
(4, 2)
def Dijkstra(listeAdj,s):
""" listeAdj est la liste d'adjacence d'un graphe pondéré
pour chaque sommet on calcule la distance minimum de s à t
on retourne le résultat dans une liste"""
#création du dictionnaire vu
vu = {}
for sommet in listeAdj:
vu[sommet] = False
# création de la liste aTraite
aTraiter = [(s,0)]
#creation de la liste des résultats
R = []
while aTraiter != []:
x = minDist(aTraiter) #élément avec une distance minimum
aTraiter = [y for y in aTraiter if y != x] # on enlève cet élément de la liste aTraiter
sommet = x[0] # sommet correspondant
if not vu[sommet]: # si ce sommet n'a pas encore été vu
R.append(x) # on l'ajoute au résultat
delta = x[1] # distance à s correspondant
vu[sommet] = True #on le marque comme vu
for y in listeAdj[sommet]: #on place dans aTraiter tous ses voisins non vus
if not vu[y[0]]:
aTraiter.append((y[0],y[1]+delta))
return R
Dijkstra(LA,1)
[(1, 0), (2, 3), (7, 5), (4, 6), (6, 9), (5, 10)]
LA = {1:[(2,3),(7,5)], 2:[(5,7)], 3:[(1,3)], 4:[], 5:[(6,2)], 6:[(5,5),(2,7)],
7:[ (1,2),(2,6),(4,1),(6,4)]}
def minDist(L):
""" L est une liste de couples (s,dist) ou de triplets (s,dist,t)
la fonction retourne un élément pour lequel dist est le plus petit possible"""
xmin = L[0]
min = xmin[1]
for x in L:
if x[1]<min:
xmin = x
min = xmin[1]
return xmin
def cheminMini(listeAdj,s,t):
""" listeAdj est la liste d'adjacence d'un graphe pondéré
on détermine le chemin de poids minimum pour aller de s à t
on retourne le poids et le chemin comme une liste de sommets"""
#création du dictionnaire vu
vu = {}
for sommet in listeAdj:
vu[sommet] = False
# création de la liste aTraite
aTraiter = [(s,0)]
#creation du dictionnaire résultat de l'algorithme de Dijkstra
R = {}
while not vu[t]:
x = minDist(aTraiter) #élément avec une distance minimum
aTraiter = [y for y in aTraiter if y != x] # on enlève cet élément de la liste aTraiter
sommet = x[0] # sommet correspondant
if not vu[sommet]: # si ce sommet n'a pas encore été vu
R[sommet] = x # on l'ajoute au résultat
d = x[1] # distance à s correspondant
vu[sommet] = True #on le marque comme vu
for y in listeAdj[sommet]: #on place dans aTraiter tous ses voisins non vus
if not vu[y[0]]:
aTraiter.append((y[0],y[1]+d,sommet))
poids = R[t][1]
chemin = [t]
x = t
while x != s:
x = R[x][2]
chemin = [x]+chemin
return poids,chemin
print(cheminMini(LA,3,5))
(13, [3, 1, 2, 5])
from collections import deque
import matplotlib.pyplot as plt
#Création du graphe (liste d'adjacence)
N =40
S = [(i,j) for i in range(N) for j in range(N)]
listeAdj = {}
for i in range(N):
for j in range(N):
L = []
for a in (i-1,i+1):
if 0 <= a <= N-1:
L.append(((a,j),1))
for b in (j-1,j+1):
if 0 <= b <= N-1:
L.append(((i,b),1))
listeAdj[(i,j)] = L
def minDist(L):
""" L est une liste de couples (s,dist)
la fonction retourne un élément pour lequel dist est le plus petit possible"""
xmin = L[0]
min = xmin[1]
for x in L:
if x[1]<min:
xmin = x
min = xmin[1]
return xmin
def cheminMini(listeAdj,s,t):
""" listeAdj est la liste d'adjacence d'un graphe pondéré
on détermine le chemin de poids minimum pour aller de s à t
on retourne le poids et le chemin comme une liste de sommets"""
#création du dictionnaire vu
vu = {}
for sommet in listeAdj:
vu[sommet] = False
# création de la liste aTraite
aTraiter = [(s,0)]
#creation du dictionnaire résultat de l'algorithme de Dijkstra
R = {}
while not vu[t]:
x = minDist(aTraiter) #élément avec une distance minimum
aTraiter = [y for y in aTraiter if y != x] # on enlève cet élément de la liste aTraiter
sommet = x[0] # sommet correspondant
if not vu[sommet]: # si ce sommet n'a pas encore été vu
R[sommet] = x # on l'ajoute au résultat
d = x[1] # distance à s correspondant
vu[sommet] = True #on le marque comme vu
plt.plot([sommet[0]],[sommet[1]], '.k')
for y in listeAdj[sommet]: #on place dans aTraiter tous ses voisins non vus
if not vu[y[0]]:
aTraiter.append((y[0],y[1]+d,sommet))
poids = R[t][1]
chemin = [t]
x = t
while x != s:
x = R[x][2]
chemin = [x]+chemin
return poids,chemin
# affichage des sommets du graphe
for s in S:
plt.plot([s[0]],[s[1]],'.r')
print(cheminMini(listeAdj,(20,20),(5,5)))
(30, [(20, 20), (19, 20), (18, 20), (17, 20), (16, 20), (15, 20), (14, 20), (13, 20), (12, 20), (11, 20), (10, 20), (9, 20), (8, 20), (7, 20), (6, 20), (5, 20), (5, 19), (5, 18), (5, 17), (5, 16), (5, 15), (5, 14), (5, 13), (5, 12), (5, 11), (5, 10), (5, 9), (5, 8), (5, 7), (5, 6), (5, 5)])
from collections import deque
from numpy import sqrt
import matplotlib.pyplot as plt
#Création du graphe (liste d'adjacence)
N =40
S = [(i,j) for i in range(N) for j in range(N)]
listeAdj = {}
for i in range(N):
for j in range(N):
L = []
for a in (i-1,i+1):
if 0 <= a <= N-1:
L.append(((a,j),1))
for b in (j-1,j+1):
if 0 <= b <= N-1:
L.append(((i,b),1))
listeAdj[(i,j)] = L
def minDist(L):
""" L est une liste de couples (s,dist)
la fonction retourne un élément pour lequel dist est le plus petit possible"""
xmin = L[0]
min = xmin[1]
for x in L:
if x[1]<min:
xmin = x
min = xmin[1]
return xmin
def distEuclid(s,t):
""" retourne la distance euclidienne de s à t
s et t sont des couples de réels """
return sqrt((s[0]-t[0])**2+(s[1]-t[1])**2)
def cheminMini(listeAdj,s,t):
""" listeAdj est la liste d'adjacence d'un graphe pondéré
on détermine le chemin de poids minimum pour aller de s à t
on retourne le poids et le chemin comme une liste de sommets"""
#création du dictionnaire vu
vu = {}
for sommet in listeAdj:
vu[sommet] = False
# création de la liste aTraite
aTraiter = [(s,0)]
#creation du dictionnaire résultat de l'algorithme de Dijkstra
R = {}
while not vu[t]:
x = minDist(aTraiter) #élément avec une distance minimum
aTraiter = [y for y in aTraiter if y != x] # on enlève cet élément de la liste aTraiter
sommet = x[0] # sommet correspondant
if not vu[sommet]: # si ce sommet n'a pas encore été vu
R[sommet] = x # on l'ajoute au résultat
d = x[1] # distance à s correspondant
vu[sommet] = True #on le marque comme vu
plt.plot([sommet[0]],[sommet[1]], '.k')
for y in listeAdj[sommet]: #on place dans aTraiter tous ses voisins non vus
if not vu[y[0]]:
aTraiter.append((y[0],y[1]+distEuclid(y[0],t)-distEuclid(sommet,t)+d,sommet))
poids = R[t][1]
chemin = [t]
x = t
while x != s:
x = R[x][2]
chemin = [x]+chemin
return poids+distEuclid(s,t),chemin
# affichage des sommets du graphe
for s in S:
plt.plot([s[0]],[s[1]],'.r')
print(cheminMini(listeAdj,(20,20),(5,5)))
plt.show()
(29.999999999999996, [(20, 20), (19, 20), (19, 19), (18, 19), (18, 18), (17, 18), (17, 17), (16, 17), (16, 16), (15, 16), (15, 15), (14, 15), (14, 14), (13, 14), (13, 13), (12, 13), (12, 12), (11, 12), (10, 12), (9, 12), (8, 12), (7, 12), (7, 11), (7, 10), (7, 9), (7, 8), (7, 7), (6, 7), (6, 6), (5, 6), (5, 5)])
