Matrice d’adjacence – Représentation de graphes
Un graphe est une structure composée de sommets (nœuds) et d’arêtes reliant ces sommets. Les graphes peuvent servir à modéliser des relations entre différents objets ou à représenter un réseau. Ils sont souvent utilisés pour illustrer les connexions entre des villes, des personnes ou même des entités abstraites.
Les graphes peuvent être soit dirigés, soit non dirigés :
- Graphes dirigés : Toutes les arêtes possèdent une direction, ce qui signifie qu’il peut exister une « route » partant d’un sommet et allant vers un autre, sans qu’il y ait forcément un chemin retour. C’est un peu comme une route à sens unique. Toutefois, il est possible d’avoir les deux sens dans un graphe dirigé ; ils sont simplement marqués explicitement (comme la connexion entre les sommets 5 et 8 dans l’exemple).
Yet, it’s possible to have both directions in a directed graph. They are just explicitly marked for that (the connection between vertices 5 and 8 in the graph).
- Graphes non dirigés : Les arêtes n’ont pas de direction définie. Si une arête relie deux sommets, ces sommets sont alors accessibles l’un depuis l’autre (dans les deux sens).
L’une des façons de représenter un graphe est la matrice d’adjacence. Il s’agit d’une matrice carrée décrivant l’ensemble du graphe. Chaque ligne et chaque colonne correspondent à un sommet. Si une arête relie deux sommets, l’entrée correspondante dans la matrice sera égale à 1. Sinon, elle sera égale à 0.
Une matrice d’adjacence pour le graphe dirigé présenté plus haut pourrait ressembler à ceci :
g = [
# 1 2 3 4 5 6 7 8
[0, 1, 0, 1, 0, 0, 0, 0], # connexions sortant du sommet 1
[0, 0, 0, 0, 1, 0, 0, 0], # connexions sortant du sommet 2
[0, 1, 0, 0, 0, 0, 0, 0], # connexions sortant du sommet 3
[0, 0, 0, 0, 0, 0, 0, 0], # connexions sortant du sommet 4
[0, 0, 0, 0, 0, 1, 0, 1], # connexions sortant du sommet 5
[0, 0, 0, 1, 0, 0, 1, 0], # connexions sortant du sommet 6
[0, 0, 0, 0, 0, 0, 0, 1], # connexions sortant du sommet 7
[0, 0, 0, 0, 1, 0, 0, 0], # connexions sortant du sommet 8
]Notez que lorsqu’une arête est bidirectionnelle, les deux sommets concernés ont chacun un 1 à la position appropriée.
Remarquez également que nous avons modifié l’indexation des sommets. Ainsi, si nous accédons à
g[0], nous obtenons toutes les connexions du sommet indexé par 1. Nous aurions pu utiliser 9 lignes et 9 colonnes à la place de 8 pour maintenir une correspondance exacte avec la numérotation de l’image, mais c’est à vous de voir 😎.Défi : Arêtes vers matrice d’adjacence
Étant donné un graphe ayant
v sommets et e arêtes, vous devez produire sa matrice d’adjacence.Entrée
La première ligne de l’entrée contient deux entiers
v (1 ≤ v ≤ 1000) et e (1 ≤ e ≤ 100 000).Les
e lignes suivantes contiennent des paires d’entiers v1, v2 (1 ≤ v1, v2 ≤ v), indiquant que le sommet v1 est connecté au sommet v2 et réciproquement.Sortie
Le programme doit afficher la matrice d’adjacence du graphe. Les valeurs dans chaque ligne doivent être séparées par un espace.
Exemples
Entrée | Sortie |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 0 1 0 1 0 0 0 0
1 0 1 0 1 0 0 0
0 1 0 0 0 0 0 0
1 0 0 0 0 1 0 0
0 1 0 0 0 1 0 1
0 0 0 1 1 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 1 0 1 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB