Merge pull request thuva4#257 from bugov/master

thuva4 · web-flow · commit 700dae18493d · 2017-10-18T21:12:40.000+05:30
DepthFirstSearch in Python thuva4#248
diff --git a/DepthFirstSearch/Python/dfs_recursive.py b/DepthFirstSearch/Python/dfs_recursive.py
@@ -0,0 +1,35 @@
+#!/usr/bin/env python3
+# Naive recursive implementation of DFS on ordered graphs
+from collections import defaultdict
+import sys
+
+
+def dfs(node, adjacency_lists, strategy, visited=None):
+    if not visited:
+        visited = set()
+    
+    visited.add(node)
+    strategy(node)
+    
+    for adj_node in adjacency_lists[node]:
+        if adj_node in visited:
+            continue
+        
+        dfs(adj_node, adjacency_lists, strategy, visited)
+
+
+if __name__ == '__main__':
+    start_from = next(sys.stdin).strip()
+    adjacency = defaultdict(list)
+
+    for line in sys.stdin:
+        line = line.strip()
+        
+        if not line:
+            continue
+
+        from_, to = line.split()
+        adjacency[from_].append(to)
+
+    dfs(start_from, adjacency, lambda x: print(x))
+
diff --git a/DepthFirstSearch/Python/in.txt b/DepthFirstSearch/Python/in.txt
@@ -0,0 +1,17 @@
+0
+0 1
+0 6
+0 8
+1 4
+1 6
+1 9
+2 4
+2 6
+3 4
+3 5
+3 8
+4 5
+4 9
+7 8
+7 9
+
diff --git a/README.md b/README.md
@@ -17,7 +17,7 @@ Borwein's Algorithm | :+1: |  |  |  | :+1: |  |  |  | ||
 BubbleSort | :+1: | :+1: | :+1: | :+1: | :+1: | :+1: |  | :+1: | :+1: |
 Conjugate Gradient |  |  |  |  | :+1: |  |  |  | ||
 CountingSort | :+1: | :+1: |  |  | :+1: |  |  |  | |
-DepthFirstSearch | :+1: |  |  |  | :+1: |  |  |  | |
+DepthFirstSearch | :+1: | :+1: |  |  | :+1: |  |  |  | |
 Dijkstra's  | :+1: | :+1: |  |  | :+1: |  |  |  | |
 Doomsday | :+1: | :+1: |  |  |  | :+1: |  |  |  | :+1: | :+1:
 ElevatorAlgorithm | :+1: |  |  |  |  |  |  |  |  

-Original file line number
+Diff line change
@@ @@ -0,0 +1,17 @@ @@
 +0
 +0 1
 +0 6
 +0 8
 +1 4
 +1 6
 +1 9
 +2 4
 +2 6
 +3 4
 +3 5
 +3 8
 +4 5
 +4 9
 +7 8
 +7 9
++