concept · INFO-CS-ADS-101Graph 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
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.
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
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
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.
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
| Name | Description |
|---|
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
| Question | Answer |
|---|
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