Tout d'abord, j'ai eu une matrice de distance N * N, pour chaque point, j'ai calculé son voisin le plus proche, nous avons donc eu une matrice N * 2, il semble que ce em>:
0 -> 1
1 -> 2
2 -> 3
3 -> 2
4 -> 2
5 -> 6
6 -> 7
7 -> 6
8 -> 6
9 -> 8
3 Réponses :
L'algorithme le plus rapide pour la recherche de composants connectés attribués à une liste de bord est le Union-Trouvez algorithme: Pour chaque nœud, maintenez le pointeur sur un nœud dans le même ensemble, avec tous les bords convergeant sur le même nœud, si vous trouvez un chemin de longueur au moins 2, reconnectez le nœud inférieur vers le haut.
Ceci va certainement fonctionner. En temps linéaire: p> puisque la liste des bords forme déjà presque une arborescence union-trouver, il est possible de sauter la première étape: p> for each node
- if the node is not marked as collected
-- walk along the edges until you find an order-1 or order-2 loop,
collecting nodes en-route
-- reconnect all nodes to the end of the path and consider it a root for the set.
-- store all nodes in the set for the root.
-- update the set of non-empty sets.
-- mark all nodes as collected.
return the set of non-empty sets
Étant donné que chaque nœud n'a qu'un seul bord sortant, vous pouvez simplement traverser le graphique un bord à la fois jusqu'à ce que vous arriviez à un sommet que vous avez déjà visité. Un degré élevé de 1 signifie tout autre traversant à ce stade ne vous mènera que là où vous avez déjà été. Les sommets traversés dans ce chemin sont tous dans le même composant.
dans votre exemple: Vous pouvez visiter chaque noeud exactement une fois, alors le temps est O (n) . L'espace est O (n) car tout ce dont vous avez besoin est un identifiant de composant pour chaque nœud et une liste d'identifiants de composants.
En fait, mon exemple peut-être trop spécial pour votre idée, car il manque une sorte de fusion de fonctionnement. O (n) est juste le meilleur cas.
Si vous voulez le faire séquencialement, vous pouvez le faire à l'aide de la compression de l'union rapide et du chemin pondéré .complexity o (n + mlog (journal (n))). Vérifiez ce lien. Voici le pseudocode .honoring @pycho 's mots
` `
@reference https://www.cs.princeton.edu/~rs/algsds07 /01unionfind.pdf Si vous souhaitez trouver des composants connectés parallèles, la complexité asymptotique peut être réduite à O (journal (journal (n)) à l'aide d'un obstacle de pointeur et d'union rapide pondérée avec chemin compression. Vérifiez ce lien
C'est si gentil de votre part que vous avez partagé vos connaissances avec nous. Mais cela aurait été beaucoup mieux si vous aviez écrit toute la réponse par vous-même au lieu de donner des liens.
C'est super. :) Gardez un codage heureux souriant.