Chapter 4 Trees and Graphs - 4.2
Problem 4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Classic homework in the course of graph theory. Either BFS or DFS can solve it.

from stack import *# Use adjacent list to represent the direct graphclass node:    def __init__(self, value = None):        self.value = value        self.next = Nonedef is_connected(graph_list, n1, n2):    # Use DFS    s = stack()    s.push(n1)    visited_list = []    while not s.is_empty():        n = s.pop()        visited_list.append(n)        out_point = graph_list[n].next        while out_point != None:            if out_point.value == n2:                return True            if out_point.value not in visited_list:                s.push(out_point.value)                visited_list.append(out_point.value)                break            out_point = out_point.next    return False# Test caseif __name__ == "__main__":    nodes = [node(i) for i in range(0, 6)]    nodes[0].next = node(1)    nodes[1].next = node(2)    nodes[2].next = node(3)    nodes[3].next = node(1)    nodes[3].next.next = node(2)    nodes[3].next.next.next = node(4)    nodes[5].next = node(4)    print is_connected(nodes, 0, 5)