✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-102

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.

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

A

  • B

  • C

B

  • A

  • D

C

  • A

D

  • B

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.

Weighted Example

A

    • B

    • 5

    • C

    • 8

B

    • A

    • 5

    • D

    • 3

C

    • A

    • 8

D

    • B

    • 3

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.

Bfs Or Dfs

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.

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.

Best Use Cases

  • Sparse graphs

  • Large networks

  • BFS and DFS

  • Social networks

  • Road and communication networks

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

NameDescription

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

QuestionAnswer

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