图的广度优先遍历和深度优先遍历

# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


def breadthFisrtSearch(source, target):
    if source == target:
        return
    queue = [source]
    is_visited = [source]
    prev = {}
    found = False

    result = []
    while len(queue):
        cur = queue.pop(0)
        for nei in cur.neighbors:
            if nei not in is_visited:
                prev[nei] = cur
                queue.append(nei)
                is_visited.append(nei)
                if nei.val == target.val:
                    p = nei
                    while p in prev:
                        result.append(p.val)
                        p = prev[p]
                    if p != nei:
                        result.append(p.val)
                    break
    print('result', result[::-1])
    

def depthFisrtSearch(source, target):
    found = [False]
    is_visited = []
    prev = {}

    dfs_helper(source, target, is_visited, prev, found)
    if found[0]:
        result = []
        p = target
        while p in prev:
            result.append(p.val)
            p = prev[p]
        if p != target:
            result.append(p.val)
        print('result', result[::-1])
    return False


def dfs_helper(s, target, is_visited, prev, found):
    if found[0]:
        return
    is_visited.append(s)
    if s.val == target.val:
        found[0] = True
        return
    for nei in s.neighbors:
        if nei not in is_visited:
            prev[nei] = s
            dfs_helper(nei, target, is_visited, prev, found)
    

if __name__ == '__main__':
    node1 = Node(1) 
    node2 = Node(2)  
    node3 = Node(3)   
    node4 = Node(4)   
    node5 = Node(5)             
    node6 = Node(6)   
    node1.neighbors = [node2, node3, node5]
    node2.neighbors = [node1, node4]
    node3.neighbors = [node1, node4, node5]
    node4.neighbors = [node2, node3, node6]
    node5.neighbors = [node1, node3, node6]
    node6.neighbors = [node4, node5]
    breadthFisrtSearch(node1, node6)


    depthFisrtSearch(node1, node6)