Why is it taking so long for the depth-first traversal to take place?

Question

Python

I want to make a fill on the image, as in paint. To paint over all pixels of the same color as on the selected one (so far I am comparing only one channel). On a 30*30 image, everything works well.

source

Result

But as soon as I want to do the same with a 480*740 image, the process takes a very long time. I checked the execution speed, it is constant, each vertex is processed the same amount of time.

Here is the bypass itself, without recursion:

The code

def dfs_not_recursion(self):        
        while (self.stack != []):            
            peak_vertex = self.stack.pop()
                      
            if (peak_vertex is not None):
                if (not self.is_visited_boolean(peak_vertex)):
                    self.visited_boolean[peak_vertex.y][peak_vertex.x] = True
                    
                    if (self.img[peak_vertex.y][peak_vertex.x][0] == self.start_vertex.color[0]):
                        self.img_draw[peak_vertex.y][peak_vertex.x] = self.GREEN

                        neighbours = peak_vertex.get_neighbours(self.img)

                        for i in neighbours:
                            self.stack.append(i)

The img image is the source, img_draw is the one to draw on.

Why does it take milliseconds in paint to process a large image, but here it takes minutes?

Answer 1

It's just that paint uses an efficient shading algorithm , and not depth-first crawling.
self.visited_boolean[peak_vertex.y][peak_vertex.x]
This is generally very long, there should be work with raw image lines