Structure des données graphiques et Algorithms (Exemple)
Sarah Chen
⚡ Résumé intelligent
Une structure de données de type graphe est un ensemble non linéaire de sommets et d'arêtes, chaque arête reliant deux sommets. Les graphes modélisent des réseaux du monde réel tels que les cartes, les réseaux sociaux et les pages web, et prennent en charge de nombreux algorithmes puissants.
Qu’est-ce qu’un graphique dans la structure des données ?
Un graphe est une structure de données non linéaire composée de sommets et d'arêtes, les sommets contenant les informations ou les données, et les arêtes servant de lien entre deux sommets.
Il sert à résoudre des problèmes concrets, comme trouver le meilleur itinéraire pour atteindre une destination ou optimiser le réseau pour les télécommunications et les réseaux sociaux. Les utilisateurs sont représentés par des nœuds dans le graphe, et les liens entre eux par des arêtes.
Si les arêtes sont représentées par E et les sommets par V, alors le graphe G peut être écrit comme l'ensemble des sommets et des arêtes, tel que G (V, E).
Exemple de graphique dans la structure de données
Voici un exemple simple de structure de données graphique :
Il s'agit d'un graphe simple non orienté (un type de graphe). L'ensemble des sommets est : {A, B, C, D, E, F}. Deux sommets forment une arête. Par exemple, A et B sont reliés par une arête. En revanche, A et F ne sont reliés par aucune arête.
Terminologies graphiques dans la structure des données
Voici quelques termes importants utilisés dans la structure de données graphiques :
| Long | Description |
|---|---|
| Sommet | Chaque élément de données est appelé un sommet ou un nœud. Dans l'image ci-dessus, A, B, C, D et E sont les sommets. |
| Bord (Arc) | Les liens reliant deux nœuds ou sommets sont appelés une arête (arc). Elle possède deux extrémités et est représentée par (sommet de départ, sommet d'arrivée). |
| Bord non orienté | C'est un bord bidirectionnel. |
| Bord dirigé | C'est un bord unidirectionnel. |
| Bord pondéré | Une arête portant une valeur. |
| Degré | Dans un graphe, le nombre d'arêtes connectées à un sommet est appelé son degré. |
| Diplôme | Le nombre total d’arêtes entrantes connectées à un sommet. |
| Degré supérieur | Le nombre total d’arêtes sortantes connectées à un sommet. |
| Auto-boucle | Une arête est appelée auto-boucle si ses deux extrémités coïncident. |
| Proximité | Deux sommets sont dits adjacents s'il existe une arête qui les relie. |
Types de graphiques dans la structure des données
Voici la liste des plus courants types de graphiques dans la structure de données:
- Graphique dirigé
- Graphe non orienté
- Graphique pondéré
- Graphique bidirectionnel
- Graphique infini
- Graphique nul
- Graphique trivial
- Graphique multiple
- Graphique complet
- Graphique connecté
- Graphique cyclique
- Graphe acyclique dirigé (DAG)
- Graphique cyclique
- Graphique bipartite
- Graphique d'Euler
- Graphique de Hamilton
Comment représenter un graphe dans une structure de données ?
Un graphe est généralement stocké en mémoire selon l'une des deux représentations suivantes. Ce choix influe sur la quantité de mémoire utilisée par le graphe et sur la vitesse d'exécution des opérations courantes.
- Matrice d'adjacence : Un tableau bidimensionnel V × V où la cellule [i][j] vaut 1 (ou le poids de l'arête) si une arête existe entre le sommet i et le sommet j, et 0 sinon. Il permet une recherche d'arête en O(1) mais utilise un espace mémoire de O(V²), ce qui le rend idéal pour les graphes denses.
- Liste d'adjacence : Un tableau de listes où chaque sommet stocke une liste de ses sommets voisins. Il utilise un espace mémoire de O(V + E) et est efficace pour les graphes creux, ce qui explique pourquoi la plupart des graphes réels l'utilisent.
Vous pouvez en savoir plus à ce sujet dans le liste d'adjacence et représentation matricielle d'un graphe tutoriel.
Applications de la structure des données graphiques
Les graphes ont de nombreuses applications. De nombreux algorithmes les utilisent. Voici quelques exemples :
- Google Les cartes utilisent des graphiques pour trouver l'intersection de deux routes et calculer la distance entre deux points. Par exemple, Dijkstra, pour trouver la distance la plus courte entre le lieu de départ et le lieu d'arrivée.
- Facebook utilise des graphes pour trouver les amis communs des utilisateurs. Son algorithme considère chaque utilisateur comme un nœud d'un graphe.
- Pour l'allocation des ressources, on utilise un DAG (graphe acyclique orienté). Celui-ci vérifie la dépendance des ressources.
- Le Google Les moteurs de recherche utilisent des graphiques pour établir le classement des sites web.
- Une carteping L'appareil utilise la structure de données graphiques.
- A Toupie et son protocole utilise le graphe pour apprendre le chemin vers la destination.
