Skip to main content

​
Overview

The AdjacencyMatrixGraph class represents an unweighted graph using an adjacency matrix. It supports both directed and undirected graphs and stores edges as boolean values in a 2D matrix.

​
Constructor

AdjacencyMatrixGraph(directed=False, weighted=False, vertices=None)
​
directed
bool
default:"False"
Whether the graph is directed
​
weighted
bool
default:"False"
Whether the graph is weighted (always False for this class)
​
vertices
list[str]
default:"None"
List of vertex labels to initialize the graph with
Raises: ValueError if duplicate vertex labels are provided 
from dsa.graph import AdjacencyMatrixGraph

# Create empty graph
g = AdjacencyMatrixGraph()

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

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

​
Attributes

​
is_directed
bool
Whether the graph is directed
​
is_weighted
bool
Whether the graph is weighted (always False)
​
labels
list[str]
List of all vertex labels in the graph

​
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 = AdjacencyMatrixGraph()
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')

​
delete_vertex

Delete a vertex from the graph. 
delete_vertex(label: str)
​
label
str
required
The vertex label to delete
g = AdjacencyMatrixGraph(vertices=['A', 'B', 'C'])
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 = AdjacencyMatrixGraph(vertices=['A', 'B', 'C'])

# 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')

​
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 the edge does not exist 
g = AdjacencyMatrixGraph()
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 = AdjacencyMatrixGraph(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 = AdjacencyMatrixGraph()
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 = AdjacencyMatrixGraph(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 = AdjacencyMatrixGraph()
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 = AdjacencyMatrixGraph()
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 = AdjacencyMatrixGraph()
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 = AdjacencyMatrixGraph(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 = AdjacencyMatrixGraph()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
print(g.size())  # 2 (undirected, so A-B and B-C are counted once each)
Print a visual representation of the adjacency matrix. 
print_graph()

g = AdjacencyMatrixGraph(vertices=['A', 'B', 'C'])
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.print_graph()
# Output:
#    | A   B   C  
# ----------------
#  A |     T      
#  B | T       T  
#  C |     T

​
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 = AdjacencyMatrixGraph()
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) -> AdjacencyMatrixGraph
​
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
AdjacencyMatrixGraph
A new graph instance
data = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}
g = AdjacencyMatrixGraph.from_dict(data)

​
Special Methods

​
__getitem__

Get adjacent vertices using bracket notation. 
g = AdjacencyMatrixGraph()
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 = AdjacencyMatrixGraph(vertices=['A', 'B'])
print('A' in g)  # True
print('C' in g)  # False

​
__len__

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

​
Complete Examples

from dsa.graph import AdjacencyMatrixGraph

# Create social network graph
g = AdjacencyMatrixGraph()

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

print(f"Vertices: {g.vertices()}")
print(f"Edges: {g.undirected_edges()}")
print(f"Alice's friends: {g.adjacents('Alice')}")
print(f"Graph order: {g.order()}")  # 4 vertices
print(f"Graph size: {g.size()}")    # 4 edges

# Check connections
print(f"Are Alice and Bob friends? {g.has_edge('Alice', 'Bob')}")
print(f"Are Alice and Charlie friends? {g.has_edge('Alice', 'Charlie')}")

​
Performance

  • Space Complexity: O(V²) where V is the number of vertices
  • Add Vertex: O(V²) - requires resizing matrix
  • Delete Vertex: O(V²) - requires resizing matrix
  • Add Edge: O(1)
  • Delete Edge: O(1)
  • Has Edge: O(1)
  • Get Adjacents: O(V)
  • Get All Edges: O(V²)

​
Notes

  • Best for dense graphs where most vertices are connected
  • Provides O(1) edge lookup time
  • Uses more space than adjacency list for sparse graphs
  • Vertex labels must be strings
  • Self-loops are not supported
  • For undirected graphs, edges are stored symmetrically in the matrix

Build docs developers (and LLMs) love

Get started for freeTalk to us