La dernière structure de données que nous étudierons dans ce cours d'instruction est les graphiques. Les graphiques sont semblables aux arbres sauf que, ils n'ont pas autant de restrictions. Dans le cours d'instruction précédent, nous avons vu que chaque arbre a un noeud de racine, et tous autres noeuds dans l'arbre sont des enfants d'un noeud perticular. Nous avons également vu que les noeuds peuvent avoir beaucoup d'enfants mais seulement un parent. Quand nous détendons ces restrictions, nous obtenons la structure de données de graphique. La représentation logique d'un graphique typique pourrait sembler quelque chose comme la figure montrée ci-dessous :
Noter que notre graphique n'a aucun noeud de racine comme la structure de données d'arbre. Au lieu de cela, n'importe quel noeud peut être relié à n'importe quel autre noeud dans le graphique. Les noeuds n'ont aucun rapport clair de parent-enfant comme nous voyions dans l'arbre. Au lieu de cela des noeuds s'appellent comme voisins s'ils sont reliés par un bord. Par exemple, le noeud A ci-dessus a trois voisins : B, C, et D.
Il n'est pas difficile d'imaginer comment la structure de données de graphique pourrait être utile pour représenter les données. Peut-être chacun des noeuds ci-dessus pourrait représenter une ville et les bords reliant les noeuds pourraient représenter les routes. Ou nous pourrions employer un graphique pour représenter un réseau informatique où les noeuds sont des postes de travail et les bords sont les raccordements de réseau. Les graphiques ont tant d'applications dans l'informatique et les mathématiques que plusieurs algorithmes ont été écrits pour effectuer les opérations standard de graphique telles que rechercher le graphique et trouver le Shortest-Path entre les noeuds d'un graphique.
Maintenant que vous avez une idée fondamentale de la représentation logique des graphiques, jetons un coup d'oeil à l'one-way que des graphiques sont généralement représentés dans des ordinateurs. La représentation s'appelle une matrice de contiguîté, et elle emploie la rangée bidimensionnelle pour stocker les informations sur les noeuds de graphique. La matrice de contiguîté pour notre graphique est donnée ci-dessous.
|
|
-- |
1 |
1 |
1 |
-- |
-- |
1 |
-- |
1 |
-- |
1 |
-- |
1 |
1 |
-- |
-- |
-- |
-- |
1 |
-- |
-- |
-- |
1 |
1 |
-- |
1 |
-- |
1 |
-- |
-- |
-- |
-- |
-- |
1 |
-- |
-- |
|
Noter que la matrice montrée ci-dessus a six rangées et six colonnes marquées avec les noeuds du graphique. Nous marquons un « 1 » dans une cellule si là existe un bord de deux noeuds qui classent cette cellule. Par exemple, puisque nous avons un bord entre A et B, nous marquons un « 1 » dans les cellules classées par A et le B. Ces cellules sont identifiées par un fond gris-foncé dans la matrice de contiguîté. Avec notre matrice de contiguîté, nous pouvons représenter chaque bord possible que notre graphique peut avoir.
|
Keywords:
Graphs programming, graph c++, graph programming, graphing calculator programming, graphs in c++, linear programming graph, graphics programming, graphs tutorial, graphs java