【数据结构与算法】图——邻接表与邻接矩阵-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】图——邻接表与邻接矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、图的基本概念

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E），其中，G表示一个图，V是顶点的集合，E是边的集合。
在图中数据元素，我们则称之为顶点（Vertex）。
图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

有上面的定义可以得出树是一个特殊的图，与图的区别是没有环连通。
树关注的是节点（顶点）的值，而图关注的是顶点及边的权值。

图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。

比方说现在想表示社交关系，那么QQ，微信等就是无向图，抖音微博这种就是有向图（你关注的人不一定关注了你）。

图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。
图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。
图上的边或弧上带权则称为网。
一个图包含了另一个图的部分顶点和部分边，就叫做子图。
图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环（回路），当中不重复叫简单路径。若无向图任意两顶点都是连通的，则图就是连通图，有向则称强连通图。
生成树： 在无向图中，一个连通图的最小连通子图称作该图的生成树。有 n 个顶点的连通图的生成树有 n 个顶点和 n-1 条边。

二、图的存储结构

一个图的信息包括两部分，即图中顶点的信息以及描述顶点之间的关系 ---- 边或者弧的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两个面的信息。下面介绍两种常用的图的存储结构。这篇介绍两个常见的结构：邻接矩阵和邻接表。

2.1 邻接矩阵

因为节点与节点之间的关系就是联通与否，即为 0 或者 1，因此邻接矩阵（二维数组）即是：先用一个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。
【数据结构与算法】图——邻接表与邻接矩阵
可以看出无向图是对称的，而有向图没有对称关系。
如果边是带权值的且两个顶点不相连，我们可以用INT_MAX或者INT_MIN来表示。

邻接矩阵存储图的优点是能够快速知道图中两个顶点是否连通，缺点是顶点很多且边比较少时，比较浪费空间，并且两个节点之间的路径不好求。若要确定图中有多少条边，需要遍历一遍邻接矩阵，空间复杂度为 O(N^2) 。这是用邻接矩阵来存储图的局限性。

所以邻接矩阵适合存稠密图，适合查找两个顶点是否相连

2.2 邻接表

邻接表：使用数组表示顶点的集合，使用链表表示边的关系。

用数组保存顶点，用链表保存连通的顶点。
【数据结构与算法】图——邻接表与邻接矩阵
邻接表适合存稀疏图，适合查找一个顶点连出去的边

2.3 邻接矩阵的实现

邻接矩阵有以下的模板参数：

template <class V, class W, W MAX = INT_MAX, bool DIR = false>

V - 顶点，W - 权值，MAX - 最大值(默认参数给整形的最大值)，DIR - 表示图是否有方向。

template <class V, class W, W MAX = INT_MAX, bool DIR = false>
class Graph
{
public:
private:
	vector<V> _vertexs;// 顶点集合
	unordered_map<V, int> _idxMap;// 顶点映射下标
	vector<vector<W>> _matrix;// 邻接矩阵
};

构造函数
我们传进一个数组和一个size_t型数据，数组里面存放顶点，数据表示数组的大小。
在内部我们首先要把每个顶点存储起来，并初始化邻接矩阵，把权值全部初始化成MAX代表不相连。

Graph(const V* a, size_t n)
{
	_vertexs.reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		_vertexs.push_back(a[i]);// 将传入数组的值存储到vector中
		_idxMap[a[i]] = i;// 让数组中的每一个数据映射一个下标
	}

	_matrix.resize(n);
	for (size_t i = 0; i < n; i++)
	{
		_matrix[i].resize(n, MAX);
	}
}

添加边

首先要获取两个顶点的下标，然后还要判断是有向图还是无向图，无向图要添加两次。

// 获取顶点下标
size_t GetIdx(const V& v)
{
	auto it = _idxMap.find(v);
	if (it == _idxMap.end())
	{
		assert(false);
		return -1;
	}
	return it->second;
}

void addEdge(const V& src, const V& dst, const W& w)
{
	size_t si = GetIdx(src);
	size_t di = GetIdx(dst);
	_matrix[si][di] = w;
	if (DIR == false)
	{
		_matrix[di][si] = w;
	}
}

打印观察

void Print()
{
	// 打印矩阵横坐标
	cout << "  ";
	for (size_t i = 0; i < _vertexs.size(); ++i)
	{
		printf("%5d", i);
	}
	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)
				printf("%5c", '*');
			else
				printf("%5d", _matrix[i][j]);
		}
		cout << endl;
	}
}

整体代码

template <class V, class W, W MAX = INT_MAX, bool DIR = 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]);// 将传入数组的值存储到vector中
			_idxMap[a[i]] = i;// 让数组中的每一个数据映射一个下标
		}

		_matrix.resize(n);
		for (size_t i = 0; i < n; i++)
		{
			_matrix[i].resize(n, MAX);
		}
	}

	// 获取顶点下标
	size_t GetIdx(const V& v)
	{
		auto it = _idxMap.find(v);
		if (it == _idxMap.end())
		{
			assert(false);
			return -1;
		}
		return it->second;
	}

	void addEdge(const V& src, const V& dst, const W& w)
	{
		size_t si = GetIdx(src);
		size_t di = GetIdx(dst);
		_matrix[si][di] = w;
		if (DIR == false)
		{
			_matrix[di][si] = w;
		}
	}
	void Print()
	{
		// 打印顶点和下标间的映射关系
		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
		}
		cout << endl;

		// 打印矩阵横坐标
		cout << "  ";
		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			printf("%5d", i);
		}
		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)
					printf("%5c", '*');
				else
					printf("%5d", _matrix[i][j]);
			}
			cout << endl;
		}
	}

private:
	vector<V> _vertexs;// 顶点集合
	unordered_map<V, int> _idxMap;// 顶点映射下标
	vector<vector<W>> _matrix;// 邻接矩阵
};

void TestGraph()
{
	Graph<char, int, INT_MAX, false> g("ABCDE", 5);
	g.addEdge('A', 'B', 1);
	g.addEdge('B', 'D', 4);
	g.addEdge('A', 'D', 2);
	g.addEdge('B', 'C', 9);
	g.addEdge('A', 'C', 8);
	g.addEdge('E', 'A', 5);
	g.addEdge('A', 'E', 3);
	g.addEdge('C', 'D', 6);
	g.Print();
}

【数据结构与算法】图——邻接表与邻接矩阵

2.4 邻接表的实现

邻接表里面存的是边，所以我们要设计一个边的类。

template <class W>
struct Edge
{
	Edge(int dsti, const W& w)
		: _dsti(dsti)
		, _w(w)
		, _next(nullptr)
	{}
	int _dsti;
	W _w;// 权值
	Edge<W>* _next;
};

当要加入一个边的时候，直接头插即可。
其他的和邻接矩阵同理。

template <class W>
struct Edge
{
	Edge(int dsti, const W& w)
		: _dsti(dsti)
		, _w(w)
		, _next(nullptr)
	{}
	int _dsti;
	W _w;// 权值
	Edge<W>* _next;
};

template <class V, class W, bool DIR = 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]);// 将传入数组的值存储到vector中
			_idxMap[a[i]] = i;// 让数组中的每一个数据映射一个下标
		}
		_tables.resize(n, nullptr);
	}

	// 获取顶点下标
	size_t GetIdx(const V& v)
	{
		auto it = _idxMap.find(v);
		if (it == _idxMap.end())
		{
			assert(false);
			return -1;
		}
		return it->second;
	}

	void addEdge(const V& src, const V& dst, const W& w)
	{
		size_t si = GetIdx(src);
		size_t di = GetIdx(dst);
		Edge<W>* eg = new Edge<W>(di, w);
		eg->_next = _tables[si];
		_tables[si] = eg;
		if (DIR == false)
		{
			Edge<W>* eg = new Edge<W>(si, w);
			eg->_next = _tables[di];
			_tables[di] = 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<W>* cur = _tables[i];
			while (cur)
			{
				cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
				cur = cur->_next;
			}
			cout << "nullptr" << endl;
		}
	}

private:
	vector<V> _vertexs;// 顶点集合
	unordered_map<V, int> _idxMap;// 顶点映射下标
	vector<Edge<W>*> _tables;// 邻接表
};

void TestGraph()
{
	Graph<char, int, true> g("ABCDE", 5);
	g.addEdge('A', 'B', 1);
	g.addEdge('B', 'D', 4);
	g.addEdge('A', 'D', 2);
	g.addEdge('B', 'C', 9);
	g.addEdge('A', 'C', 8);
	g.addEdge('E', 'A', 5);
	g.addEdge('A', 'E', 3);
	g.addEdge('C', 'D', 6);
	g.Print();
}

【数据结构与算法】图——邻接表与邻接矩阵

三、总结

根据邻接表和邻接矩阵的结构特性可知，当图为稀疏图、顶点较多，即图结构比较大时，更适宜选择邻接表作为存储结构。当图为稠密图、顶点较少时，或者不需要记录图中边的权值时，使用邻接矩阵作为存储结构较为合适。
邻接表和邻接矩阵相辅相成，各有优缺点，是互补的。文章来源地址https://www.toymoban.com/news/detail-433608.html

到了这里，关于【数据结构与算法】图——邻接表与邻接矩阵的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！