An adjacency list represents a graph by grouping edges according to their source vertex. A dictionary associates each vertex with the collection of its outgoing edges or destination vertices. section 13.9
For a vertex v, its adjacency list contains every edge whose source is v. The collection can be a linked list, Python list, set, or another container that supports searching and traversal. section 13.9
A practical Python implementation can organize the representation like this:
- Store vertices in a Python dictionary keyed by unique vertex identifiers. section 13.9
- Give each internal Vertex object its own adjacency list for outgoing edges. section 13.9
- Store destination vertices directly when edges are unweighted and unlabeled; otherwise store Edge objects or pairs and tuples such as (source, destination, weight). section 13.9
- Search before insertion so duplicate edges are rejected, and remove incoming references when deleting a vertex. section 13.9
A small class structure
A Vertex can keep a singly linked list and expose operations such as has_edge_to and add_edge_to. An outer Graph can initialize an empty dictionary, retrieve vertices by key, insert vertices and edges, and delete vertices while removing references to them. section 13.9
class Vertex:
def __init__(self, key):
self.id = key
self._adj_list = SinglyLinkedList()
def has_edge_to(self, destination_vertex):
return self._adj_list._search(destination_vertex) is not None
def add_edge_to(self, destination_vertex):
if self.has_edge_to(destination_vertex):
raise ValueError(f'Edge already exists: {self} -> { destination_vertex}')
self._adj_list.insert_in_front(destination_vertex)
Inspect the compact Vertex implementation that delegates edge searching and insertion to a singly linked list. section 13.9
Adjacency lists are one of the two common graph representations; adjacency matrices are used mainly in niche contexts. They support graph traversal and searching, including breadth-first search and depth-first search. section 13.8 section 13.16
