concept · INFO-CS-ADS-102Graph Representation — Adjacency List
An adjacency list represents a graph by storing a collection of neighboring vertices for each vertex. It is memory-efficient for sparse graphs and supports efficient graph traversal.
Explanation
Overview
An adjacency list is a graph representation in which each vertex maintains a list of vertices directly connected to it.
Structure
A graph is represented as an array, map, or dictionary in which each vertex is associated with its neighbors.
Basic operations
addVertex: Create an empty neighbor list for the new vertex.; addEdge: Add the destination vertex to the appropriate neighbor list.; removeEdge: Remove the corresponding neighbor entry.; findNeighbors: Access the list associated with the selected vertex.; checkEdge: Search the selected vertex's neighbor list.
Key concepts
name: Core idea; description: The central focus of graph representation — adjacency list is the capability described here: An adjacency list represents a graph by storing a collection of neighboring vertices for each vertex. It is memory-efficient for sparse graphs and supports efficient graph traversal.; name: Problem context; description: Graph Representation — Adjacency List is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using graph representation — adjacency list, check its assumptions, input requirements, expected output, and resource constraints.
Time complexity
iterateNeighbors: O(deg(v)); checkEdge: O(deg(v)) with ordinary unsorted lists.; addEdge: O(1) amortized when appending to a suitable dynamic list.; removeEdge: O(deg(v)) with ordinary lists.; bfsOrDfs: O(V + E)
Space complexity
O(V + E), because each vertex is stored and each edge contributes one adjacency entry in a directed graph or two entries in an undirected graph.
Example
A: B; C; B: A; D; C: A; D: B
Example or application
Definition
An adjacency list is a graph representation in which each vertex maintains a list of vertices directly connected to it.
Structure
A graph is represented as an array, map, or dictionary in which each vertex is associated with its neighbors.
Undirected Graph Property
For an undirected edge between A and B, B appears in A's neighbor list and A appears in B's neighbor list.
Directed Graph Property
For a directed edge A → B, B appears in A's outgoing-neighbor list. A does not automatically appear in B's list.
Weighted Graph Representation
Each neighbor entry stores both the destination vertex and the associated edge weight.
Basic Operations
Add Vertex
Create an empty neighbor list for the new vertex.
Add Edge
Add the destination vertex to the appropriate neighbor list.
Remove Edge
Remove the corresponding neighbor entry.
Find Neighbors
Access the list associated with the selected vertex.
Check Edge
Search the selected vertex's neighbor list.
Time Complexity
Iterate Neighbors
O(deg(v))
Check Edge
O(deg(v)) with ordinary unsorted lists.
Add Edge
O(1) amortized when appending to a suitable dynamic list.
Remove Edge
O(deg(v)) with ordinary lists.
Space Complexity
O(V + E), because each vertex is stored and each edge contributes one adjacency entry in a directed graph or two entries in an undirected graph.
Advantages
Memory-efficient for sparse graphs.
Supports efficient BFS and DFS traversal.
Makes it easy to iterate over the neighbors of a vertex.
Can naturally store weighted edges.
Suitable for graphs that grow dynamically.
Limitations
Edge-existence checks may require scanning a neighbor list.
Removing an edge may require searching for its entry.
Implementation must handle duplicate edges according to the graph model.
Neighbor lists require additional management when vertices are removed.
Comparison With Matrix
Adjacency List Space
O(V + E)
Adjacency Matrix Space
O(V²)
Edge Lookup
O(deg(v)) for a standard adjacency list versus O(1) for an adjacency matrix.
Neighbor Iteration
O(deg(v)) for an adjacency list versus O(V) for a matrix row.
Implementation Considerations
Choose arrays, linked lists, sets, or maps according to the required operations.
Use a consistent representation for vertex identifiers.
Store edge weights when modeling weighted graphs.
Avoid accidental duplicate entries when the graph is intended to be simple.
For undirected graphs, maintain both directions consistently.
Related Concepts
Adjacency Matrix
Graph Traversal
Sparse Graphs
Weighted Graphs
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of graph representation — adjacency list is the capability described here: An adjacency list represents a graph by storing a collection of neighboring vertices for each vertex. It is memory-efficient for sparse graphs and supports efficient graph traversal. |
Problem context | Graph Representation — Adjacency List is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using graph representation — adjacency list, check its assumptions, input requirements, expected output, and resource constraints. |
Applications
Network analysis tasks that use graph representation — adjacency list.
Dependency and infrastructure models requiring graph representation — adjacency list.
Scheduling or resource-allocation workflows involving graph representation — adjacency list.
Practice Questions
| Question | Answer |
|---|
What is the main purpose of graph representation — adjacency list? | An adjacency list represents a graph by storing a collection of neighboring vertices for each vertex. It is memory-efficient for sparse graphs and supports efficient graph traversal. |
What should be checked before applying graph representation — adjacency list? | For graph representation — adjacency list, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of graph representation — adjacency list be validated? | Trace a representative graph representation — adjacency list case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of graph representation — adjacency list.
Identify the assumptions, inputs, and conditions relevant to graph representation — adjacency list.
Evaluate an application of graph representation — adjacency list for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures