Implementing a Graph Data Structure in Python

Introduction

Graphs are a versatile data structure that can represent anything from social networks to web pages and their interconnections.

A graph consists of vertices (also known as nodes) and edges that connect pairs of vertices.

In this blog post, we’ll explore the fundamentals of graph theory and implement a simple, undirected graph in Python.

Types of Graphs

There are various types of graphs:

1. Undirected Graphs: Edges have no direction (A-B is the same as B-A).
2. Directed Graphs (Digraphs): Edges have a direction (A-B is not the same as B-A).
3. Weighted Graphs: Edges have weights or costs associated with them.
4. Unweighted Graphs: Edges have no weights.

Text-Based Representation

Here’s a simple undirected, unweighted graph:

   A----B
   |   /|
   |  / |
   | /  |
   C----D

This graph consists of 4 vertices (A, B, C, D) and 5 edges (AB, AC, BD, CD, BC).

Python Implementation

There are various ways to represent graphs in Python:

1. Adjacency Matrix: A 2D array where the cell at the ith row and jth column is 1 if there is an edge between vertices i and j; otherwise, it’s 0.
2. Adjacency List: A list where the ith element is a list of vertices adjacent to the ith vertex.

We’ll implement an undirected graph using an adjacency list for simplicity.

Graph Class

Here’s a simple class to represent an undirected graph using an adjacency list.

class Graph:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph.keys():
            self.graph[vertex] = []

    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.graph.keys() and vertex2 in self.graph.keys():
            self.graph[vertex1].append(vertex2)
            self.graph[vertex2].append(vertex1)

    def show_graph(self):
        for vertex in self.graph.keys():
            print(vertex, ":", self.graph[vertex])

Method Details:

• add_vertex: Adds a vertex to the graph.
• add_edge: Adds an edge between two vertices in the graph.
• show_graph: Displays the graph.

Using the Graph Class

Here’s how you can use the Graph class to create a simple graph.

# Create a new Graph
g = Graph()

# Add vertices
g.add_vertex("A")
g.add_vertex("B")
g.add_vertex("C")
g.add_vertex("D")

# Add edges
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")
g.add_edge("B", "C")

# Show the graph
g.show_graph()

When you run show_graph, you’ll see the adjacency list representation of the graph:

A : ['B', 'C']
B : ['A', 'D', 'C']
C : ['A', 'D', 'B']
D : ['B', 'C']

Each entry in the list corresponds to an edge in the graph. For example, vertex A has edges connecting it to B and C.

If you find this guide helpful, please share with others, and spread the knowledge!