Der beste Ansatz für Perkolation, Tiefensuche oder Vereinigungssuche?

Question

Welcher Ansatz ist am besten für das Perkolationsproblem geeignet, Tiefensuche zuerst oder Union finden? Was sind die zeitlichen Komplexitäten dieser beiden Algorithmen?

Answer 1

Sie können prüfen, diejenigen über Versickerungs Problem beim Lesen:

• http://introcs.cs.princeton.edu/java/24percolation/
• http://algs4.cs.princeton.edu/lectures/15UnionFind.pdf

Zuerst ein präsentieren den Problem und die Lösung unter Verwendung von dfs, zweiter mit gewerkschafts finden. Was die Laufzeit betrifft, würde es einen Benchmark benötigen, um den besten Weg zu finden.