【数据结构】图的创建（邻接矩阵，邻接表）以及深度广度遍历（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;}