J'ai appris les bases des structures de données de graphe. Maintenant, je veux implémenter toutes les structures/algorithmes/opérations qui peuvent être effectuées sur les graphes.Implémentation de la structure de données de graphe en C
S'il vous plaît partager quelques liens utiles où je peux obtenir commencé à faire des implémentations de graphique en C.
adjacency list et adjacency matrix sont les deux alternatives les plus classiques pour la mise en œuvre des graphiques. Je ne suis pas sûr s'il y a beaucoup d'exemples de chacun en ligne en C, mais here est un pour la représentation de matrice d'adjacence.
Merci Alex .... On dirait plutôt bon exemple ... Je vais travailler sur ..... mais il y a un article sur la liste d'adjacence avec une mise en œuvre incomplète http://www.cs.bu.edu/teaching/c/graph/linked/........ Mais je trouve qu'il est difficile de commencer ... Pouvez-vous nous aider ... J'ai compris les structures, mais maintenant si nous voulons insérer un sommet ou un bord .. etc .... – AGeek
@AGeek, dans adj matrix: insère le bord (entre les sommets existants I et J) → il suffit de définir la matrice 'I [J] = 1'; insère le nouveau sommet N + 1 → alloue le nouveau N + 1 par la matrice N + 1 et copie l'ancien sur le remplissage avec la nouvelle ligne et la colonne des 0. adj liste: dans adj matrice: insert bord (entre les sommets existants I et J) → ajouter J à la liste adj de I; insérer un nouveau sommet → l'ajouter à la liste des sommets existants. –
Le livre, The Algorithm Design Manual [PDF] a un code C implémentant un graphique. Pour un manuel plus complet sur les graphes et les algorithmes apparentés (DFS, Bellman-Ford, etc.), Introduction to Algorithms (excellent) a des implémentations de pseudo-codes que vous pourriez implémenter.
La liste d'adjacence standard ou les représentations matricielles mentionnées par Alex sont décrites dans les deux.
Avez-vous essayé d'utiliser CGAL? – Borealid