0
\$\begingroup\$

Task: Do DFS traversal from a given given graph and print output.

Is this code the correct implementation of DFS traversal in Graph?

from collections import defaultdict

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def depth_first_search(self,node):
        visited = []
        stack = [node]

        while stack:

            node = stack.pop()
            if node not in visited:
                print node
                visited.append(node)

                for i in self.graph[node]:
                    stack.append(i)



G = Graph()
G.add_edge(1,2)
G.add_edge(1,4)
G.add_edge(1,5)
G.add_edge(2,3)
G.add_edge(3,5)
G.depth_first_search(1)
\$\endgroup\$
  • \$\begingroup\$ What is your expected behavior for cyclic graphs? You only have an acyclic graph in your example and DFS struggles with cycles on an arbitrary graph. \$\endgroup\$ – FirefoxMetzger Apr 16 '18 at 4:35
  • 1
    \$\begingroup\$ looks good, the only thing to improve is that you could define what node is and based on that you can add hashing algorithm for it. so then instead of having visited as list you could have it as a set. Which will improve your in lookup from O(N) to O(1) \$\endgroup\$ – Alex Apr 16 '18 at 13:51
1
\$\begingroup\$

Classic DFS doesn't use any pruning. That means you should not have a list of visited nodes; Hence, my question in the comments. This means that for cyclic graphs DFS does not terminate by default which is why people commonly do pruning on visited nodes; however, revisiting nodes may be wanted, e.g. "list all paths from edge 1 to edge 5". Making the choice of using visited not only makes your graph acyclic, but rather "tree-ifys" (technical term ;-) ) it.


Assuming visited is an okay thing to do you don't want to check if node not in visited: after poping an element but rather before you insert it. It saves you the overhead of appending and popping visited nodes which can be quite substantial.

Further, visited should be a set (as stated in @Alex 's comment).

It could also be a good idea to use an actual queue object, be that collections.deque (for FIFO / LIFO) or a queue.PriorityQueue. The latter will slightly reduce performance (insert from O(1) to O(log(queue_size))), but offers a lot of added flexibility and easy scalability to graph search.

Setting the priority to: 1/depth is DFS, depth is BFS, sum(depth) (or sum(transition costs)) is Dijkstra's search, expected_cost_to_goal is greedy search, sum(transition costs) + expected_cost_to_goal is A*. I think that's a really cool property.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.