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

Graph Representation — Adjacency Matrix

An adjacency matrix represents a graph using a two-dimensional array in which each cell indicates whether two vertices are connected. It provides constant-time edge-existence checks and is particularly useful for dense graphs.

Explanation

Overview

An adjacency matrix is a V × V matrix where each entry represents the presence, absence, or weight of an edge between two vertices.

Structure

For a graph with V vertices, the matrix contains V rows and V columns.

Basic operations

checkEdge: Read A[u][v].; addEdge: Set A[u][v] to 1 or the required weight.; removeEdge: Set A[u][v] to the absent-edge representation.; findNeighbors: Scan the corresponding row to identify outgoing neighbors.

Key concepts

name: Core idea; description: The central focus of graph representation — adjacency matrix is the capability described here: An adjacency matrix represents a graph using a two-dimensional array in which each cell indicates whether two vertices are connected. It provides constant-time edge-existence checks and is particularly useful for dense graphs.; name: Problem context; description: Graph Representation — Adjacency Matrix is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using graph representation — adjacency matrix, check its assumptions, input requirements, expected output, and resource constraints.

Time complexity

checkEdge: O(1); addEdge: O(1); removeEdge: O(1); findNeighbors: O(V); fullMatrixInitialization: O(V²)

Space complexity

O(V²), regardless of how many edges are present.

Example

vertices: A; B; edges: A; B; B; C; matrix: 0; 1; 0; 1; 0; 1

Example or application

Vertices

  • A

  • B

  • C

Edges

    • A

    • B

    • B

    • C

Matrix

    • 0

    • 1

    • 0

    • 1

    • 0

    • 1

    • 0

    • 1

    • 0

Definition

An adjacency matrix is a V × V matrix where each entry represents the presence, absence, or weight of an edge between two vertices.

Structure

For a graph with V vertices, the matrix contains V rows and V columns.

Matrix Notation

A[i][j]

Unweighted Graph

A[i][j] = 1 if an edge exists from vertex i to vertex j; otherwise A[i][j] = 0.

Weighted Graph

A[i][j] stores the edge weight when an edge exists. A separate representation or sentinel is needed to distinguish an absent edge from a valid zero-weight edge.

Undirected Graph Property

The adjacency matrix of an undirected graph is symmetric because A[i][j] = A[j][i].

Directed Graph Property

The adjacency matrix of a directed graph does not have to be symmetric.

Self Loop Representation

A self-loop is represented by a nonzero diagonal entry, such as A[i][i] = 1 in an unweighted graph.

Basic Operations

Check Edge

Read A[u][v].

Add Edge

Set A[u][v] to 1 or the required weight.

Remove Edge

Set A[u][v] to the absent-edge representation.

Find Neighbors

Scan the corresponding row to identify outgoing neighbors.

Time Complexity

Check Edge

O(1)

Add Edge

O(1)

Remove Edge

O(1)

Find Neighbors

O(V)

Full Matrix Initialization

O(V²)

Space Complexity

O(V²), regardless of how many edges are present.

Advantages

  • Simple and straightforward representation.

  • Constant-time edge-existence checks.

  • Convenient for dense graphs.

  • Easy to implement using two-dimensional arrays.

  • Useful for matrix-based graph algorithms.

Limitations

  • Requires O(V²) memory.

  • Wastes space for sparse graphs.

  • Finding all neighbors requires scanning an entire row.

  • Adding or removing a vertex may require creating a larger matrix.

Best Use Cases

  • Dense graphs

  • Small graphs

  • Graphs requiring frequent edge-existence checks

  • Matrix-based graph computations

Implementation Considerations

  • Assign each vertex a stable numeric index.

  • For undirected graphs, update both A[u][v] and A[v][u].

  • For directed graphs, update only the appropriate directed entry.

  • Choose a clear representation for absent edges.

  • Use suitable numeric types for weighted graphs.

Related Concepts

  • Adjacency List

  • Graph Traversal

  • Directed Graphs

  • Weighted Graphs

Key Concepts

NameDescription

Core idea

The central focus of graph representation — adjacency matrix is the capability described here: An adjacency matrix represents a graph using a two-dimensional array in which each cell indicates whether two vertices are connected. It provides constant-time edge-existence checks and is particularly useful for dense graphs.

Problem context

Graph Representation — Adjacency Matrix is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using graph representation — adjacency matrix, check its assumptions, input requirements, expected output, and resource constraints.

Applications

  • Network analysis tasks that use graph representation — adjacency matrix.

  • Dependency and infrastructure models requiring graph representation — adjacency matrix.

  • Scheduling or resource-allocation workflows involving graph representation — adjacency matrix.

Practice Questions

QuestionAnswer

What is the main purpose of graph representation — adjacency matrix?

An adjacency matrix represents a graph using a two-dimensional array in which each cell indicates whether two vertices are connected. It provides constant-time edge-existence checks and is particularly useful for dense graphs.

What should be checked before applying graph representation — adjacency matrix?

For graph representation — adjacency matrix, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of graph representation — adjacency matrix be validated?

Trace a representative graph representation — adjacency matrix 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 matrix.

  • Identify the assumptions, inputs, and conditions relevant to graph representation — adjacency matrix.

  • Evaluate an application of graph representation — adjacency matrix 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