Graph Algorithms

Graphs are mathematical structures used to model paired relationships between objects. A graph in this context is composed of vertices (also called nodes or points) that are connected by edges (also called links or lines). Graph algorithms are mathematical procedures designed to solve problems involving graphs.

Importance of graph algorithms

Graphs are fundamentally important in many fields including computer science, biology, and social sciences. They help solve problems such as network flow, finding shortest paths, creating spanning trees, and much more. Let's explore some basic and advanced graph algorithms.

Basic definitions

Before getting into the algorithms it is essential to understand some basic terms related to graphs.

• Vertex (or node): The point in a graph where edges meet.
• Edge (or link): A connection between two vertices.
• Adjacency: Two vertices are adjacent if they are directly connected by an edge.
• Path: A sequence of edges that connects a sequence of vertices.
• Cycle: A path that starts and ends at the same vertex.
• Connected graph: A graph in which there is a path between every pair of vertices.

Types of graphs

• Directed graph (digraph): A graph in which the edges have directions. Each edge is an ordered pair of vertices.
• Undirected graph: A graph in which the edges have no direction. Each edge is an unordered pair of vertices.
• Weighted graph: A graph in which each edge has a numerical value (weight) associated with it.
• Unweighted graph: A graph in which the edges have no weights.
• Complete graph: A graph in which there is exactly one edge between every pair of vertices.

Graph representation

Graphs can be represented in two main ways:

Adjacency matrix

The adjacency matrix is a 2D array where each element indicates whether there is an edge between pairs of vertices.

a = [
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 1],
    [0, 1, 1, 0]
]

This matrix shows a graph with 4 vertices and edges between the pairs (0,1), (1,2), (1,3) and (2,3).

Adjacency list

The adjacency list represents the graph as a list of vertices, where each vertex has its own list of adjacent vertices.

{
    0: [1],
    1: [0, 2, 3],
    2: [1, 3],
    3: [1, 2]
}

In this list, vertex 0 is connected to vertex 1, vertex 1 is connected to vertex 0, 2, 3, and so on.

Graph traversal algorithms

Graph traversal means the process of visiting every vertex of a graph. There are two main ways to traverse a graph:

Breadth-First Search (BFS)

BFS is a method that iterates through a graph by exploring the neighbouring nodes located at the current depth before moving on to nodes located at the next depth level.

def bfs(graph, start):
    visited = set()
    queue = [start]

    while queue:
        vertex = queue.pop(0)

        if vertex not in visited:
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)

    return visited

In the above code, a graph is traversed starting from vertex start. The BFS method uses a queue to keep track of the vertex points to visit next.

Example of BFS in action

The above SVG shows a simple graph with vertices numbered 0 to 3. Starting from vertex 0, BFS will visit nodes in this order: 0, 1, 3, 2.

Depth-First Search (DFS)

DFS is a traversal method in which depth is prioritized, and one moves as far along a branch as possible before backtracking.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    for next in graph[start]:
        if next not in visited:
            dfs(graph, next, visited)

    return visited

In the DFS code, the method is called recursively and the stack is used through the function calls to keep track of the path.

Example of DFS in action

For the same graph, DFS will visit the nodes in this order: 0, 1, 2, 3.

Shortest path algorithm

The goal of graph algorithms is often to find the shortest path between nodes. Here are two well-known shortest path algorithms:

Dijkstra's algorithm

Dijkstra's algorithm finds the shortest path from the initial vertex to all other vertices in a weighted graph.

import heapq

def dijkstra(graph, start):
    queue = []
    heapq.heappush(queue, (0, start))
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

This algorithm maintains a queue to find the edges with the smallest cumulative weight first. It uses a priority queue (min-heap) to efficiently get the edge with the minimum distance.

Bellman–Ford algorithm

The Bellman-Ford algorithm calculates the shortest paths from a single source vertex to all other vertices in a graph. It can handle graphs with negative weights.

def bellman_ford(graph, start):
    distance = {i: float('inf') for i in graph}
    distance[start] = 0

    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                if distance[vertex] + weight < distance[neighbor]:
                    distance[neighbor] = distance[vertex] + weight

    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if distance[vertex] + weight < distance[neighbor]:
                raise ValueError("The graph contains a negative weight cycle")

    return distance

Unlike Dijkstra's algorithm, Bellman-Ford works well with graphs containing edges with negative weights. It repeatedly checks each edge to ensure that optimal paths have been found.

Minimum spanning tree (MST) algorithm

The minimum spanning tree of a connected, undirected graph is a subset of edges that connects all vertices without any cycles and with the minimum possible total edge weight.

Kruskal's algorithm

Kruskal's algorithm constructs the MST by adding edges one by one, starting with the shortest one, and adding only those edges that do not form cycles.

def kruskal(graph):
    parent = {}
    
    def find(n):
        while parent[n] != n:
            n = parent[n]
        return n

    def union(n1, n2):
        root1 = find(n1)
        root2 = find(n2)
        parent[root2] = root1

    graph.sort(key=lambda x: x[2])
    for n1, n2, _ in graph:
        parent[n1] = n1
        parent[n2] = n2

    mst = []
    for n1, n2, weight in graph:
        if find(n1) != find(n2):
            union(n1, n2)
            mst.append((n1, n2, weight))
    return mst

This algorithm starts by sorting all the edges by weight. It uses a union-find data structure to keep track of the connected components and ensures that no cycles are formed.

Prim's algorithm

Prim's algorithm constructs an MST by starting from an arbitrary vertex and successively adding the lowest-weight edge from already selected vertices to vertices not yet selected.

import heapq

def prim(graph, start):
    mst = []
    visited = set()
    min_edges = [(0, start, None)]

    while min_edges:
        weight, vertex, frm = heapq.heappop(min_edges)
        if vertex in visited:
            continue

        visited.add(vertex)
        if frm is not None:
            mst.append((frm, vertex, weight))

        for next_vertex, next_weight in graph[vertex].items():
            if next_vertex not in visited:
                heapq.heappush(min_edges, (next_weight, next_vertex, vertex))
    return mst

Prim's algorithm uses a priority queue to always expand the node in the current fringe with the lowest cost.

Conclusion

Graph algorithms provide solutions to a wide range of problems related to networks of nodes and edges. Whether it is finding the shortest path, optimal connections or traversing nodes, these algorithms play a vital role in solving complex problems efficiently. Understanding the basic definitions, representations and major algorithms like BFS, DFS, Dijkstra, Bellman-Ford, Kruskal and Prim is crucial to leverage graph algorithms in real-life applications.

Comments