Lire un graphe

Le code.

G = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}

def voisins(G, s):
    return G[s]

def sont_voisins(G, u, v):
    return v in G[u]

def nb_aretes(G):
    total = 0
    for s in G:
        total = total + len(G[s])
    return total // 2       # chaque arete compte dans DEUX listes

print(voisins(G, 2))            # [0, 1, 3]
print(sont_voisins(G, 0, 3))    # False
print(sont_voisins(G, 2, 3))    # True
print(nb_aretes(G))             # 4

Les arêtes de l'exemple. Ce sont $\{0,1\}$, $\{0,2\}$, $\{1,2\}$ et $\{2,3\}$ : il y en a bien $4$. La somme des longueurs des listes vaut $2+2+3+1=8$, et $8//2=4$.

Le // 2 est essentiel. Dans un graphe non orienté, chaque arête $\{u,v\}$ figure deux fois dans la structure : $v$ dans G[u] et $u$ dans G[v]. Sans la division, on compterait chaque arête deux fois. Sur un graphe orienté, en revanche, la somme des longueurs donne directement le nombre d'arcs, et diviser serait une erreur.

Le coût des deux représentations. Avec les listes d'adjacence, tester v in G[u] parcourt la liste des voisins de u : le coût dépend du degré de u. Avec une matrice d'adjacence, le même test se ferait en une seule lecture A[u][v], mais la matrice occuperait $n^2$ cases même si le graphe a peu d'arêtes. Le choix dépend donc de ce qu'on fait le plus souvent, et du nombre d'arêtes que porte le graphe.

Un contrôle de saisie. Le sommet $3$ est bien dans G[2] et $2$ est bien dans G[3] : la structure est symétrique, comme doit l'être un graphe non orienté. Une asymétrie fausserait silencieusement les degrés et le compte des arêtes.