无向图的邻接矩阵可用一维数组存储

简介: 无向图的邻接矩阵可用一维数组存储

在无向图中,邻接矩阵是一个对称矩阵,即矩阵的第 i 行第 j 列元素与第 j 行第 i 列元素相同(A[i][j] = A[j][i])。由于这个性质,我们不需要存储整个 n×n 的矩阵来表示一个包含 n 个顶点的无向图。我们只需要存储矩阵的上三角部分或下三角部分。

例如,考虑一个包含 4 个顶点的无向图,其邻接矩阵可能如下所示:

0 1 2 3
0 0 1 1 0
1 1 0 1 1
2 1 1 0 1
3 0 1 1 0

在这个邻接矩阵中,我们只需要存储非对角线上方或下方的元素。对于上三角矩阵(不包括对角线),我们可以按照以下顺序存储元素:

(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)

对应的一维数组就是:

1, 1, 0, 1, 1, 1

这里,我们按行优先的顺序存储了上三角矩阵中的元素。如果我们想通过一维数组来访问邻接矩阵中的元素 A[i][j] (假设 i < j),我们可以使用以下方法来计算一维数组中的索引:

index = i * (n - 1) - (i * (i + 1) / 2) + (j - i) - 1

这里,n 是顶点的数量。这个公式的理解是:

  • i * (n - 1) 是如果存储完整行时直到行 i 的元素数量。
  • (i * (i + 1) / 2) 是由于我们只存储上三角部分,所以需要减去前 i 行对角线及其下方的元素数量(即前 i 行中不存储的元素数量)。
  • (j - i) 是当前行 i 中,从对角线到我们要找的列 j 的元素数量。
  • 最后,我们减去 1 是因为数组索引从 0 开始。

这样,我们就可以仅用一个一维数组来存储无向图的邻接矩阵,节省了空间。

目录
相关文章
|
机器学习/深度学习 人工智能 自然语言处理
视觉 注意力机制——通道注意力、空间注意力、自注意力
本文介绍注意力机制的概念和基本原理,并站在计算机视觉CV角度,进一步介绍通道注意力、空间注意力、混合注意力、自注意力等。
11936 58
|
前端开发 JavaScript Java
基于Java+Springboot+Vue开发的医院门诊预约挂号系统
基于Java+Springboot+Vue开发的医院门诊预约挂号系统(前后端分离),这是一项为大学生课程设计作业而开发的项目。该系统旨在帮助大学生学习并掌握Java编程技能,同时锻炼他们的项目设计与开发能力。通过学习基于Java的门诊预约挂号管理系统项目,大学生可以在实践中学习和提升自己的能力,为以后的职业发展打下坚实基础。
385 2
基于Java+Springboot+Vue开发的医院门诊预约挂号系统
|
缓存 自然语言处理 算法
ICWS 2024 | 基于生成长度预测的大语言模型推理请求调度
大量实验证明,Magnus 可以有效降低请求响应时间并提高LLM批处理的吞吐量
882 0
|
机器学习/深度学习 算法 调度
|
Java
Java8中List转Map的几种方式
Java8中List转Map的几种方式
563 1
|
缓存 监控 Linux
深入了解Linux的`lscpu`命令:你的CPU信息专家
`lscpu`是Linux下的命令行工具,用于获取CPU详细信息,如架构、核心、线程、缓存和型号。它从系统文件读取数据,提供实时信息,支持多种输出格式,如扩展视图、解析格式。常用参数包括显示所有CPU (`-a`)、在线CPU (`-b`) 和可解析格式 (`--parseable`)。结合其他工具,`lscpu`在系统管理和性能调优中十分有用。
|
数据采集 存储 安全
登录态数据抓取:Python爬虫携带Cookie与Session的应用技巧
登录态数据抓取:Python爬虫携带Cookie与Session的应用技巧
|
存储 数据库 索引
B树与B+树的区别
B树与B+树的区别
|
存储 算法
【PTA刷题】求链式线性表的倒数第K项(代码+详解)
【PTA刷题】求链式线性表的倒数第K项(代码+详解)
378 0
|
机器学习/深度学习 数据采集 算法
机器学习:(PCA)主成分分析法及应用(spss)
机器学习:(PCA)主成分分析法及应用(spss)
926 0
机器学习:(PCA)主成分分析法及应用(spss)