Python Graph Algorithms

in

To set the stage, what exactly is a graph? Well, it’s basically just a bunch of nodes (or vertices) connected by edges. You might be thinking, “Okay, but why would I want to use this in my code?” And that’s where the magic happens graphs can help us solve all sorts of problems!

For example, let’s say you have a social network and you want to find out who your closest friends are. You could create a graph with each person as a node and connect them if they know each other (represented by an edge). Then, using Python and some fancy algorithms, we can figure out which nodes are the most connected aka, our besties!

But before we get into all that, some of the basic graph concepts. First up is adjacency lists, which allow us to store information about each node’s connections in an easy-to-access format. Here’s what it might look like:

# Creating a graph using an adjacency list to store information about each node's connections
graph = {
    'Alice': ['Bob', 'Charlie'], # Alice is connected to Bob and Charlie
    'Bob': ['Alice', 'David'], # Bob is connected to Alice and David
    'Charlie': ['Alice', 'Eve'], # Charlie is connected to Alice and Eve
    'David': ['Bob'] # David is connected to Bob
}

In this example, we have a dictionary where each key is a node and the value is a list of its adjacent nodes. Pretty simple! Now let’s move on to some more advanced concepts like depth-first search (DFS) and breadth-first search (BFS). These algorithms allow us to traverse through our graph in different ways, which can be useful for all sorts of tasks from finding the shortest path between two nodes to identifying connected components.

So how do we implement these algorithms using Python? Well, let’s start with DFS. Here’s a basic example:

# This function implements Depth First Search (DFS) algorithm on a given graph
def dfs(graph, start):
    visited = set() # keep track of which nodes have been visited
    stack = [start] # initialize our stack with the starting node
    while stack:
        current_node = stack.pop() # pop the last item from the stack (our current node)
        if current_node not in visited: # check if we've already visited this node before
            print(current_node) # output the current node to our console
            for neighbor in graph[current_node]: # iterate through all of its adjacent nodes
                stack.append(neighbor) # add them to our stack (in reverse order)
            visited.add(current_node) # mark this node as visited so we don't revisit it later

# The function takes in two parameters: a graph and a starting node
# It keeps track of visited nodes using a set data structure
# It uses a stack to keep track of the nodes to be visited
# The while loop runs until the stack is empty, meaning all nodes have been visited
# The current node is popped from the stack and checked if it has been visited before
# If not, it is printed and its adjacent nodes are added to the stack
# The current node is then marked as visited to avoid revisiting it later

In this example, we start by initializing an empty set called `visited` and a list called `stack`. We then add the starting node to our stack (which is represented by the variable `start`) and begin iterating through each item in the stack. For each current node, we check if it’s already been visited using the `in` keyword. If not, we output its value to the console and add all of its adjacent nodes to the stack but this time, in reverse order! This is because DFS traverses our graph in a depth-first manner (hence the name), which means that it explores as far as possible along each branch before backtracking.

Now let’s move on to BFS. Here’s what that might look like:

# This function performs a breadth-first search on a given graph, starting from a specified starting node.
def bfs(graph, start):
    visited = set() # keep track of which nodes have been visited
    queue = [start] # initialize our queue with the starting node
    while queue: # continue until we've processed all items in the queue
        current_node = queue.pop(0) # remove and output the first item from the queue (our current node)
        if current_node not in visited: # check if we've already visited this node before
            print(current_node) # output the current node to our console
            for neighbor in graph[current_node]: # iterate through all of its adjacent nodes
                queue.append(neighbor) # add them to our queue (in forward order)
            visited.add(current_node) # mark this node as visited so we don't revisit it later

# The function takes in two parameters: a graph and a starting node.
# It keeps track of visited nodes using a set and initializes a queue with the starting node.
# It then continues to process the queue until it is empty.
# The current node is removed from the queue and checked if it has been visited before.
# If not, it is printed and its adjacent nodes are added to the queue in forward order.
# The current node is then marked as visited to avoid revisiting it later.

In this example, we start by initializing an empty set called `visited` and a list called `queue`. We then add the starting node to our queue (which is represented by the variable `start`) and begin iterating through each item in the queue. For each current node, we check if it’s already been visited using the `in` keyword. If not, we output its value to the console and add all of its adjacent nodes to the queue but this time, in forward order! This is because BFS traverses our graph in a breadth-first manner (hence the name), which means that it explores as far as possible along each branch before moving on to the next level.

And there you have it a brief introduction to Python’s graph algorithms using DFS and BFS! Of course, this is just scratching the surface of what’s possible with graphs in Python (there are many other algorithms out there), but hopefully this has given you a good starting point for your own explorations.

SICORPS