【CS.DS】数据结构 —— 图：深入了解三种表示方法之邻接表(Adjacency List)

文章目录

    • 1 概念
    • 2 无向图的邻接表
      • 2.1 示例
      • 2.2 Mermaid 图示例
      • 2.3 C++实现
        • 2.3.1 简单实现
        • 2.3.2 优化封装
      • 2.4 总结
    • 3 有向图的邻接表
      • 3.1 示例
      • 3.2 C++实现
      • 3.3 总结
    • 4 邻接图的遍历
    • 5 拓展补充
    • References

数据结构
在这里插入图片描述

1 概念

  • 优点：空间效率高，适合稀疏图。动态性强，可以方便地添加或删除边。

    • 邻接表表示法是一种高效表示稀疏图的方式。//

  • 缺点：查找某条边是否存在的时间复杂度较高。

  • 示例：

A: B -> D
B: A -> C -> D
C: B
D: A -> B
  • 示例解释：顶点 A 连接到 B 和 D，顶点 B 连接到 A、C 和 D，以此类推。

2 无向图的邻接表

2.1 示例

假设有以下无向图，其中节点 A、B、C、D、E 表示城市，边表示城市之间的道路，权重表示道路的距离。

在邻接表（链式）表示法中，图的边权重是预先给定的，而不是通过某种计算得到的。它们通常是图的定义的一部分，表示从一个顶点到另一个顶点的距离、时间或其他成本。例如，在地图中的路径权重可以表示两个地点之间的距离。

    A----3----B|         |4         2|         |C----1----D|     5     |E

对应的邻接表为：

A -> B(3) -> C(4)
B -> A(3) -> D(2)
C -> A(4) -> D(1) -> E(5)
D -> B(2) -> C(1)
E -> C(5)

2.2 Mermaid 图示例

表节点链表
顶点
3
3
4
2
5
4
2
1
5
1
^
C
^
D
^
E
D
^
C
^
B
A
A
B
A
C
B
D
C
E

e.g. 顶点 A 的邻接表：

  • 顶点 A 连接到顶点 B，边的权重是 3。
  • 顶点 A 再连接到顶点 C，边的权重是 4。
  • 最后一个节点指向 ^ 表示链表结束。

2.3 C++实现

2.3.1 简单实现
#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;// 表示图的结构: `Edge` 结构体表示图的边，包括目的顶点 `dest`、边的权重 `weight` 和指向下一条边的指针 `next`。
struct Edge {int dest;   // 目的顶点int weight; // 边的权重Edge* next; // 指向下一条边的指针
};// `Vertex` 结构体表示图的顶点，包括顶点数据 `data` 和指向第一个相邻顶点的指针 `first`。
struct Vertex {char data;    // 顶点数据Edge* first; // 指向第一个相邻顶点的指针
};// 初始化图: `addEdge` 函数用于向图中添加边，每次添加新边时，会将其插入到链表的头部。
void addEdge(Vertex vertices[], int src, int dest, int weight) {Edge* newEdge = new Edge{dest, weight, vertices[src].first};vertices[src].first = newEdge;
}void printGraph(Vertex vertices[], int V) {for (int i = 0; i < V; ++i) {cout << "顶点 " << vertices[i].data << " 的邻接表: ";Edge* edge = vertices[i].first;while (edge) {cout << " -> " << vertices[edge->dest].data << " (权重 " << edge->weight << ")";edge = edge->next;}cout << endl;}
}int main() {const int V = 5;Vertex vertices[V] = {{'A', nullptr}, {'B', nullptr}, {'C', nullptr}, {'D', nullptr}, {'E', nullptr}};// 根据图添加边addEdge(vertices, 0, 1, 3); // A -> BaddEdge(vertices, 0, 2, 4); // A -> CaddEdge(vertices, 1, 0, 3); // B -> AaddEdge(vertices, 1, 3, 2); // B -> DaddEdge(vertices, 2, 0, 4); // C -> AaddEdge(vertices, 2, 3, 1); // C -> DaddEdge(vertices, 2, 4, 5); // C -> EaddEdge(vertices, 3, 1, 2); // D -> BaddEdge(vertices, 3, 2, 1); // D -> CaddEdge(vertices, 4, 2, 5); // E -> CprintGraph(vertices, V);return 0;
}

封装实现:
优点：

  • 直接性：直接使用链表来表示邻接表，比较直观。
  • 高效性：链表的插入操作比较高效。
    缺点：
  • 复杂性：需要手动管理内存，容易出现内存泄漏问题。
  • 灵活性：不如 STL 容器灵活，操作起来相对繁琐。
#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;struct Edge {int dest;int weight;Edge* next;
};struct Vertex {char data;Edge* first;
};class Graph {
public:// 构造函数，初始化顶点数量和顶点数组Graph(int vertices) : V(vertices) {vertex_list = new Vertex[V];for (int i = 0; i < V; ++i) {vertex_list[i].data = 'A' + i;vertex_list[i].first = nullptr;}}// 析构函数，释放所有动态分配的内存~Graph() {for (int i = 0; i < V; ++i) {Edge* current = vertex_list[i].first;while (current) {Edge* temp = current;current = current->next;delete temp;}}delete[] vertex_list;}void AddEdge(int src, int dest, int weight) {Edge* newEdge = new Edge{dest, weight, vertex_list[src].first};vertex_list[src].first = newEdge;}void PrintGraph() const {for (int i = 0; i < V; ++i) {cout << "顶点 " << vertex_list[i].data << " 的邻接表: ";Edge* edge = vertex_list[i].first;while (edge) {cout << " -> " << vertex_list[edge->dest].data << " (权重 " << edge->weight << ")";edge = edge->next;}cout << endl;}}private:int V;Vertex* vertex_list;
};int main() {Graph g(5);// 根据图添加边  g.AddEdge(0, 1, 3); // A -> B  g.AddEdge(0, 2, 4); // A -> C  g.AddEdge(1, 0, 3); // B -> A  g.AddEdge(1, 3, 2); // B -> D  g.AddEdge(2, 0, 4); // C -> A  g.AddEdge(2, 3, 1); // C -> D  g.AddEdge(2, 4, 5); // C -> E  g.AddEdge(3, 1, 2); // D -> B  g.AddEdge(3, 2, 1); // D -> C  g.AddEdge(4, 2, 5); // E -> C  g.PrintGraph();return 0;
}

执行后, 输出如下:

顶点 A 的邻接表:  -> C (权重 4) -> B (权重 3) # 对于顶点 `A` 的邻接表：A -> C(4) -> B(3) 或者 A -> B(3) -> C(4) 都是正确的，它们表示的图结构是一样的。关键在于每个顶点的邻接节点及其对应的边权重是否正确记录。
顶点 B 的邻接表:  -> D (权重 2) -> A (权重 3)
顶点 C 的邻接表:  -> E (权重 5) -> D (权重 1) -> A (权重 4)
顶点 D 的邻接表:  -> C (权重 1) -> B (权重 2)
顶点 E 的邻接表:  -> C (权重 5)
2.3.2 优化封装

优点：

  • 简洁性：代码更简洁，易于阅读和维护。
  • 内存管理：使用 STL 容器，不需要手动管理内存，减少内存泄漏风险。
  • 灵活性：STL 容器操作更灵活，提供了更多的功能。
    缺点：
  • 抽象程度：链表的表示方式被隐藏在 STL 容器中，可能不够直观。
#include <iostream>
#include <vector>class Graph {
public:Graph(int vertices): vertices_(vertices) {adj_list_.resize(vertices_);}void AddEdge(int u, int v, int weight) {adj_list_[u].emplace_back(v, weight);adj_list_[v].emplace_back(u, weight); // 对于无向图，需要双向添加边}void PrintAdjList() const {for (int v = 0; v < vertices_; ++v) {std::cout << static_cast<char>('A' + v) << ": ";for (const auto& edge : adj_list_[v]) {std::cout << static_cast<char>('A' + edge.first) << " (权重 " << edge.second << ") ";}std::cout << std::endl;}}private:int vertices_;std::vector<std::vector<std::pair<int, int>>> adj_list_;
};int main() {Graph g(5);// 根据图添加边g.AddEdge(0, 1, 3); // A -> Bg.AddEdge(0, 2, 4); // A -> Cg.AddEdge(1, 3, 2); // B -> Dg.AddEdge(1, 4, 2); // B -> Eg.AddEdge(2, 3, 1); // C -> Dg.AddEdge(3, 4, 5); // D -> Eg.PrintAdjList();return 0;
}

2.4 总结

在邻接表表示法中，链表中顶点的顺序实际上是不重要的。邻接表的主要目的是表示每个顶点的邻接关系以及对应的边权重，因此，顶点的顺序并不会影响图的表示和算法的正确性。

总体来看，第二种封装方式更符合现代 C++ 编程规范，更加推荐。主要原因如下：

  1. 简洁性和可维护性：使用 STL 容器使代码更简洁，易于维护和扩展。
  2. 内存管理：STL 容器自动管理内存，减少内存泄漏的风险。
  3. 灵活性：STL 容器提供了丰富的操作接口，使用更加灵活。

当然, 如果你需要对图进行非常细粒度的控制，或者在非常严格的性能要求下，第一种封装方式可能更适合。

3 有向图的邻接表

假设有以下有向图，其中节点 A、B、C、D、E 表示城市，边表示城市之间的道路，权重表示道路的距离。

3.1 示例

    A----3---->B|         |4         2|         |v         vC<----1----D|     5     |v E

对应的邻接表为：

A -> B(3) -> C(4)
B -> D(2)
C -> E(5)
D -> C(1)
E ->

3.2 C++实现

#include <iostream>
#include <vector>class Graph {
public:Graph(int vertices): vertices_(vertices) {adj_list_.resize(vertices_);}void AddEdge(int u, int v, int weight) {adj_list_[u].emplace_back(v, weight);}/*// 对比无向图的, 向图中添加边:void AddEdge(int u, int v, int weight) {adj_list_[u].emplace_back(v, weight);adj_list_[v].emplace_back(u, weight); // 对于无向图，需要双向添加边}*/void PrintAdjList() const {for (int v = 0; v < vertices_; ++v) {std::cout << static_cast<char>('A' + v) << ": ";for (const auto& edge : adj_list_[v]) {std::cout << static_cast<char>('A' + edge.first) << " (权重 " << edge.second << ") ";}std::cout << std::endl;}}private:int vertices_;std::vector<std::vector<std::pair<int, int>>> adj_list_;
};int main() {Graph g(5);g.AddEdge(0, 1, 3); // A -> Bg.AddEdge(0, 2, 4); // A -> Cg.AddEdge(1, 3, 2); // B -> Dg.AddEdge(3, 2, 1); // D -> Cg.AddEdge(2, 4, 5); // C -> Eg.PrintAdjList();return 0;
}

3.3 总结

有向图表示的邻接表结构和无向图类似，只是边的方向性需要注意。

4 邻接图的遍历

// **图的遍历（DFS 和 BFS）**
#include <iostream>
#include <vector>
#include <stack>
#include <queue>class Graph {
public:Graph(int vertices): vertices_(vertices) {adj_list_.resize(vertices_);}void AddEdge(int u, int v, int weight) {adj_list_[u].emplace_back(v, weight);}void DFS(int start) {std::vector<bool> visited(vertices_, false);std::stack<int> stack;stack.push(start);while (!stack.empty()) {int v = stack.top();stack.pop();if (!visited[v]) {std::cout << static_cast<char>('A' + v) << " ";visited[v] = true;}for (const auto& edge : adj_list_[v]) {if (!visited[edge.first]) {stack.push(edge.first);}}}std::cout << std::endl;}void BFS(int start) {std::vector<bool> visited(vertices_, false);std::queue<int> queue;queue.push(start);visited[start] = true;while (!queue.empty()) {int v = queue.front();queue.pop();std::cout << static_cast<char>('A' + v) << " ";for (const auto& edge : adj_list_[v]) {if (!visited[edge.first]) {queue.push(edge.first);visited[edge.first] = true;}}}std::cout << std::endl;}void PrintAdjList() const {for (int v = 0; v < vertices_; ++v) {std::cout << static_cast<char>('A' + v) << ": ";for (const auto& edge : adj_list_[v]) {std::cout << static_cast<char>('A' + edge.first) << " (权重 " << edge.second << ") ";}std::cout << std::endl;}}private:int vertices_;std::vector<std::vector<std::pair<int, int>>> adj_list_;
};int main() {Graph g(5);g.AddEdge(0, 1, 3); // A -> Bg.AddEdge(0, 2, 4); // A -> Cg.AddEdge(1, 3, 2); // B -> Dg.AddEdge(3, 2, 1); // D -> Cg.AddEdge(2, 4, 5); // C -> Estd::cout << "邻接表:" << std::endl;g.PrintAdjList();std::cout << "DFS 从 A 开始:" << std::endl;g.DFS(0);std::cout << "BFS 从 A 开始:" << std::endl;g.BFS(0);return 0;
}

5 拓展补充

  • 时间复杂度分析：
    • 添加边：O(1) - 在邻接表中添加一条边的时间复杂度为常数时间，因为只需将新边添加到链表头部。
    • 删除边：O(E) - 删除一条边可能需要遍历整个链表，时间复杂度为 O(E)，其中 E 是链表的长度。
    • 查找邻接点：O(V) - 查找某个顶点的所有邻接点的时间复杂度为 O(V)，其中 V 是顶点的数量。
    • 查找某条边：O(E) - 查找某条边是否存在的时间复杂度为 O(E)，其中 E 是链表的长度。
  • 图的遍历：
    • **深度优先搜索（DFS）和广度优先搜索（BFS）**都可以在邻接表上高效实现。时间复杂度均为 O(V + E)，其中 V 是顶点的数量，E 是边的数量。
  • 存储结构：
    • 邻接表可以使用数组、链表、向量（std::vector）、哈希表（std::unordered_map）等数据结构来实现，具体选择取决于需求和编程语言。
  • 内存消耗：
    • 相比邻接矩阵（Adjacency Matrix），邻接表在稀疏图（Sparse Graph）上更加节省内存。对于具有 V 个顶点和 E 条边的图，邻接矩阵需要 O(V^2) 的空间，而邻接表只需要 O(V + E) 的空间。
  • 变种：
    • 加权图：每条边都有权重（已在示例中展示）。
    • 有向图和无向图：有向图的每条边有方向，反映在邻接表中只在一个方向上添加边；无向图在两个顶点之间添加双向边。
    • 多重图（Multigraph）：允许在两个顶点之间存在多条边。邻接表可以通过链表或向量来支持多重图。
  • 图的表示法转换：
    • 邻接表可以轻松转换为邻接矩阵，反之亦然，但在稀疏图上邻接表更有效。
  • 动态图：
    • 对于动态变化的图（例如频繁添加或删除边），邻接表比邻接矩阵更具优势，因为添加和删除操作更高效。

References

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/361309.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

springboot 整合redis

springboot 整合redis

文章目录 一、Jedis二、Lettuce三、RedisTemplate(重点)单机3.1 springboot 整合swagger3.2 序列化中文问题集群3.3 applications配置3.4 问题 一、Jedis package com.example.redis;import redis.clients.jedis.Jedis;import javax.print.DocFlavor; import java.util.*;/***…
阅读更多...
【编译原理】绪论

【编译原理】绪论

1.计算机程序语言以及编译 编译是对高级语言的翻译 源程序是句子的集合&#xff0c;树可以较好的反应句子的结构 编译程序是一种翻译程序 2.编号器在语言处理系统中的位置 可重定位&#xff1a;在内存中存放的起始位置不是固定的 加载器&#xff1a;修改可重定位地址&#x…
阅读更多...
古文字识别笔记

古文字识别笔记

前置知识 部件&#xff1a;大部分的汉字是由若干组笔画结构拼合而成的&#xff0c;这些相对独立的笔画结构称为「部件」。 部件是大于基本笔画&#xff08;例如&#xff1a;点、横、撇、捺等&#xff09;而小于或等同于 偏旁 的结构单位。 例如「测」字有三个部件&#xff1a;…
阅读更多...
【学习】使用PyTorch训练与评估自己的ResNet网络教程

【学习】使用PyTorch训练与评估自己的ResNet网络教程

参考&#xff1a;保姆级使用PyTorch训练与评估自己的ResNet网络教程_训练自己的图像分类网络resnet101 pytorch-CSDN博客 项目地址&#xff1a;GitHub - Fafa-DL/Awesome-Backbones: Integrate deep learning models for image classification | Backbone learning/comparison…
阅读更多...
高效修复机床导轨磨损，保障加工精度！

高效修复机床导轨磨损，保障加工精度！

机床导轨是支承和引导运动构件沿着一定轨迹运动的传动装置&#xff0c;在机器设备中是个十分重要的部件&#xff0c;在机床中是常见的部件。机床的加工精度与导轨精度有直接的联系&#xff0c;且导轨一旦损坏&#xff0c;维修较复杂且困难。我们简单总结了以下几点对于机床导轨…
阅读更多...
编程设计思想

编程设计思想

健康检查脚本 nmap:扫描端口 while true do healthycurl B:httpPORT/healthy -i | grep HTTP/1.1 | tail -n 1 | awk {print $2} done 批量操作类型脚本&#xff08;记录每一步日志&#xff09; 将100个nginx&#xff1a;vn推送到harbor仓库192.168.0.100 根据镜像对比sha值…
阅读更多...
【开源项目】自然语言处理领域的明星项目推荐：Hugging Face Transformers

【开源项目】自然语言处理领域的明星项目推荐：Hugging Face Transformers

在当今人工智能与大数据飞速发展的时代&#xff0c;自然语言处理&#xff08;NLP&#xff09;已成为推动科技进步的重要力量。而在NLP领域&#xff0c;Hugging Face Transformers无疑是一个备受瞩目的开源项目。本文将从项目介绍、代码解释以及技术特点等角度&#xff0c;为您深…
阅读更多...
面向对象修炼手册（四）（多态与空间分配）（Java宝典）

面向对象修炼手册（四）（多态与空间分配）（Java宝典）

&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;面向对象修炼手册 &#x1f4aa;&#x1f3fb; 十二月的寒冬阻挡不了春天的脚步&#xff0c;十二点的黑夜遮蔽不住黎明的曙光 目录 前言 1 多态 1.1 多态的形式&…
阅读更多...
需求之 实现获取调试信息在h5页面，在手机端可以查看调试（二）

需求之 实现获取调试信息在h5页面，在手机端可以查看调试（二）

事实证明 chatgpt很好用&#xff0c;有不懂的问题可以问它 https://zhuanlan.zhihu.com/p/690118775 国内外9个免费的ChatGPT网站 我筛选出来的比较好用免费的网站 fchat.dykyzdh.cn/ 这个也可以 阿里云的 通义灵码 在vscode中安装使用 而且阿里云有一个产品&#xff0c;可以…
阅读更多...
面试-Java线程池

面试-Java线程池

1.利用Excutors创建不同的线程池满足不同场景的需求 分析&#xff1a; 如果并发的请求的数量非常多&#xff0c;但每个线程执行的时间非常短&#xff0c;这样就会频繁的创建和销毁线程。如此一来&#xff0c;会大大降低系统的效率。 可能出现&#xff0c;服务器在为每个线程创建…
阅读更多...
jdk1.8升级到jdk11遇到的各种问题

jdk1.8升级到jdk11遇到的各种问题

一、第三方依赖使用了BASE64Decoder 如果项目中使用了这个类 sun.misc.BASE64Decoder&#xff0c;就会导致错误&#xff0c;因为再jdk11中&#xff0c;该类已经被删除。 Caused by: java.lang.NoClassDefFoundError: sun/misc/BASE64Encoder 当然这个类也有替换方式&#xf…
阅读更多...
MySQL实训--原神数据库

MySQL实训--原神数据库

原神数据库 er图DDL/DML语句查询语句存储过程/触发器 er图 DDL/DML语句 SET NAMES utf8mb4; SET FOREIGN_KEY_CHECKS 0;DROP TABLE IF EXISTS artifacts; CREATE TABLE artifacts (id int NOT NULL AUTO_INCREMENT,artifacts_name varchar(255) CHARACTER SET utf8 COLLATE …
阅读更多...
一文搞懂Linux多线程【下】

一文搞懂Linux多线程【下】

目录 &#x1f6a9;多线程代码的健壮性 &#x1f6a9;多线程控制 &#x1f6a9;线程返回值问题 &#x1f6a9;关于Linux线程库 &#x1f6a9;对Linux线程简单的封装 在观看本博客之前&#xff0c;建议大家先看一文搞懂Linux多线程【上】由于上一篇博客篇幅太长&#xff0c;为…
阅读更多...
文件操作＜C语言＞

文件操作＜C语言＞

导言 平时我们在写程序时&#xff0c;在运行时申请内存空间&#xff0c;运行完时内存空间被收回&#xff0c;如果想要持久化的保存&#xff0c;我们就可以使用文件&#xff0c;所以下文将要介绍一些在程序中完成一些文件操作。 目录 导言 文件流 文件指针 文件的打开与关闭 …
阅读更多...
《黑神话悟空》电脑配置要求

《黑神话悟空》电脑配置要求

《黑神话&#xff1a;悟空》这款国内优秀的3A游戏大作&#xff0c;拥有顶级的特效与故事剧情&#xff0c;自公布以来便备受玩家期待&#xff0c;其精美的画面与流畅的战斗体验&#xff0c;对玩家的电脑配置提出一定要求。那么这款优秀的游戏需要什么样的电脑配置&#xff0c;才…
阅读更多...
记录：[android] SSLHandshakeException: Handshake failed 问题；已解决！

记录：[android] SSLHandshakeException: Handshake failed 问题；已解决！

1、问题描述&#xff1a;在使用Retrofit2 时在安卓老设备上&#xff08;安卓6.0&#xff09;网络无法请求、安卓 10 、 11 未出现此问题&#xff1f;what? 原因&#xff1a;服务端 TLS 版本过高 2、废话不多说、解决方案A 、添加依赖&#xff1a;implementation org.conscrypt…
阅读更多...
黑马苍穹外卖6 清理redis缓存+Spring Cache+购物车的增删改查

黑马苍穹外卖6 清理redis缓存+Spring Cache+购物车的增删改查

缓存菜品 后端服务都去查询数据库&#xff0c;对数据库访问压力增大。 解决方式&#xff1a;使用redis来缓存菜品&#xff0c;用内存比磁盘性能更高。 key :dish_分类id String key “dish_” categoryId; RestController("userDishController") RequestMapping…
阅读更多...
游戏工厂：AI（AIGC/ChatGPT）与流程式游戏开发

游戏工厂：AI（AIGC/ChatGPT）与流程式游戏开发

游戏工厂&#xff1a;AI&#xff08;AIGC/ChatGPT&#xff09;与流程式游戏开发 码客 卢益贵 ygluu 关键词&#xff1a;AI&#xff08;AIGC、ChatGPT、文心一言&#xff09;、流程式管理、好莱坞电影流程、电影工厂、游戏工厂、游戏开发流程、游戏架构、模块化开发 一、前言…
阅读更多...
【每日刷题】Day75

【每日刷题】Day75

【每日刷题】Day75 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 1. 1833. 雪糕的最大数量 - 力扣&#xff08;LeetCode&#xff09; 2. 面试题 17.14. 最小K个数 - 力扣…
阅读更多...
LabVIEW电梯钢丝绳实时监测系统

LabVIEW电梯钢丝绳实时监测系统

电梯作为现代高层建筑中不可或缺的交通工具&#xff0c;其安全性直接影响到乘客的生命财产安全。电梯钢丝绳作为承载乘客与货物的关键部件&#xff0c;其健康状况尤为重要。传统的钢丝绳检测方法大多依赖于定期检查&#xff0c;无法实现实时监控&#xff0c;存在一定的安全隐患…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023