Graphs

A graph is a collection of nodes called vertices that are connected to one another through edges.

Direction

Direction relates to the way vertices are connected with one another. If one vertex points to another vertex, but that other vertex does not necessarily point back, then we have a directed graph. If the connection goes both ways, then it is an undirected graph or a bi-directional graph.

Connection

A graph is considered connected when you can reach any vertex from any other vertex, or that there are no sets of vertices that are disconnected from the other vertices. A graph is considered strongly connected if all of the connections are bi-directional. Otherwise it is weakly connected.

Cycles

A cycle is when three or more vertices connect to form a closed loop. A graph that has no cycles is called a acyclic graph. A graph with at least one cycle is a cyclic graph. When traversing cyclic graphs you need to be careful to not get into an infinite loop, and instead mark nodes as visited.

Respresenting in code

Graphs are created using an adjacency list, or list of nodes with their adjacent nodes in another list.

class Vertex:
    def __init__(self, val, edges):
        self.var = val
        self.edges = list(edges) # Pointers

Complexity

The space complexity of a graph is O(v+e) where v is the number of vertices and e is the number of edges.

• Depth First Search Traversing: O(v+e)
• Bredth First Search Traversing: O(v+e)

Searching

To search a graph, you can use either DFS or BFS.

def DFS(graph, start):
    visited = set()  # keep track of the visited nodes
    stack = [start]  # use a stack to keep track of nodes to visit next

    while stack:
        node = stack.pop()  # get the next node to visit
        if node not in visited:
            visited.add(node)  # mark the node as visited
            print(node, end=' ')  # visit the node (print its value in this case)
            stack.extend(graph[node] - visited)  # add the node's neighbors to the stack, able to remove seen nodes in python for efficiency

def BFS(graph, start):
    visited = set()  # Keep track of the nodes that we've visited
    queue = [start]  # Use a queue to implement the BFS

    while queue:
        node = queue.pop()  # Dequeue a node from front of queue
        if node not in visited:
            visited.add(node)  # Mark the node as visited
            print(node, end=' ')  # Visit the node (print its value in this case)
            queue.extend(graph[node])  # Enqueue all neighbours

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}

DFS(graph, 'A')  # Output: A C F E B D
BFS(graph, 'A')  # Output: A B C D E F

Finding Paths

The below algorithms find all possible paths from the start to goal. This is assuming all edges have equal weights. If you need to find the shortest path with weighted graphs, you can add the weight to the tuple stored in the stack and find the shortest after all paths have been found.

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        (vertex, path) = stack.pop()
        # Again we are using python to subtract nodes already in the path
        # You could also check if next is not in the current path instead
        for next in graph[vertex] - set(path):
            # if next in path: continue
            if next == goal:
                yield path + [next]
            else:
                stack.append((next, path + [next]))

# Will always have shortest path first (if all edges are equal)
def bfs_paths(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graph[vertex] - set(path):
            # if next in path: continue
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))

Finding Shortest Path (Djikstra's Algorithm)

from collections import defaultdict

class Graph():
    def __init__(self):
        """
        self.edges is a dict of all possible next nodes
        e.g. {'X': ['A', 'B', 'C', 'E'], ...}
        self.weights has all the weights between two nodes,
        with the two nodes as a tuple as the key
        e.g. {('X', 'A'): 7, ('X', 'B'): 2, ...}
        """
        self.edges = defaultdict(list)
        self.weights = {}

    def add_edge(self, from_node, to_node, weight):
        # Note: assumes edges are bi-directional
        self.edges[from_node].append(to_node)
        self.edges[to_node].append(from_node)
        self.weights[(from_node, to_node)] = weight
        self.weights[(to_node, from_node)] = weight

def dijsktra(graph, initial, end):
    # shortest paths is a dict of nodes
    # whose value is a tuple of (previous node, weight)
    shortest_paths = {initial: (None, 0)}
    current_node = initial
    visited = set()

    while current_node != end:
        visited.add(current_node)
        destinations = graph.edges[current_node]
        weight_to_current_node = shortest_paths[current_node][1]

        for next_node in destinations:
            weight = graph.weights[(current_node, next_node)] + weight_to_current_node
            if next_node not in shortest_paths:
                shortest_paths[next_node] = (current_node, weight)
            else:
                current_shortest_weight = shortest_paths[next_node][1]
                if current_shortest_weight > weight:
                    shortest_paths[next_node] = (current_node, weight)

        next_destinations = {node: shortest_paths[node] for node in shortest_paths if node not in visited}
        if not next_destinations:
            return "Route Not Possible"
        # next node is the destination with the lowest weight
        current_node = min(next_destinations, key=lambda k: next_destinations[k][1])

    # Work back through destinations in shortest path
    path = []
    while current_node is not None:
        path.append(current_node)
        next_node = shortest_paths[current_node][0]
        current_node = next_node
    # Reverse path
    path = path[::-1]
    return path