Un graphe connexe est un graphe où :

Il existe un chemin entre toute paire de sommets

Comment représente-t-on un graphe pondéré avec des listes d'adjacence ?

On utilise des tuples (voisin, poids)

Qu'est-ce qu'un cycle dans un graphe ?

Un chemin qui revient à son point de départ

Dans un graphe orienté, un arc de A vers B signifie :

On peut aller de A vers B mais pas forcément de B vers A

Un graphe connexe est un graphe où :

Il existe un chemin entre toute paire de sommets. Un graphe connexe signifie que depuis n'importe quel sommet, on peut atteindre n'importe quel autre sommet en suivant les arêtes.

Comment représente-t-on un graphe pondéré avec des listes d'adjacence ?

On utilise des tuples (voisin, poids). On utilise des tuples (voisin, poids) dans les listes d'adjacence, par exemple : {'A': [('B', 5), ('C', 3)]}.

Qu'est-ce qu'un cycle dans un graphe ?

Un chemin qui revient à son point de départ. Un cycle est un chemin dont le sommet de départ et le sommet d'arrivée sont identiques. Par exemple : A → B → C → A.

Dans un graphe orienté, un arc de A vers B signifie :

On peut aller de A vers B mais pas forcément de B vers A. Dans un graphe orienté, un arc a une direction. L'arc (A→B) permet d'aller de A vers B, mais ne garantit pas l'existence d'un arc (B→A).

Pour tester si l'arête (i,j) existe, quelle représentation est la plus efficace ?

Matrice d'adjacence en O(1). Avec une matrice d'adjacence, il suffit de lire M[i][j] en O(1). Avec des listes d'adjacence, il faut parcourir la liste des voisins.

Quel est un exemple concret de graphe non orienté ?

Le réseau d'amitiés Facebook. Sur Facebook, l'amitié est réciproque : si A est ami avec B, alors B est ami avec A. C'est un graphe non orienté. Twitter (followers) est orienté car suivre n'est pas réciproque.

NSI (Spé) — Structures de données

Graphes : représentation et parcours

Q: Dans un graphe non orienté, la matrice d'adjacence est :

Symétrique. Dans un graphe non orienté, si l'arête (i,j) existe, alors l'arête (j,i) aussi, donc M[i][j] = M[j][i] : la matrice est symétrique.

Q: Quelle est la complexité mémoire d'une matrice d'adjacence pour n sommets ?

O(n²). La matrice d'adjacence est un tableau de taille n×n, soit O(n²) en mémoire, indépendamment du nombre d'arêtes.

Q: Les listes d'adjacence sont préférées pour les graphes :

Creux (peu d'arêtes). Les listes d'adjacence occupent O(n + m) en mémoire, ce qui est bien plus efficace que O(n²) quand le graphe a peu d'arêtes (m << n²).

Q: Le degré d'un sommet dans un graphe non orienté est :

Le nombre d'arêtes incidentes à ce sommet. Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes, c'est-à-dire le nombre de voisins directs de ce sommet.

Graphes orientés et non orientés, matrices d'adjacence, listes d'adjacence, parcours BFS et DFS

Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub

Résumé

Un graphe est un ensemble de sommets reliés par des arêtes (non orienté) ou des arcs (orienté). Par exemple, un réseau social est un graphe non orienté où les sommets sont les utilisateurs et les arêtes les amitiés. Un plan de métro peut être modélisé par un graphe pondéré où les poids représentent les temps de trajet. On représente un graphe de deux manières : la matrice d'adjacence (tableau 2D de booléens ou entiers) ou les listes d'adjacence (dictionnaire associant à chaque sommet la liste de ses voisins). La matrice d'adjacence convient aux graphes denses, les listes d'adjacence aux graphes creux. Les parcours permettent de visiter tous les sommets accessibles depuis un sommet de départ.

Articles utiles

Spécialités

Bac NSI 2026 : comment réussir l'épreuve écrite et pratique

Questions fréquentes

Les points clés à retenir sur Graphes : représentation et parcours, extraits du quiz de révision.

Dans un graphe non orienté, la matrice d'adjacence est :

Réponse : Symétrique

Dans un graphe non orienté, si l'arête (i,j) existe, alors l'arête (j,i) aussi, donc M[i][j] = M[j][i] : la matrice est symétrique.

Quelle est la complexité mémoire d'une matrice d'adjacence pour n sommets ?

Réponse : O(n²)

La matrice d'adjacence est un tableau de taille n×n, soit O(n²) en mémoire, indépendamment du nombre d'arêtes.

Les listes d'adjacence sont préférées pour les graphes :

Réponse : Creux (peu d'arêtes)

Les listes d'adjacence occupent O(n + m) en mémoire, ce qui est bien plus efficace que O(n²) quand le graphe a peu d'arêtes (m << n²).

Le degré d'un sommet dans un graphe non orienté est :

Réponse : Le nombre d'arêtes incidentes à ce sommet

Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes, c'est-à-dire le nombre de voisins directs de ce sommet.

Résumé

Questions fréquentes

Les points clés à retenir sur Graphes : représentation et parcours, extraits du quiz de révision.

Dans un graphe non orienté, la matrice d'adjacence est :

Réponse : Symétrique

Dans un graphe non orienté, si l'arête (i,j) existe, alors l'arête (j,i) aussi, donc M[i][j] = M[j][i] : la matrice est symétrique.

Quelle est la complexité mémoire d'une matrice d'adjacence pour n sommets ?

Réponse : O(n²)

La matrice d'adjacence est un tableau de taille n×n, soit O(n²) en mémoire, indépendamment du nombre d'arêtes.

Les listes d'adjacence sont préférées pour les graphes :

Réponse : Creux (peu d'arêtes)

Les listes d'adjacence occupent O(n + m) en mémoire, ce qui est bien plus efficace que O(n²) quand le graphe a peu d'arêtes (m << n²).

Le degré d'un sommet dans un graphe non orienté est :

Réponse : Le nombre d'arêtes incidentes à ce sommet

Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes, c'est-à-dire le nombre de voisins directs de ce sommet.

Graphes : représentation et parcours

Résumé

Vocabulaire des graphes

Matrice d'adjacence

Listes d'adjacence

Comparaison et choix de représentation

Quiz - Graphes : représentation et parcours

Articles utiles

Questions fréquentes

Graphes : représentation et parcours

Résumé

Vocabulaire des graphes

Matrice d'adjacence

Listes d'adjacence

Comparaison et choix de représentation

Quiz - Graphes : représentation et parcours

Articles utiles

Questions fréquentes