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)
