Structure des données graphiques et Algorithms (Exemple)
Sarah Chen
Qu’est-ce qu’un graphique dans la structure des données ?
Un graphique est une structure de données non linéaire composée de sommets et d'arêtes, où les sommets contiennent des informations ou des données, et les arêtes fonctionnent comme un lien entre une paire de sommets.
Il est utilisé pour résoudre de vrais problèmes tels que trouver le meilleur itinéraire vers le lieu de destination et l'itinéraire pour les télécommunications et les réseaux sociaux. Les utilisateurs sont considérés comme un nœud dans le graphique et les fils sont les bords reliant les utilisateurs.
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 :
C'est un simple graphe non orienté (un type de graphe). Ici, l'ensemble des sommets est : {A, B, C,D,E,F}. Deux sommets créent une arête. Par exemple, A et B sont liés par une arête. Cependant, A et F ne sont liés à aucune arête.
Terminologies graphiques dans la structure des données
Voici quelques termes importants utilisés dans la structure des données graphiques :
| Long | Description |
|---|---|
| Sommet | Tout é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 de connexion entre deux nœuds ou sommets sont appelés arête (Arc). Il a deux extrémités et est représenté par (startingVertex,endingVertex). |
| Bord non orienté | C'est un bord bidirectionnel. |
| Bord dirigé | C'est un bord unidirectionnel. |
| Bord pondéré | Un avantage avec de la valeur. |
| Degré | Dans Graph, le nombre d’arêtes connectées à un sommet est appelé un 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é | Les sommets sont dits adjacents si une arête est connectée. |
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
Applications de la structure des données graphiques
Un graphique a de nombreux cas d’utilisation. Il existe de nombreux algorithmes qui utilisent beaucoup les graphiques. Voici quelques-unes des applications du Graph :
- Google Maps utilise des graphiques pour trouver l'intersection de deux routes et calculer la distance entre deux emplacements.
Par exemple, Dijkstra, pour trouver la distance la plus courte entre l'emplacement source et l'emplacement de destination. - Facebook utilise Graphs pour trouver l'ami commun des utilisateurs. Son algorithme considère chaque utilisateur comme un nœud d'un graphe.
- Pour l'allocation des ressources, DAG (Direct Acyclic Graph) est utilisé. Il vérifie la dépendance des ressources.
- Le moteur de recherche Google utilise des graphiques pour créer le classement des sites Web.
- Un dispositif de cartographie utilise la structure de données graphique.
- Toupie et le protocole de t utilise le graphique pour connaître le chemin du chemin de destination.
