Skip to main content

​
Overview

The AdjacencyListGraph class represents an unweighted graph using an adjacency list. It stores each vertex and its list of adjacent vertices in a dictionary, making it space-efficient for sparse graphs.

​
Constructor

AdjacencyListGraph(directed=False, vertices=None)
​
directed
bool
default:"False"
Whether the graph is directed
​
vertices
list[str]
default:"None"
List of vertex labels to initialize the graph with
from dsa.graph import AdjacencyListGraph

# Create empty graph
g = AdjacencyListGraph()

# Create directed graph
g = AdjacencyListGraph(directed=True)

# Create with initial vertices
g = AdjacencyListGraph(vertices=['A', 'B', 'C', 'D'])

​
Attributes

​
is_directed
bool
Whether the graph is directed
​
is_weighted
bool
Whether the graph is weighted (always False)

​
Methods

​
add_vertex

Add a vertex to the graph. 
add_vertex(label: str)
​
label
str
required
The vertex label to add
Raises: ValueError if the vertex already exists 
g = AdjacencyListGraph()
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')

​
delete_vertex

Delete a vertex from the graph and remove all edges connected to it. 
delete_vertex(label: str)
​
label
str
required
The vertex label to delete
g = AdjacencyListGraph(vertices=['A', 'B', 'C'])
g.add_edge('A', 'B')
g.delete_vertex('B')
print(g.vertices())  # ['A', 'C']

​
add_edge

Add an edge between two vertices. 
add_edge(start_label: str, end_label: str, directed=None)
​
start_label
str
required
Starting vertex label
​
end_label
str
required
Ending vertex label
​
directed
bool
default:"None"
Override the graph’s default directed behavior. If None, uses self.is_directed
g = AdjacencyListGraph()

# Add undirected edge (creates A→B and B→A)
g.add_edge('A', 'B')

# Add directed edge (creates B→C only)
g.add_edge('B', 'C', directed=True)

# Vertices are auto-created if they don't exist
g.add_edge('D', 'E')

​
add_directed_edge

Add a directed edge from start to end. 
add_directed_edge(start_label: str, end_label: str)
​
start_label
str
required
Starting vertex label
​
end_label
str
required
Ending vertex label
g = AdjacencyListGraph()
g.add_directed_edge('A', 'B')  # Only adds A→B

​
delete_edge

Delete an edge between two vertices. 
delete_edge(start_label: str, end_label: str, directed=None)
​
start_label
str
required
Starting vertex label
​
end_label
str
required
Ending vertex label
​
directed
bool
default:"None"
Override the graph’s default directed behavior. If None, uses self.is_directed
Raises: KeyError if either vertex or the edge does not exist 
g = AdjacencyListGraph()
g.add_edge('A', 'B')
g.delete_edge('A', 'B')

​
has_vertex

Check if a vertex exists in the graph. 
has_vertex(label: str) -> bool
​
label
str
required
The vertex label to check
​
return
bool
True if the vertex exists, False otherwise
g = AdjacencyListGraph(vertices=['A', 'B'])
print(g.has_vertex('A'))  # True
print(g.has_vertex('C'))  # False

​
has_edge

Check if an edge exists between two vertices. 
has_edge(start_label: str, end_label: str) -> bool
​
start_label
str
required
Starting vertex label
​
end_label
str
required
Ending vertex label
​
return
bool
True if an edge exists from start to end, False otherwise
Raises: KeyError if either vertex does not exist 
g = AdjacencyListGraph()
g.add_edge('A', 'B')
print(g.has_edge('A', 'B'))  # True
print(g.has_edge('B', 'C'))  # Raises KeyError

​
vertices

Get a list of all vertex labels. 
vertices() -> list
​
return
list[str]
List of all vertex labels in the graph
g = AdjacencyListGraph(vertices=['A', 'B', 'C'])
print(g.vertices())  # ['A', 'B', 'C']

​
edges

Get a list of all edges in the graph. 
edges() -> list
​
return
list[tuple]
List of edges, each represented as a tuple (start, end)
g = AdjacencyListGraph()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
print(g.edges())  # [('A', 'B'), ('B', 'A'), ('B', 'C'), ('C', 'B')]

​
undirected_edges

Get a list of edges without duplicates for undirected graphs. 
undirected_edges() -> list
​
return
list[tuple]
List of unique edges, each represented as a tuple (start, end)
g = AdjacencyListGraph()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
print(g.undirected_edges())  # [('A', 'B'), ('B', 'C')]

​
adjacents

Get a list of adjacent vertices for a given vertex. 
adjacents(vertex: str) -> list
​
vertex
str
required
The vertex label
​
return
list[str]
List of adjacent vertex labels
g = AdjacencyListGraph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
print(g.adjacents('A'))  # ['B', 'C']

​
order

Get the number of vertices in the graph. 
order() -> int
​
return
int
The number of vertices
g = AdjacencyListGraph(vertices=['A', 'B', 'C'])
print(g.order())  # 3

​
size

Get the number of edges in the graph. 
size() -> int
​
return
int
The number of edges
g = AdjacencyListGraph()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
print(g.size())  # 2 (undirected, so A-B and B-C counted once each)

​
to_dict

Convert the graph to a dictionary representation. 
to_dict() -> dict
​
return
dict
Dictionary where keys are vertices and values are lists of adjacent vertices
g = AdjacencyListGraph()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
print(g.to_dict())
# {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}

​
Class Methods

​
from_dict

Create a graph from a dictionary representation. 
@classmethod
from_dict(data: dict, directed: bool = False) -> AdjacencyListGraph
​
data
dict
required
Dictionary where keys are vertices and values are lists of adjacent vertices
​
directed
bool
default:"False"
Whether the graph is directed
​
return
AdjacencyListGraph
A new graph instance
data = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}
g = AdjacencyListGraph.from_dict(data)

​
Special Methods

​
__getitem__

Get adjacent vertices using bracket notation. 
g = AdjacencyListGraph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
print(g['A'])  # ['B', 'C']

​
__contains__

Check if a vertex exists using the in operator. 
g = AdjacencyListGraph(vertices=['A', 'B'])
print('A' in g)  # True
print('C' in g)  # False

​
__len__

Get the number of vertices. 
g = AdjacencyListGraph(vertices=['A', 'B', 'C'])
print(len(g))  # 3

​
Complete Examples

from dsa.graph import AdjacencyListGraph

# Create social network (sparse graph)
g = AdjacencyListGraph()

# Add friendships
g.add_edge('Alice', 'Bob')
g.add_edge('Alice', 'Charlie')
g.add_edge('Bob', 'David')
g.add_edge('Charlie', 'Eve')
g.add_edge('David', 'Eve')

print(f"Users: {g.vertices()}")
print(f"Friendships: {g.undirected_edges()}")

# Find friends
alice_friends = g.adjacents('Alice')
print(f"Alice's friends: {alice_friends}")

# Find mutual friends
def find_mutual_friends(graph, user1, user2):
    friends1 = set(graph.adjacents(user1))
    friends2 = set(graph.adjacents(user2))
    return list(friends1.intersection(friends2))

mutual = find_mutual_friends(g, 'Bob', 'Charlie')
print(f"Mutual friends of Bob and Charlie: {mutual}")

​
Performance

  • Space Complexity: O(V + E) where V = vertices, E = edges
  • Add Vertex: O(1)
  • Delete Vertex: O(V + E) - must remove vertex from all adjacency lists
  • Add Edge: O(1) average case
  • Delete Edge: O(degree(V)) - must search adjacency list
  • Has Edge: O(degree(V))
  • Get Adjacents: O(1)
  • Get All Edges: O(V + E)

​
Notes

  • Best for sparse graphs where E is much less than V²
  • More space-efficient than adjacency matrix for sparse graphs
  • Faster vertex addition than adjacency matrix
  • Slower edge lookup than adjacency matrix
  • Vertex labels must be strings
  • Adjacency lists are implemented using Python dictionaries and lists
  • For undirected graphs, edges are stored in both directions

Build docs developers (and LLMs) love

Get started for freeTalk to us