Depth First Search (DFS) – Travel

• A traveral fnc that go through all nodes
• each node visit Once
• each edge examine Twice
• Time: O (|Vertices| + |Edges|)

Code:

# go through all nodes
# using recursion
# - each node visit Once
# - each edge examine Twice
def DFS_Recursion(graph, start):
    seen = {start}
    for adjacent_vertex in graph[start]:
        if adjacent_vertex not in seen:
            DFS_Recursion(graph,adjacent_vertex)

Depth First Search (DFS) – Finding Target

Throughout these algorithms I’m using a structure (path length, previous element, vertex) to represent the path. This has the effect of making a liked list of vertices in reverse order. This lets me display the path after running the algorithm. The important part is that the first argument is the path length upto that point, and the last argument is the vertex we’re looking at.

Code:

# Using Iteration
# input graph: the graph (can be weighted or unweighted)
# input start: the source vertex
# input end: the target vertex
# output a path from start to end
# struct push into the stack is path = (path length, previous element, vertex) 
def DFS_Iteration(graph, start, end):
    # We need a stack for DFS, so we'll use pythons double ended queue
    stack = deque()
    stack.append((0, None, start))

    # keep track of all of the vertices we've seen (avoids cycles)
    seen = {start}

    # look at the top of the stack
    # loop through all of the neighbors, and add them to the stack
    # repeat until we find the target
    while len(stack) > 0:
        path = stack.pop()
        (pathLen, prevVer, ver) = path

        # we found the target so return
        if ver == end:
            return path
		
		# for every adjacent vertex u
        for adjVer in graph[ver]:
            # if we haven't seen the vertex, then add it to the stack
            # update total path length
            # add to the seen list			
            if adjVer not in seen:
                stack.append((pathLen + graph[ver][adjVer], path, adjVer))
                seen.add(adjVer)

    # well, we failed, Let's return a null pointer
    # that always ends well
    return None

Breadth First Search (BFS) – Travel

• A traveral fnc that go through all nodes
• each node visit Once
• each edge examine Twice
• Time: O (|Vertices| + |Edges|)

Code:

def BFS2(graph, start):
    # now we'll treat the deque like a queue
    queue = deque()
    queue.append(start)

    seen = {start}

    # exactly the same as DFS, but we get each element from the bottom of the deque
    # instead of the top
    while len(queue) > 0:
        current_vertex = queue.popleft()

        for adjacent_vertex in graph[current_vertex]:
            # again don't add a vertex we've already seen
            if adjacent_vertex not in seen:
                queue.append( adjacent_vertex )
                seen.add(adjacent_vertex)

    return seen


# Another bfs, visit vertex in 1st loop, slower than the one above
# Difference: not adding first vertex to visited before loop
#
def BFS3(graph, start):
    visited = []                    # breadth first order list of visited vertices
    queue   = [start]               # a queue of vertices that we are waiting to visit
    while len(queue)>0:             # so long as there are vertices to visit ...
        v = queue.pop(0)            # ... take a vertex from front of the queue
        visited.append(v)           # ... add it to the visited list
        for w in graph[v]:          # ... add its unvisited neighbors to end of queue
            if w not in visited and w not in queue:
                queue.append(w)
    return visited

Breadth First Search (BFS) – Finding Target

Input taking a start vertex and a end vertex, then find a path from start to the end.

Code:

# input graph: the graph (can be weighted or unweighted)
# input start: the source vertex
# input end: the target vertex
# output a path from start to end that is the shortest length
# 
def BFS(graph, start, end):
    # now we'll treat the deque like a queue
    queue = deque()
    queue.append((0, None, start))

    seen = {start}

    # exactly the same as DFS, but we get each element from the bottom of the deque
    # instead of the top
    while len(queue) > 0:
        current_path = queue.popleft()
        (pathLen, last_path, current_vertex) = current_path

        # we found the end, return
        if current_vertex == end:
            return current_path

        for adjacent_vertex in graph[current_vertex]:
            # again don't add a vertex we've already seen
            if adjacent_vertex not in seen:
                queue.append((pathLen + graph[current_vertex][adjacent_vertex], current_path, adjacent_vertex))
                seen.add(adjacent_vertex)

    return None

Minimum Spanning Tree

Code:

# Prim's Algorithm
# 
# input graph: a weighted graph
# input start: the vertex to start the tree at
# output: the edges of a minimum spanning tree
def prim(graph, start):
    path = []
    vertex_count = 1
    visited = [start]
    while vertex_count < graph.order():
        least_edge = None
        # find a least edge
        for a_visited in visited:                           # loop every vetex in visited vertices
            for neighbor in graph[a_visited]:               # loop every neighbor for a vertex
                weight = graph[a_visited][neighbor]
                if (neighbor not in visited) and ((not least_edge) or (weight <least_edge[2])):
                    least_edge = (a_visited, neighbor, weight)
                    
        visited.append(least_edge[1])
        path.append(least_edge)
        vertex_count += 1
    
    return path

Finding Shortest Path

Code:

# input graph: the graph (must be weighted)
# input start: the source vertex
# input end: the target vertex
# output a path from start to end that is the shortest length
# 
def dijkstra(graph, start, end):
    # if the graph isn't weighted, then use BFS, it's faster
    if not graph.weighted:
        return BFS(graph, start, end)

    # python has heappush and heappop
    # which will treat an array like a heap
    # so, we basically get a priority queue for free
    heap = []
    heappush(heap, (0, None, start))

    # now, not only do we need to know if we've seen a vertex, but we need
    # to know the shortest path from s to t
    seen = {}
    seen[start] = 0

    # just like before, we keep removing vertices from the heap
    # we keep going until we find the target vertex
    while len(heap) > 0:
        path = heappop(heap)
        (pathLen, t, v) = path

        # we hit the end, so return
        if v == end:
            return path

        # for neighbor of v we need to check if we've seen it,
        # or, if we have seen it, we need to check if
        # we've found a shorter path
        #
        # pathLen + graph[v][u] is the new path from s -> u
        # seen[u] is the old path from s -> u
        for u in graph[v]:
            if u not in seen or pathLen + graph[v][u] < seen[u]:
                heappush(heap, (pathLen + graph[v][u], path, u))
                seen[u] = pathLen + graph[v][u] 

    # well, we failed, null pointer time!
    return None