Noms des algorithmes de parcours de graphes
Ce que je suis à la recherche d'une liste exhaustive de graphique de la traversée des algorithmes, avec une brève description de leur objet, comme un saut de point de départ pour des recherches sur eux. Jusqu'à présent, je suis au courant de:
- Dijkstra est - à source unique chemin le plus court
- Kruskal - trouve un minimum spanning tree
Quels sont les autres bien connus? Veuillez fournir une brève description de chaque algorithme pour chacune de vos réponses.
source d'informationauteur Ben Lakey
Vous devez vous connecter pour publier un commentaire.
le bien personnes connues sont :
de flux de réseau
Un peu hors du haut de ma tête:
Profondeur d'abord et en Largeur d'abord traversals, vraiment juste deux façons différentes de toucher tous les nœuds.
De Floyd-Warshall algorithme recherche les plus courts chemins entre toutes les paires de points (grand-theta)(v^3).
De l'algorithme de Prim est une alternative à Kruskal pour MST.
Il existe également des algorithmes pour trouver entièrement composantes connexes, qui sont des groupes de nœuds où vous pouvez obtenir auprès d'un membre dans le composant à un autre membre. Cette seule matière pour "les graphes orientés", où vous pouvez traverser une arête d'une seule direction.
Personnellement, je pense que le plus cool de l'extension de la théorie des graphes (pas exactement liées à votre question, mais si vous êtes intéressés à en apprendre plus sur les graphiques en général, c'est certainement utile de votre temps) les concepts de "flux réseaux": http://en.wikipedia.org/wiki/Flow_network . C'est une façon de calculer environ, disons, la quantité d'électricité que peut-on distribuer sur les maisons avec une variété de besoins en énergie et exigences, et une variété de stations d'énergie.
Algorithmes sur les graphes
Tous les algorithmes dans un endroit
Dictionnaire des algorithmes et structures de données:
Dictionnaire: http://xlinux.nist.gov/dads/
Par zone: http://xlinux.nist.gov/dads/termsArea.html
Par type de matière: http://xlinux.nist.gov/dads/termsType.html
Liste de toutes les implémentations dans les diff. langues: http://xlinux.nist.gov/dads/termsImpl.html