Simple Graph Algos

graphs.py

from collections import deque
from sys import maxint as MAXINT

# Breadth first search
def bfs(graph, start):
    explored, queue = set([start]), deque([start])
    while len(queue):
        vertex = queue.popleft()
        yield vertex
        for neighbor in graph[vertex]:
            if neighbor not in explored:
                explored.add(neighbor)
                queue.append(neighbor)

# shortest path for start to end in a graph
# using BFS. Useful when all edge lengths are same or 1.
def stortest_path(start, graph, end):
    explored, queue = set([start]), deque([start])
    distance = {n: MAXINT for n in graph}
    distance[start] = 0
    while len(queue):
        v = queue.popleft()
        for n in graph[v]:
            if n not in explored:
                distance[n] = distance[v] + 1
                explored.add(n)
                queue.append(n)
    return distance


# depth first search
def dfs(graph, start):
    explored = set()
    def _loop(s):
        if s in explored:
            return
        yield s
        explored.add(s)
        for n in graph[s]:
            if n not in explored:
                for elem in _loop(n):
                    yield elem
    return _loop(start)

# Topological sort
def topo(g):
    explored, order = set([]), deque()
    def dfs(s):
        if s in explored:
            return False
        explored.add(s)
        for n in g[s]:
            if n not in explored:
                dfs(n)
        order.appendleft(s)
    for n in g:
        if n not in explored:
            dfs(n)
    return order


if __name__ == "__main__":
    graph = {
        "a": ["c", "b"],
        "b": ["c"],
        "c": ["d"],
        "d": ["b", "f"],
        "e": ["d", "f"],
        "f": ["e"]
    }
    bfs(graph, "a")
    print
    dfs(graph, "a")
    print 
    topo(graph, "a")