Graph Traversal

# Adjacency Matrix : a matrix where 1 in a cell (i, j) means
# that there is an edge in the graph
# to use it in an algorithm find a valid vertex
def getGraphAM(edges, maxVertex):
    graph = [[0 for _ in range(maxVertex+1)] for _ in range(maxVertex+1)]
    for e in edges:
        graph[e[0]][e[1]] = 1
    return graph

# Adjacency List: list of vertices linked to list of vertices
# they are connected to
# use the first element as starting point in an algorithm
def getGraphAL(edges):
    graph = {}
    for e in edges:
        if not e[0] in graph:
            graph[e[0]] = []
        if not e[1] in graph:
            graph[e[1]] = []
        graph[e[0]].append(e[1])
    return graph

# Breadth First Search
# Explore the nearest neighbours first
def bfs(graph):
    
    root = list(graph.keys())[0]
    visited = {}
    color = {}
    queue = []

    queue.append(root)
    visited[root] = True
    color[root] = "grey"
    while len(queue) != 0:
        node = queue.pop(0)
        print(node)
        color[node] = "black"
        for child in graph[node]:
            if not child in visited:
                queue.append(child)
                visited[child] = True
                color[child] = "grey"

    print(visited)
    print(color)

# Depth First Search:
# Explore the fathest neighbours first
def dfs(graph):
    root = list(graph.keys())[0]
    visited = {}
    color = {}
    stack = []

    stack.append(root)
    visited[root] = True
    color[root] = "grey"
    while len(stack) != 0:
        node = stack.pop(-1)
        print(node)
        color[node] = "black"
        for child in graph[node]:
            if not child in visited:
                stack.append(child)
                visited[child] = True
                color[child] = "grey"

    print(visited)
    print(color)

if __name__ == "__main__":

    edges = [
        (1, 2),
        (2, 3),
        (2, 4),
        (4, 5),
    ]

    graph = getGraphAL(edges)
    print(graph)
    bfs(graph)
    dfs(graph)