README.md

Graphs

• graph = nodes + edges
• describes relations between things
• types: directed; undirected
• represented as: adjacency list or adjacency matrix

An example fo adjacency list:

{
    a: [b,c],
    b: [d],
    c: [e],
    d: [],
    e: [b],
    f: [d]
}

• Graphs can be traversed in 2 ways: depth-first and breadth-first

Depth-first traversal

• Uses a stack

Iterative code

def depth_first_traversal(graph, source):
    stack = [ source ]

    while stack:
        current = stack.pop()
        print(current)

        for neighbor in graph[current]:
            stack.append(neighbor)

Recursive code

def depth_first_traversal(graph, source):
    print(source)

    for neighbor in graph[source]:
        depth_first_traversal(graph, neighbor)

Breadth-first traversal

• Uses a queue

def breadth_first_traversal(graph, source):
    queue = [ source ]

    while queue:
        current = queue.pop(0)
        print(current)

        for neighbor in graph[current]:
            queue.append(neighbor)

Fundamental coding problems

• Has Path
• Undirected Path
• Connected Components Count
• Largest Component
• Shortest Path
• Island Count
• Minimum Island