Merge pull request nryoung#39 from lcheung90/dfs

nryoung · nryoung · commit bf1415c7151d · 2013-03-10T12:58:19.000-07:00
Implement Depth-First-Search algorithm
diff --git a/algorithms/searching/depth_first_search.py b/algorithms/searching/depth_first_search.py
@@ -0,0 +1,25 @@
+"""
+    depth_first_search.py
+
+    Recursive implementation of DFS algorithm on a graph.
+
+    Depth First Search Overview:
+    ------------------------
+    Used to traverse trees, tree structures or graphs.
+    Starts at a selected node (root) and explores the branch
+    as far as possible before backtracking.
+
+    Time Complexity: O(E + V)
+        E = Number of edges
+        V = Number of vertices (nodes)
+
+    Pseudocode: https://en.wikipedia.org/wiki/Depth-first_search    
+"""
+def dfs(graph,start,path = []):
+    if start not in graph or graph[start] == None or graph[start] == []:
+        return None
+    path = path + [start]
+    for edge in graph[start]:
+        if edge not in path:
+            path = dfs(graph, edge,path)
+    return path
diff --git a/algorithms/tests/test_searching.py b/algorithms/tests/test_searching.py
@@ -1,6 +1,6 @@
 """ Unit Tests for searching """
 import unittest
-from ..searching import binary_search, kmp_search, rabinkarp_search, bmh_search
+from ..searching import binary_search, kmp_search, rabinkarp_search, bmh_search, depth_first_search
 
 
 class TestBinarySearch(unittest.TestCase):
@@ -69,3 +69,66 @@ def test_bmhsearch(self):
         rv2 = bmh_search.search(self.string, "ABCDER")
         self.assertIs(rv1[0], 9)
         self.assertFalse(rv2)
+
+class TestDepthFirstSearch(unittest.TestCase):
+    """
+    Tests DFS on a graph represented by a adjacency list
+    """
+
+    def test_dfs(self):
+        self.graph = {'A': ['B','C','E'],
+                      'B': ['A','D','F'],
+                      'C': ['A','G'],
+                      'D': ['B'],
+                      'F': ['B'],
+                      'E': ['A'],
+                      'G': ['C']}
+        rv1 = depth_first_search.dfs(self.graph, "A")
+        rv2 = depth_first_search.dfs(self.graph, "G")
+        rv1e = depth_first_search.dfs(self.graph, "Z")
+        self.assertEqual(rv1, ['A', 'B', 'D', 'F', 'C', 'G', 'E'])
+        self.assertEqual(rv2, ['G', 'C', 'A', 'B', 'D', 'F', 'E'])
+        self.assertEqual(rv1e, None)
+        self.graph = {1:[2,3,4],
+                      2:[1,6,10],
+                      3:[1,5,10],
+                      4:[1,10,11],
+                      5:[3,10],
+                      6:[2,7,8,9],
+                      7:[6,8],
+                      8:[6,7],
+                      9:[6,10],
+                      10:[3,5,9,12],
+                      11:[4],
+                      12:[10]}
+        rv3 = depth_first_search.dfs(self.graph,1)
+        rv4 = depth_first_search.dfs(self.graph,5)
+        rv5 = depth_first_search.dfs(self.graph,6)
+        rv2e = depth_first_search.dfs(self.graph,99)
+        self.assertEqual(rv3, [1, 2, 6, 7, 8, 9, 10, 3, 5, 12, 4, 11])
+        self.assertEqual(rv4, [5, 3, 1, 2, 6, 7, 8, 9, 10, 12, 4, 11])
+        self.assertEqual(rv5, [6, 2, 1, 3, 5, 10, 9, 12, 4, 11, 7, 8])
+        self.assertEqual(rv2e, None)
+        self.graph = {1:[2,3,4,5,6],
+                     2:[1,4,7,8,9],
+                     3:[1,10],
+                     4:[1,2,11,12],
+                     5:[1,13,14,15],
+                     6:[1,15],
+                     7:[2],
+                     8:[2],
+                     9:[2,10],
+                     10:[3,9],
+                     11:[4],
+                     12:[4],
+                     13:[5],
+                     14:[5],
+                     15:[5,6]}
+        rv6 = depth_first_search.dfs(self.graph,1)
+        rv7 = depth_first_search.dfs(self.graph,10)
+        rv8 = depth_first_search.dfs(self.graph,5)
+        rv3e = depth_first_search.dfs(self.graph,-1)
+        self.assertEqual(rv6, [1, 2, 4, 11, 12, 7, 8, 9, 10, 3, 5, 13, 14, 15, 6])
+        self.assertEqual(rv7, [10, 3, 1, 2, 4, 11, 12, 7, 8, 9, 5, 13, 14, 15, 6])
+        self.assertEqual(rv8, [5, 1, 2, 4, 11, 12, 7, 8, 9, 10, 3, 6, 15, 13, 14])
+        self.assertEqual(rv3e, None)
