Graphs

graph.py

#TODO: bidirectional bfs/dfs, 
directedGraph = {0: [1,4], 1: [3], 2: [], 3: [0,1,4], 4: [0,3]}
undirectedGraph = {0: [1,4], 1: [0,3], 2: [], 3: [1,4], 4: [0,3]}
completeGraph = {0:[1,2,3], 1:[0,2,3], 2:[0,1,3], 3:[0,1,2]}

def bfs(graph, start, path=[]):
    queue = [start]
    while queue:
        visited = queue.pop(0)
        if visited not in path:
            path += [visited]
            if visited in graph:
                queue += graph[visited]
    return path

def dfs(graph, start, path=[]):
    queue = [start]
    while queue:
        visited = queue.pop(0)
        if visited not in path:
            path += [visited]
            if visited in graph:
                queue = graph[visited] + queue
    return path

def isComplete(graph):
    elements=[]
    for x in graph:
        elements.append(x)
    elements.sort()
    for x in elements:
        y = graph[x] + [x]
        y.sort()
        if y != elements:
            return False
    return True

print isComplete(directedGraph)
print isComplete(completeGraph)