@@ -0,0 +1,2873 @@
+from __future__ import absolute_import%0Afrom __future__ import print_function%0Afrom __future__ import division%0A%0Afrom ds_stack import Stack%0A%0A%0Adef dfs(adjacency_dict, start_vertex):%0A    %22%22%22Depth First Search by Iteration using Stack.%22%22%22%0A    ls_stack = Stack()%0A    ls_stack.push(%5Bstart_vertex%5D)%0A    visited_set = set(%5Bstart_vertex%5D)%0A    %0A    while ls_stack.size() %3E 0:%0A        # Take top vertex as the next start vertex.%0A        path_ls = ls_stack.peek()%0A        vertex = path_ls%5B-1%5D%0A        print('vertex: %7B%7D'.format(vertex))%0A        yield vertex, path_ls%0A        neighbor_vertices = adjacency_dict%5Bvertex%5D%0A        if len(neighbor_vertices) %3E 0:%0A            neighbor_vertex = neighbor_vertices.pop()%0A            if neighbor_vertex not in path_ls:%0A                visited_set.add(neighbor_vertex)%0A                ls_stack.push(path_ls + %5Bneighbor_vertex%5D)%0A        else:%0A            ls_stack.pop()%0A%0Adef traverse_dfs(adjacency_dict, start_vertex, end_vertex):%0A    %22%22%22Traverse graph by Depth First Search by Iteration with Stack.%22%22%22%0A    connect_bool = False%0A    for vertex, path_ls in dfs(adjacency_dict, start_vertex):%0A        if vertex == end_vertex:%0A            connect_bool = True%0A            print(' -%3E '.join(path_ls))%0A            break%0A%0A    if not connect_bool:%0A        print('No path from %7B0%7D to %7B1%7D'.format(start_vertex, end_vertex))%0A%0A%0Adef dfs_recur(adjacency_dict, start_vertex, visited_set, discover_ls, finish_ls):%0A    %22%22%22Depth First Search by Recursion.%22%22%22%0A    visited_set.add(start_vertex)%0A    # path_ls.append(start_vertex)%0A    discover_ls.append(start_vertex)%0A    for neighbor_vertex in adjacency_dict%5Bstart_vertex%5D:%0A        if neighbor_vertex not in visited_set:%0A            dfs_recur(adjacency_dict, neighbor_vertex, visited_set, %0A                      discover_ls, finish_ls)%0A    finish_ls.insert(0, start_vertex)%0A%0Adef traverse_dfs_recur(adjacency_dict):%0A    %22%22%22Traverse graph by Depth First Search by Recursion.%0A%0A    To make sure all vertices in connected or disconnected graph%0A    are visited, we start from start_vertex to iterate all vertices.%0A    %22%22%22%0A    visited_set = set()%0A    # path_ls = %5B%5D%0A    discover_ls = %5B%5D%0A    finish_ls = %5B%5D%0A    for vertex in adjacency_dict:%0A        if vertex not in visited_set:%0A            dfs_recur(adjacency_dict, vertex, visited_set, discover_ls, finish_ls)%0A    print('discover_ls: %7B%7D'.format(discover_ls))%0A    print('finish_ls: %7B%7D'.format(finish_ls))%0A%0A%0Adef main():%0A    # Connected graph.%0A    conn_adjacency_dict = %7B%0A        'A': %5B'B', 'D'%5D,%0A        'B': %5B'C', 'D'%5D,%0A        'C': %5B%5D,%0A        'D': %5B'E'%5D,%0A        'E': %5B'B', 'F'%5D,%0A        'F': %5B'C'%5D,%0A    %7D%0A%0A    # print('For dfs by iteration:')%0A    # start_vertex = 'A'%0A    # end_vertex = 'F'%0A    # traverse_dfs(conn_adjacency_dict, start_vertex, end_vertex)%0A%0A    print('For dfs by recursion:')%0A    traverse_dfs_recur(conn_adjacency_dict)%0A%0Aif __name__ == '__main__':%0A    main()%0A

Rename to alg_depth_first_search_bak.py for back up naive version