Property |
Value |
dbo:abstract
|
- Les algorithmes de connexité permettent de déterminer rapidement si deux sommets d'un graphe non orienté sont reliés par un chemin ou non, en créant un tableau de pointeurs qui implémente en fait une forêt d'arbres. Chaque arbre créé par l'algorithme correspond à une composante connexe du graphe : ainsi, deux sommets seront reliés par un chemin du graphe si et seulement s'ils appartiennent au même arbre. La vérification se résume à la comparaison des racines des arbres respectifs. Dans le cas d'un graphe fixé à l'avance, cet algorithme est moins efficace que l'algorithme de parcours en largeur et l'algorithme de parcours en profondeur, qui permettent de répondre à ce type de requête en temps constant après un prétraitement linéaire. Cependant, il est utile dans le cas d'un graphe construit de façon incrémentale. (fr)
- Les algorithmes de connexité permettent de déterminer rapidement si deux sommets d'un graphe non orienté sont reliés par un chemin ou non, en créant un tableau de pointeurs qui implémente en fait une forêt d'arbres. Chaque arbre créé par l'algorithme correspond à une composante connexe du graphe : ainsi, deux sommets seront reliés par un chemin du graphe si et seulement s'ils appartiennent au même arbre. La vérification se résume à la comparaison des racines des arbres respectifs. Dans le cas d'un graphe fixé à l'avance, cet algorithme est moins efficace que l'algorithme de parcours en largeur et l'algorithme de parcours en profondeur, qui permettent de répondre à ce type de requête en temps constant après un prétraitement linéaire. Cependant, il est utile dans le cas d'un graphe construit de façon incrémentale. (fr)
|
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 9405 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-fr:wikiPageUsesTemplate
| |
dct:subject
| |
rdfs:comment
|
- Les algorithmes de connexité permettent de déterminer rapidement si deux sommets d'un graphe non orienté sont reliés par un chemin ou non, en créant un tableau de pointeurs qui implémente en fait une forêt d'arbres. Chaque arbre créé par l'algorithme correspond à une composante connexe du graphe : ainsi, deux sommets seront reliés par un chemin du graphe si et seulement s'ils appartiennent au même arbre. La vérification se résume à la comparaison des racines des arbres respectifs. (fr)
- Les algorithmes de connexité permettent de déterminer rapidement si deux sommets d'un graphe non orienté sont reliés par un chemin ou non, en créant un tableau de pointeurs qui implémente en fait une forêt d'arbres. Chaque arbre créé par l'algorithme correspond à une composante connexe du graphe : ainsi, deux sommets seront reliés par un chemin du graphe si et seulement s'ils appartiennent au même arbre. La vérification se résume à la comparaison des racines des arbres respectifs. (fr)
|
rdfs:label
|
- Algorithmes de connexité basés sur des pointeurs (fr)
- Algorithmes de connexité basés sur des pointeurs (fr)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageRedirects
of | |
is dbo:wikiPageWikiLink
of | |
is oa:hasTarget
of | |
is foaf:primaryTopic
of | |