Skip to main content

​
Overview

The AdjacencyListWeightedGraph class represents a weighted graph using an adjacency list. It extends AdjacencyListGraph and stores each vertex with a dictionary mapping adjacent vertices to edge weights, making it space-efficient for sparse weighted graphs.

​
Constructor

AdjacencyListWeightedGraph(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 AdjacencyListWeightedGraph

# Create empty weighted graph
g = AdjacencyListWeightedGraph()

# Create directed weighted graph
g = AdjacencyListWeightedGraph(directed=True)

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

​
Attributes

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

​
Methods

​
add_edge

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

# Add weighted edges
g.add_edge('A', 'B', 5)
g.add_edge('B', 'C', 10)
g.add_edge('A', 'C', 15)

# Add directed edge in undirected graph
g.add_edge('C', 'D', 7, directed=True)

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

​
delete_edge

Delete a weighted 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 = AdjacencyListWeightedGraph()
g.add_edge('A', 'B', 5)
g.delete_edge('A', 'B')

​
get_weight

Get the weight of an edge between two vertices. 
get_weight(start_label: str, end_label: str) -> numeric
​
start_label
str
required
Starting vertex label
​
end_label
str
required
Ending vertex label
​
return
numeric
The weight of the edge from start to end
g = AdjacencyListWeightedGraph()
g.add_edge('A', 'B', 5)
weight = g.get_weight('A', 'B')
print(weight)  # 5

​
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 (without weights)
g = AdjacencyListWeightedGraph()
g.add_edge('A', 'B', 5)
g.add_edge('A', 'C', 10)
print(g.adjacents('A'))  # ['B', 'C']

​
adjacent_items

Get a list of adjacent vertices with their edge weights. 
adjacent_items(vertex: str) -> dict_items
​
vertex
str
required
The vertex label
​
return
dict_items
Dictionary items view of (neighbor_label, weight) pairs
g = AdjacencyListWeightedGraph()
g.add_edge('A', 'B', 5)
g.add_edge('A', 'C', 10)

for neighbor, weight in g.adjacent_items('A'):
    print(f"{neighbor}: {weight}")
# Output:
# B: 5
# C: 10

​
edges

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

​
undirected_edges

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

​
Class Methods

​
from_dict

Create a weighted graph from a dictionary representation. 
@classmethod
from_dict(data: dict, directed: bool = False) -> AdjacencyListWeightedGraph
​
data
dict
required
Dictionary where keys are vertices and values are dictionaries mapping neighbors to weights
​
directed
bool
default:"False"
Whether the graph is directed
​
return
AdjacencyListWeightedGraph
A new weighted graph instance
data = {
    'A': {'B': 5, 'C': 10},
    'B': {'A': 5, 'D': 15},
    'C': {'A': 10},
    'D': {'B': 15}
}
g = AdjacencyListWeightedGraph.from_dict(data)

​
Special Methods

​
__getitem__

Get adjacent vertices and weights using bracket notation. 
g = AdjacencyListWeightedGraph()
g.add_edge('A', 'B', 5)
g.add_edge('A', 'C', 10)
print(g['A'])  # {'B': 5, 'C': 10}

​
__len__

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

​
Inherited Methods

The following methods are inherited from AdjacencyListGraph:
  • add_vertex(label) - Add a vertex
  • delete_vertex(label) - Delete a vertex
  • has_vertex(label) - Check if vertex exists
  • has_edge(start, end) - Check if edge exists
  • vertices() - Get all vertices
  • order() - Get number of vertices
  • size() - Get number of edges
  • to_dict() - Convert to dictionary (returns weighted format)
  • __contains__(label) - Check vertex membership

​
Complete Examples

from dsa.graph import AdjacencyListWeightedGraph
import sys

# Create city road network
g = AdjacencyListWeightedGraph()

g.add_edge('Seattle', 'Portland', 173)
g.add_edge('Seattle', 'Vancouver', 140)
g.add_edge('Portland', 'Eugene', 110)
g.add_edge('Vancouver', 'Kelowna', 390)
g.add_edge('Eugene', 'Medford', 165)
g.add_edge('Kelowna', 'Calgary', 610)

def dijkstra(graph, start, end):
    distances = {v: sys.maxsize for v in graph.vertices()}
    distances[start] = 0
    previous = {v: None for v in graph.vertices()}
    unvisited = set(graph.vertices())
    
    while unvisited:
        # Find minimum distance vertex
        current = min(unvisited, key=lambda v: distances[v])
        
        if distances[current] == sys.maxsize:
            break
        
        unvisited.remove(current)
        
        if current == end:
            break
        
        # Update neighbor distances
        for neighbor, weight in graph.adjacent_items(current):
            if neighbor in unvisited:
                new_distance = distances[current] + weight
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    previous[neighbor] = current
    
    # Reconstruct path
    path = []
    current = end
    while current is not None:
        path.insert(0, current)
        current = previous[current]
    
    return path, distances[end]

path, distance = dijkstra(g, 'Seattle', 'Medford')
print(f"Shortest route: {' -> '.join(path)}")
print(f"Total distance: {distance} miles")

​
Performance

  • Space Complexity: O(V + E) where V = vertices, E = edges
  • Add Vertex: O(1)
  • Delete Vertex: O(V + E)
  • Add Edge: O(1) average case
  • Delete Edge: O(1) average case (dictionary deletion)
  • Has Edge: O(1) average case
  • Get Weight: O(1) average case
  • Get Adjacents: O(1)
  • Get Adjacent Items: O(1)
  • Get All Edges: O(V + E)

​
Notes

  • Best for sparse weighted graphs where E is much less than V²
  • More space-efficient than weighted adjacency matrix
  • Fast edge weight lookups using dictionary structure
  • Weights can be any numeric type (int, float, etc.)
  • Vertex labels must be strings
  • Ideal for shortest path algorithms (Dijkstra, Bellman-Ford)
  • Good for minimum spanning tree algorithms (Prim, Kruskal)
  • For undirected graphs, edge weights are stored in both directions
  • Adjacent items are stored as dictionary items for efficient iteration

Build docs developers (and LLMs) love

Get started for freeTalk to us