Skip to main content

What are Graphs? – Part 3 DFS

· 2 min read
Strider

Hi, in the third part of my graph series, I want to talk about the search algorithms. We have programmed the graph in Python in the second part. Now it goes to the search algorithms. Each search algorithm will be discussed in separate posts.

First, let's get the graph in front of our eyes again.

dia.png

Our first search algorithm is the simple depth-first search. This should simply run from a selected start node, over the entire graph. Each node is to be visited during the run. Thereby a tree is spanned. Here, however, the weights are not yet considered. Here the depth-first search goes through all neighboring nodes of the current node.

The depth search marks all nodes as not visited. It starts at the start node and looks to see which visitable nodes it has as neighbors. The current node is marked as visited. Then all neighboring nodes are checked individually to find out which one has not been visited yet. This is very important to avoid loops.

As a diagram, the whole thing looks like this (node AA as start):

animation.gif

At blue markers, the search goes deeper and deeper. With all red crosses, it does not go further, because the nodes have already been visited. The go back, shown in green. He then always wanders back one node and looks which can still be visited, otherwise always one back to the start node. After that the search ends.

Extend our graph implementation​

Now we extend our class Graph by the depth-first search. I have implemented this recursively here.

def mstDFS(self, key):
    self.unvisitAllNodes()
    self.__mstDFS(key)

def __mstDFS(self, key):
    n = self.getNode(key)
    n.visit()

    for edge in n.getEdges():
        if not edge.getB().isVisited():
            print(edge.getA().getKey(), "--->", edge.getB().getKey(), "weight:", edge.getWeight())
    self.__mstDFS(edge.getB().getKey())

Here we see that all nodes are first marked as not visited. After that, the lower method is simply called, which starts at the start key. Now the current node is marked as visited. After marking, all neighboring nodes are determined and processed individually. If a node is present, which was not visited yet, this is output and processed in the next recursive call. That's it.

Funfact: Prolog works similarly with the evaluation.

I hope I was able to explain the depth search in a comprehensible way 😄