Python Graphs

Python Graphs

A Graph is a non-linear data structure consisting of nodes (also called vertices) and edges. An edge connects a pair of nodes, indicating a relationship between them. Graphs are used to model networks and relationships in a huge variety of applications, from social networks to mapping applications.

Key Graph Terminology

• Vertex (or Node): A fundamental part of a graph.
• Edge (or Arc): A line connecting two vertices.
• Adjacent Vertices: Two vertices are adjacent if they are connected by an edge.
• Path: A sequence of vertices where each adjacent pair is connected by an edge.
• Directed Graph: A graph where edges have a direction. An edge (u, v) goes from vertex u to vertex v. (Think of a one-way street).
• Undirected Graph: A graph where edges have no direction. An edge (u, v) is the same as (v, u). (Think of a two-way street).
• Weighted Graph: A graph where each edge has a numerical weight or cost. (Think of the distance between two cities on a map).

!Graph Diagram

Representing a Graph in Python

There are two common ways to represent a graph in code:

1. Adjacency Matrix

An adjacency matrix is a 2D array (a list of lists) of size V x V where V is the number of vertices. A slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.

• Pros: Fast to check if an edge exists between two vertices (O(1)).
• Cons: Uses a lot of memory (O(V^2)), even if the graph has few edges.

2. Adjacency List

An adjacency list represents a graph as an array of lists. The size of the array is equal to the number of vertices. An entry adj[i] is a list of vertices adjacent to the i-th vertex.

In Python, it's common to use a dictionary for an adjacency list, where each key is a vertex and its value is a list of its neighbors. This is the most common and generally most efficient method for most problems.

• Pros: Memory efficient. Only stores the connections that exist.
• Cons: Checking for a specific edge can be slower (O(k), where k is the number of neighbors).

Adjacency List Implementation

Let's model a simple social network using an adjacency list.

class Graph:
    def __init__(self):
        self.adj_list = {}
    def add_vertex(self, vertex):
        if vertex not in self.adj_list:
            self.adj_list[vertex] = []
    # For an undirected graph, add edges in both directions
    def add_edge(self, v1, v2):
        if v1 in self.adj_list and v2 in self.adj_list:
            self.adj_list[v1].append(v2)
            self.adj_list[v2].append(v1)
    def print_graph(self):
        for vertex, edges in self.adj_list.items():
            print(vertex, ":", edges)

--- Usage ---
g = Graph()
g.add_vertex("Alice")
g.add_vertex("Bob")
g.add_vertex("Charlie")
g.add_edge("Alice", "Bob")
g.add_edge("Bob", "Charlie")
g.print_graph()

The output shows who is "friends" with whom:

Alice : ['Bob']
Bob : ['Alice', 'Charlie']
Charlie : ['Bob']