Le parcours en largeur python d’un graphe (BFS) est un algorithme utilisé pour parcourir les structures de donnée de graphe. BFS met en œuvre une stratégie spécifique pour visiter tous les sommets d’un graphe.
Introduction – Parcours en largeur python
BFS commence par un sommet, puis il vérifie les voisins du sommet initial, puis les voisins des voisins, etc.
En entrée de l’algorithme il y a le graphe G et un sommet de départ D pour lequel on considère que la distance est 0.
En sortie de l’algorithme sont calculées toutes les distances entre le sommet D et chaque sommet du graphe G ainsi que l’arbre couvrant si le graphe G est connexe (c’est à dire que pour toute paire de sommet il existe un chemin entre eux dans le graphe).
Description de l’algorithme
On utilise les tableaux suivants :
Distance[.] : Stocke la distance entre D (sommet de départ) et un autre sommet du graphe.
Father[.] : Stocke le sommet père d’un sommet du graphe parcouru.
Visite[.] : Stocke l’état de visite du sommet, liste des valeurs possible 0:pas encore visité,1:Visite en cours,2:Visité
On utilise les fonctions suivantes pour une file F :
First(F) : Retourne l’élément en tête de la file F sans le supprimer.
Dequeue(F) : Retourne l’élément en tête de la file F en le supprimant.
Append(F, A) : Mettre l’élément A dans la file F en queue de la file.
Les étapes de l’algorithme :
Phase d’initialisation
1. Pour tous les sommets faire
Visite = 0 (Pas encore visité)
Pere = null (Initialise le tableau)
Distance = -1
2. Append(F,D) (ajoute l’élément de départ)
3. Distance[R] = 0 (postulat de départ)
Phase d’action (parcours du graphe G)
Tant que la file F n’est pas vide
t = First(F)
Pour tous les voisins v de t faire
Si Visite[v] = 0 (sommet non visité) alors
Visite[v] = 1 (Visite en cours)
Distance[v] = Distance[t] + 1
Father[v] = t
Append(F,v)
Dequeue(F)
Visite[t] = 2
Si on détaille les étapes avec le cas du graphe exemple ci-dessous.
Phase d’initialisation :
Initialisation l’élément A est l’élément de départ à distance 0, il est coloré en orange pour indiquer que la visite est en cours.
Visite des voisins du sommet A (Visite du sommet B)
Le sommet B passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.
Visite des voisins du sommet A (Visite du sommet C)
Le sommet C passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.
Marquage de A comme visité et suppression de la file
A est marqué comme visité (couleur bleue) et retiré de la tête de la file
Visite des voisins du sommet B (Visite du sommet D)
Le sommet C etant marqué comme en cours de visite il ne sera pas visité, on visite le sommet D on calcule sa distance = 2 et on note le sommet B comme père du sommet B.
Marquage de B et C comme visité et suppression de la file
B est marqué comme visité (couleur bleue) et retiré de la tête de la file C est marqué comme visité (couleur bleue) et retiré de la tête de la file (son voisin D est marqué en cours de visite)
Marquage de D comme visité et fin de l’algorithme
D est marqué comme visité (couleur bleue) et retiré de la tête de la file. Fin de l’algorithme
Construction de l’arbre couvrant si le graphe est connexe
Si le graphe est connexe on déplie le résultat du parcours et on obtient l’arbre couvrant du graphe qui contient tous les sommets.
Application : Le parcours en largeur d’un graphe (BFS) est utile pour :
Vérifier si un graphe est connexe (tous les sommets sont alors marqués comme visités à la fin de l’algorithme).
Implémentons le parcours en profondeur python d’un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.
Introduction
Le principe et d’explorer le graphe à partir d’un sommet donné et on explore tous ses voisins en allant le plus profond possible (càd en répétant l’opération de sommet visité en sommet visité jusqu’à ce qu’on soit coincé, on revient alors via le chemin emprunté jusqu’au point de départ).
Le parcours en profondeur permet de trouver l’arbre couvrant du graphe qui n’est pas le même en général que l’arbre couvrant trouvé via le parcours en largeur du graphe.
L’algorithme en résumé :
Phase de descente :
Partir du sommet choisi pour démarrer et le marquer.
Tant que c’est possible :
Aller vers un voisin non visité et le marquer.
Mémoriser l’arrête ou l’arc par lequel on est passé.
Si tous les voisins sont déjà visités :
Revenir vers le sommet par lequel il a été découvert (backtrack phase : de remontée)
Si tous les sommets du graphe sont visités (sont dans l’arbre couvrant) alors le graphe est connexe sinon le graphe n’est pas connexe.
Exemple Python avec 3 graphes :
Exemple de graphe connexeExemple de graphe non connexeExemple de graphe connexe
Module Python pour le parcours en profondeur :
#Parcours en profondeur d'un graphe
# Algorithme récursif : Le principe est d'explorer le graphe et de revenir sur ses pas lorsuqu'on est coincé.
def parcours_en_profondeur(graphe, sommet_en_cours:str, sommets_visites:[]):
print('Essai d explorer le sommet :' + str(sommet_en_cours))
if sommet_en_cours not in sommets_visites:
sommets_visites.append(sommet_en_cours) #Ajoute le sommet en cours au noeud visité
print('Exploration du sommet :' + str(sommet_en_cours))
sommets_voisins_non_visites = []
for sommet_voisin in graphe[sommet_en_cours]:
if sommet_voisin not in sommets_visites:
sommets_voisins_non_visites.append(sommet_voisin) # Constitue la liste des sommets voisins non encore visité
for sommet in sommets_voisins_non_visites:
#pour tout les sommets voisins non visités on effectue un parcours en profondeur
parcours_en_profondeur(graphe, sommet, sommets_visites)
#Fonction de test si le graphe est connexe suite à un parcours en profondeur
def est_un_graphe_connexe(graphe, sommets_visites):
if len(sommets_visites) == len(graphe):
print("Le graphe est connexe")
print(20 * "-")
else:
print("Le graphe n'est pas connexe")
print(20 * "-")
#Liste d'ajacence du graphe
graphe = {
'A': ['B','C'],
'B': ['A','C', 'D'],
'C': ['D'],
'D': ['C','A']
}
sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)
#Exemple de graphe non connexe : Le sommet D n'est pas connecté au graphe
graphe = {
'A': ['B','C'],
'B': ['A','C'],
'C': ['A'],
'D': []
}
sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)
#Autre exemple
graphe = {
'A': ['B','D'],
'B': ['A','C'],
'C': [],
'D': ['A']
}
sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)
#en fin de parcours si tout les sommets sont dans les sommets visités alors le graphe est connexe
#Note
#J'ai rencotré l'erreur IndentationError: unindent does not match any outer indentation level
#Je l'ai simplement résolu en reprenant toute l'indentation en debut de ligne
#et en la remplaçant par des Tabulation plutot que des espaces
Un cycle Hamiltonien est un cycle qui contient tous les sommets du graphe.
Il n’y a pas d’algorithme général (càd valable pour n’importe quel graphe) et efficace (càd pas d’algorithme dans le nombre d’étape de calcul soit un polynôme de la taille du graphe) pour trouver si il y a un cycle hamiltonien dans un graphe.
Cycle hamiltonien source wikipedia
Condition de DIRAC : Si pour tous les sommets u du graphe G degré(u) >= n /2 alors G contient un cycle hamiltonien
Condition de ORE : Si pour toute paire u et v de non voisins deg(u) + deg(v) >=n alors G contient un cycle hamiltorien
Si un graphe vérifie la condition de DIRAC alors il vérifie la condition de ORE (la réciproque est fausse).
Un couplage est un ensemble d’arête deux à deux indépendantes : elle ne partagent pas de sommets.
Exemple de couplage dans un graphe : les 2 arrêtes rouges ne partagent pas de sommets (2 à 2 indépendantes)
Couplage parfait : Chaque sommet du graphe est dans exactement une arrête du couplage
Exemple de couplage parfait dans un graphe
Un graphe parfait a un nombre pair de sommets (la réciproque n’est pas vraie)
Un couplage parfait est un couplage de taille maximale (impossible à agrandir, on ne peut pas coupler plus), la réciproque n’est pas vraie.
Exemple de couplage maximal mais pas de taille max (càd il est possible de faire par exemple un couplage avec 3 arrêtes)
Exemple d’utilisation : Dans une entreprises logistique les salariés ont un ou plusieurs permis leur permettant de rouler un certain type de véhicule. On peut représenter le problème dans un graphe avec comme sommet les salariés et les véhicules de l’entreprise. Pour résoudre le problème il faut alors trouver un couplage de taille max.
Algorithme glouton pour trouver un couplage maximal :
Etape 1 : On sélectionne une arrête aléatoirement et on la mémorise dans une copie du graphe (à gauche)
Sélection de l’arrête
Etape 2 : On supprime les arrêtes qui sont incidentes aux deux sommets et on sélectionne une autres arrête aléatoirement
Etape 3 : On supprime les arrêtes qui sont incidentes aux deux sommets, on obtient alors un couplage maximal
PageRank python est un algorithme utilisé par Google Search pour classer les sites Web dans les résultats de leurs moteurs de recherche. PageRank est un moyen de mesurer l’importance des pages de site Web.
Introduction :
Ce n’est pas le seul algorithme utilisé par Google pour ordonner les résultats des moteurs de recherche, mais c’est le premier algorithme utilisé par la société, il est le plus connu.
Le PageRank d’une page est calculé à partir de la somme du PageRank des pages avec un lien entrant à la page calculée que l’on divise par le nombre de pages sortantes de cette dernière, on applique un facteur d’atténuation pour symboliser la probabilité que l’utilisateur surfe sur une autre page.
Implémentation pagerank python :
J’installe networkx, c’est un package Python pour la création, la manipulation et l’étude de la structure, de la dynamique et des fonctions de réseaux complexes.
Networkx fournit des structures de données et des méthodes pour stocker des graphes que j’utilise pour l’algorithme pagerank.
import networkx as nx
import numpy as np
graphe=nx.DiGraph()
tableauPages = ["A","B","C"] #Exemple de page rank avec 3 pages
graphe.add_nodes_from(tableauPages) #Ajout des sommets du graphe
#on ajoute des arcs, on a :
#la page A a un lien vers B
#la page B a un lien vers C
#la page C a un lien vers B
#la page C a un lien vers A
# la page B a 2 lien entrant
# la page C a un lien entrant 2 liens sortant
# la page A a un lien entrant un lien sortant
graphe.add_edges_from([('A','B'), ('C','A'),('B','C'), ('C','B')])
print("Sommets du graphe : ")
print(graphe.nodes())
print("Arrêtes du graphe : ")
print(graphe.edges())
#Si on considere un facteur d'attenuation de 0.85 = d
# la formule du page rank est :
#PR(p) = (1-d)/n + d * Somme de toutes les pages(PR(i) des lien entrants à p/nombre de lien sortant de la page qui reference p)
# PR(A) = (1-0,85)/3 + 0,85 * (PR(C)/2)
# PR(B) = (1-0,85)/3 + 0,85 * (PR(A)/1 + PR(C)/2)
# PR(C) = (1-0,85)/3 + 0,85 * (PR(B)/1)
pagerank = nx.pagerank(graphe)
print(pagerank)
Graphe (Graph) : Un ensemble de point reliés entre eux
Sommets (vertices, a vertex) : Les points d’un graphe s’appellent des sommets Sommets adjacents (adjacent vertices) : Deux sommets sont adjacents si ils sont reliés entre eux Arête (edge) : La liaison entre deux sommets s’appelle une arête si la relation entre deux sommet n’est pas orientée (pas de notion de précédence, ou d’ordre dans lequel on visite les deux sommets).
source wikipedia : graphe orienté
Arc (arc): La liaison orientée entre deux sommet (c’est une flèche qui indique le sens de la relation orientée, il y a une notion d’ordre d’exécution et de contrainte pour visiter les deux sommets) Le degré d’un sommet (the degree of a vertex) : Nombre d’arêtes qui partent d’un sommet. Ordre d’un graphe (order of a graph) : Le nombre de sommet dans un graphe. Graphe Connexe (connected graph) : Un graphe est connexe si tous les sommets sont reliés par une chaine quelconque. Chaine Eulerienne (eulerian path) : Une chaine qui prend toutes les arêtes une seule fois du graphe.
Matrice d’adjacente : La matrice d’adjacence d’un graphe est une matrice dont les lignes et les colonnes sont toutes deux indexées par les sommets du graphe, avec un 1 dans la cellule pour la rangée i et la colonne j lorsque les sommets i et j sont adjacents, et un 0 sinon.
