Graph Traversal

Here are some basic graph algoritms.

Breadth First Search

def BFS(graph):
    visited = []
    queue = []
    queue.append(graph.get_vertex(0))
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.append(vertex)
            for neighbor in vertex.get_neighbors():
                queue.append(neighbor)
    return visited

Depth First Search

def DFS(graph):
    def DFS_helper(vertex, visited):
        visited.append(vertex)
        for neighbor in vertex.get_neighbors():
            if neighbor not in visited:
                DFS_helper(neighbor, visited)
    visited = []
    DFS_helper(graph.get_vertex(0), visited)
    return visited

def DFS_iterative(graph):
    visited = []
    stack = []
    stack.append(graph.get_vertex(0))
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.append(vertex)
            for neighbor in vertex.get_neighbors():
                stack.append(neighbor)
    return visited