【数据结构】图的创建(邻接矩阵,邻接表)以及深度广度遍历(BFS,DFS)

本文主要是介绍【数据结构】图的创建(邻接矩阵,邻接表)以及深度广度遍历(BFS,DFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
    • 1.图的存储结构
      • 1.邻接矩阵
      • 2.邻接表
  • 一、邻接矩阵
  • 二、邻接表
  • 二、图的遍历
    • 1.DFS
    • 2.BFS


前言

图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E),其中:
顶点集合V = {x|x属于某个数据对象集}是有穷非空集合;
E = {(x,y)|x,y属于V}或者E = {<x, y>|x,y属于V && Path(x, y)}是顶点间关系的有穷集合,也叫
做边的集合。
完全图:在有n个顶点的无向图中,若有n * (n-1)/2条边,即任意两个顶点之间有且仅有一条边,
则称此图为无向完全图,比如上图G1;在n个顶点的有向图中,若有n * (n-1)条边,即任意两个
顶点之间有且仅有方向相反的边,则称此图为有向完全图

1.图的存储结构

因为图中既有节点,又有边(节点与节点之间的关系),因此,在图的存储中,只需要保存:节点和
边关系即可。
节点保存比较简单,只需要一段连续空间即可,那边关系该怎么保存呢?

1.邻接矩阵

因为节点与节点之间的关系就是连通与否,即为0或者1,因此邻接矩阵(二维数组)即是:先用一
个数组将定点保存,然后采用矩阵来表示节点与节点之间的关系。

在这里插入图片描述

2.邻接表

在这里插入图片描述

一、邻接矩阵

主要思想就是,先建立顶点与数组下标的映射关系,我们通过这个两个顶点对应的下标,确定其在二维数组(邻接矩阵)中的位置,然后将邻接矩阵对应位置修改为权值(找顶点与下标关系之所以还要一个函数来控制而不用哈希表是因为我们要找的顶点可能不存在,如果用哈希表就会直接将这个不存在的顶点插入进去)

namespace matrix {//V为顶点类型,W为边权值类型,MAX_W为权值最大值也就是无效值//Direction用来判断是不是有向图,false为无向图template<class V, class W, W  MAX_W = INT_MAX, bool Direction = false>class Graph {public:Graph(const V* a, size_t n) {_vertexs.reserve(n);for (size_t i = 0; i < n; i++) {_vertexs.push_back(a[i]);_indexMap[a[i]] = i;//将顶点存入_vertexs,下标映射存进map}_matrix.resize(n);for (size_t i = 0; i < _matrix.size(); i++) {_matrix[i].resize(n, MAX_W);//邻接矩阵默认初始值为无效值}}size_t GetVertexIndex(const V& v) {//获得对应顶点在数组中的下标auto it = _indexMap.find(v);if (it != _indexMap.end()) {return it->second;//有这个顶点返回其下标}else {throw("顶点不存在");return -1;}}void _AddEdge(size_t srci, size_t dsti, const W& w) {//存入权值_matrix[srci][dsti] = w;if (Direction == false) {_matrix[dsti][srci] = w;//无向图要两个方向都存}}void AddEdge(const V& src, const V& dst, const W& w) {//添加边与顶点的关系。从src到dst方向的关系size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);//先获取其对应的下标_AddEdge(srci, dsti, w);}void Print() {for (size_t i = 0; i < _vertexs.size(); i++) {cout << "[" << i << "]" << "->" << _vertexs[i] << endl;}//打印顶点集cout << endl;//打印邻接矩阵for (size_t i = 0; i < _matrix.size(); i++) {cout << i << " ";for (size_t j = 0; j < _matrix[i].size(); j++) {if (_matrix[i][j] == MAX_W) {printf("%4c", '*');}else {printf("%4d", _matrix[i][j]);}}cout << endl;}}private:vector<V>_vertexs;//顶点集合map<V, int>_indexMap;//存顶点与数组下标的映射关系vector<vector<W>>_matrix;//邻接矩阵};}

用邻接矩阵存储图的有点是能够快速知道两个顶点是否连通,缺陷是如果顶点比较多,边比
较少时,矩阵中存储了大量的0成为系数矩阵,比较浪费空间,并且要求两个节点之间的路
径不是很好求。

二、邻接表

namespace link_table {template<class W>struct Edge {//Edge用来保存边的关系,当作结点来使int _dsti;//目标顶点对应下标W _w;//权值Edge<W>* _next;Edge(int dsti, const W& w):_dsti(dsti),_w(w),_next(nullptr){}};template<class V, class W, bool Direction = false>class Graph {typedef Edge<W> Edge;//注意这里typedf要传参public:Graph(const V* a, size_t n) {_vertexs.reserve(n);for (int i = 0; i < n; i++) {_vertexs.push_back(a[i]);_indexMap[a[i]] = i;//将顶点放入数组,并建立顶点与下标的映射关系}_tables.resize(n, nullptr);}size_t GetVertexIndex(const V& v) {//查找顶点对应的下标,这里不直接用哈希表//来查是因为顶点可能不存在auto it = _indexMap.find(v);if (it != _indexMap.end()) {return it->second;}else {throw ("顶点不存在");return -1;}}void AddEdge(const V& src, const V& dst, const W& w) {size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);Edge* eg = new Edge(dsti, w);eg->_next = _tables[srci];_tables[srci] = eg;if (Direction == false) {//如果为无向图,两个顶点都要加权值记录Edge* eg = new Edge(srci, w);eg->_next = _tables[dsti];_tables[dsti] = eg;}}void Print() {for (size_t i = 0; i < _vertexs.size(); i++) {cout << "[" << i << "]" << _vertexs[i] << endl;}//打印顶点集合cout << endl;//打印邻接表for (size_t i = 0; i < _tables.size(); i++) {cout << _vertexs[i] << "[" << i << "]->";Edge* cur = _tables[i];while (cur) {cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << endl;cur = cur->_next;}cout << "nullptr" << endl;}}private:vector<V>_vertexs;//顶点数组vector<Edge*>_tables;//邻接表map<V, int> _indexMap;//顶点与下标的映射关系};}

二、图的遍历

1.DFS

在这里插入图片描述

	void _DFS(size_t srci, vector<bool>& visited) {cout << srci << ":" << _vertexs[srci] << endl;visited[srci] = true;//标记这个顶点被访问过了for (size_t i = 0; i < _vertexs.size(); i++) {if (_matrix[srci][i] != MAX_W && visited[i] == false) {_DFS(i, visited);}}}void DFS(const V& src) {size_t srci = GetVertexIndex(src);vector<bool>visited(_vertexs.size(), false);_DFS(srci, visited);}

2.BFS

在这里插入图片描述

void BFS(const V& src) {size_t srci = GetVertexIndex(src);queue<int>q;q.push(srci);vector<bool>visited(_vertexs.size(), false);visited[srci] = true;//标记这个顶点被访问过了int levelSize = 1;while (!q.empty()) {//levelSize为当前层的大小for (size_t i = 0; i < levelSize; i++) {int front = q.front();q.pop();cout << front << ":" << _vertexs[front]<<" ";for (size_t i = 0; i < _vertexs.size(); i++) {if (_matrix[front][i] != MAX_W && visited[i] == false) {q.push(i);visited[i] = true;//标记这个顶点被访问过了}}}levelSize = q.size();//更新当前层的数量cout << endl;}cout << endl;}

这篇关于【数据结构】图的创建(邻接矩阵,邻接表)以及深度广度遍历(BFS,DFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/523613

相关文章

python如何创建等差数列

《python如何创建等差数列》:本文主要介绍python如何创建等差数列的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python创建等差数列例题运行代码回车输出结果总结python创建等差数列import numpy as np x=int(in

怎么用idea创建一个SpringBoot项目

《怎么用idea创建一个SpringBoot项目》本文介绍了在IDEA中创建SpringBoot项目的步骤,包括环境准备(JDK1.8+、Maven3.2.5+)、使用SpringInitializr... 目录如何在idea中创建一个SpringBoot项目环境准备1.1打开IDEA,点击New新建一个项

如何使用Maven创建web目录结构

《如何使用Maven创建web目录结构》:本文主要介绍如何使用Maven创建web目录结构的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录创建web工程第一步第二步第三步第四步第五步第六步第七步总结创建web工程第一步js通过Maven骨架创pytho

MySQL 用户创建与授权最佳实践

《MySQL用户创建与授权最佳实践》在MySQL中,用户管理和权限控制是数据库安全的重要组成部分,下面详细介绍如何在MySQL中创建用户并授予适当的权限,感兴趣的朋友跟随小编一起看看吧... 目录mysql 用户创建与授权详解一、MySQL用户管理基础1. 用户账户组成2. 查看现有用户二、创建用户1. 基

Python中使用uv创建环境及原理举例详解

《Python中使用uv创建环境及原理举例详解》uv是Astral团队开发的高性能Python工具,整合包管理、虚拟环境、Python版本控制等功能,:本文主要介绍Python中使用uv创建环境及... 目录一、uv工具简介核心特点:二、安装uv1. 通过pip安装2. 通过脚本安装验证安装:配置镜像源(可

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

Java中实现线程的创建和启动的方法

《Java中实现线程的创建和启动的方法》在Java中,实现线程的创建和启动是两个不同但紧密相关的概念,理解为什么要启动线程(调用start()方法)而非直接调用run()方法,是掌握多线程编程的关键,... 目录1. 线程的生命周期2. start() vs run() 的本质区别3. 为什么必须通过 st

Macos创建python虚拟环境的详细步骤教学

《Macos创建python虚拟环境的详细步骤教学》在macOS上创建Python虚拟环境主要通过Python内置的venv模块实现,也可使用第三方工具如virtualenv,下面小编来和大家简单聊聊... 目录一、使用 python 内置 venv 模块(推荐)二、使用 virtualenv(兼容旧版 P

Linux lvm实例之如何创建一个专用于MySQL数据存储的LVM卷组

《Linuxlvm实例之如何创建一个专用于MySQL数据存储的LVM卷组》:本文主要介绍使用Linux创建一个专用于MySQL数据存储的LVM卷组的实例,具有很好的参考价值,希望对大家有所帮助,... 目录在Centos 7上创建卷China编程组并配置mysql数据目录1. 检查现有磁盘2. 创建物理卷3. 创

python进行while遍历的常见错误解析

《python进行while遍历的常见错误解析》在Python中选择合适的遍历方式需要综合考虑可读性、性能和具体需求,本文就来和大家讲解一下python中while遍历常见错误以及所有遍历方法的优缺点... 目录一、超出数组范围问题分析错误复现解决方法关键区别二、continue使用问题分析正确写法关键点三