Bonjour,

J'ai un code qui permet de générer des matrices d'adjacence de façons aléatoires et ensuite qui permet de voir si elle sont connexe ou non. Avec cela je trace ensuite le graphique montrant le pourcentage de matrice connexe en fonction de leur nombre d'arrête. Ce qui m'interesse est pour les cas de très grosses matrices à partir de 100 et donc que cela est très long si quelqu'un peut m'aider à l'optimiser pour gagner ?

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import random
import numpy
import matplotlib.pyplot as plt
 
def creer_noeud(taille, arrete):
	L=[]
	i=0
	while(i<arrete):
		al1=random.randint(0,taille-1)
		al2=random.randint(0,taille-1)
		if(al1,al2) not in L and (al2,al1) not in L:
			if al1 == al2:
				L.append((al1, al2))
			else:
				L.append((al1,al2))
				L.append((al2,al1))
			i= i + 1
	return L
 
 
 
def creer_matrice(taille, arrete):
	"""int * int-> list[list[int]]
                Créer une matrice d'adjacence aléatoire d'un graphe non orienté"""
	mat = [[0] * taille for _ in range(taille)]
	noeud = creer_noeud(taille, arrete)
	for i in range(len(noeud)):
		(x,y)=noeud[i]
		mat[x][y] = 1
	return mat
 
def DFS(mat, src):
	visite = []
	DFS_rec(mat, src, visite)
	return visite
 
def DFS_rec(mat,src, visite):
	"""
        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}
        """
	visite.append(src)
	for j in range(0, len(mat)):
		if j not in visite and mat[src][j] == 1:
			DFS_rec(mat, j, visite)
	return visite
 
def isConnected(mat):
	"""
        Retourne vrai si le graphe est connexe, faux sinon.
 
        Arguments:
        mat -- matrice d'adjacence du graphe
 
        >>> isConnected([[0, 1, 0], [0, 0, 0], [0, 0, 0]])
        False
 
        >>> isConnected([[0, 1, 0], [0, 0, 1], [0, 0, 0]])
        True
        """
 
	return (len(DFS(mat, 0)) == len(mat))
 
def pour_connexe(n, taille, arrete):
	res=0
	for i in range(n):
		if isConnected(creer_matrice(taille, arrete)):
			res = res + 1
	return (res * 100)/n 
 
def liste_connexe(taille, n):
	R = []
	for i in range((taille**2)//2):
		R.append(pour_connexe(n, taille, i))
		print(i)
	return R
 
 
plt.plot(liste_connexe(50, 10))
plt.title("% de graphe connexe en fonction du nnombre d'arrete")
plt.ylabel('% de graphe connexe')
plt.xlabel("nb d'arrete")
plt.show()
Merci
Bonsoir