[高阶数据结构四] 初始图论

1.前言

本篇着重讲解图的相关知识，大家跟随我的脚步往下阅读。

本章重点：

本章着重讲解图的基本知识，图的存储结构：邻接矩阵，邻接表以及图的模拟实现

2.图的基本概念

首先明确一点，二叉树也是图的一种。 G1中的顶点就是结点0,1,2,3.记作v1,v2…,两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边，图中的第k条边记作ek，ek = (vi，vj)或<vi，vj>。

有向图和无向图： 在有向图中，顶点对 <x, y> 是有序的，顶点对 <x ， y> 称为顶点 x 到顶点 y 的一条 边 ( 弧 ) ， <x, y> 和 <y, x> 是两条不同的边 ，比如下图 G3 和 G4 为有向图。

在 无向图中，顶点对 (x, y) 是无序的，顶点对 (x,y) 称为顶点 x 和顶点 y 相关联的一条边，这条边没有特定方向， (x, y) 和 (y ， x) 是同一条边 ，比如上图 G1 和 G2 为无向图。注意： 无向边 (x, y) 等于有向边 <x, y> 和 <y, x> 。

例如：

3. 与图相关的专业名词

例如：

例如：

例如由A->D,那么路径可以有A->E->D / A->C->D /A->E->B->C->D等，路径长度就是相关值进行相+即可。 

例如：

例如：

例如：连通图：

强连通图：

图的概念和相关的转由名词较多，不可能一 一记下来，但是经常使用的话这些概念还是能够了解个大概得，概念这种东西不用背，但是你得知道。

4. 图的存储结构

因为图中既有节点，又有边 ( 节点与节点之间的关系 ) ，因此， 在图的存储中，只需要保存：节点和 边关系即可 。节点保存比较简单，只需要一段连续空间即可，那边关系该怎么保存呢？---通过邻接矩阵或者邻接表来保存

4.1 邻接矩阵

由于A和B/D是直接相连的，所以他们可以初始化为1.而A与C没有直接相邻，所以初始化为0. 

这是对于无向图来说，他们是关于45度对角线对称的，而对于有向图来说就不是这样了。看下面例子：

 对于有权值的边来说，如果两个点是连接的，那么就用权值表示，否则就表示无直接相连，用无穷大来表示。

4.2邻接表

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

1.无向图邻接表存储

A,B,C,D的下标分别是0,1,2,3.所以A顶点有两个相邻的顶点B和C. 链表中存的就是1,2

2.有向图邻接表存储

但是在后续我们只考虑出边表，不考虑入边表。

4.3 两者的优缺点分析

领接表的优点就是可以用比较少的时间，知道哪几个顶点是直接与我相连，而对于邻接矩阵来说不管相连多少都是O（N）--N为顶点的数量

缺点：他想要知道是否能A->C是否能够连通时，那么就必须要遍历一遍

对于邻接矩阵来说优点就是：想要知道A->C是否能够连通，那么只需要O（1）就够了。只需判断数组Arr[i][j]是否存在，存在那么就连通。

缺点就是：如果对于那种顶点很多，但是边很少的情况来说，矩阵就存储了大量的0元素，有点浪费空间。

5.图的模拟实现

在实现之前我们规定，用一个一位数组来存储顶点，二维矩阵则是存储的一位数组里面对应顶点的下标，由于后续需要通过顶点来找到下标，所以还需要一个哈希表来映射。

5.1 邻接矩阵模拟实现图

基本结构：

template<class V, class W, W int_MAX = INT_MAX, bool Direction = false>
class Graph
{
public:
	//图的创建方法: 1. IO输入(不方便测试) 2. 样例写在文件中,读取文件 3. 手动添加边
	Graph(const V* a,size_t n)
	{
		_vertex.reserve(n);
		for (int i = 0; i < n; i++)
		{
			_vertex.push_back(a[i]);
			_index[a[i]] = i;
		}
		_edge.resize(n);
		for (int i = 0; i < n; i++)
			_edge[i].resize(n, int_MAX);
	}
private:
	vector<V> _vertex; //图的顶点集合
	vector<vector<W>> _edge;//图的边的集合
	unordered_map<V, int> _index;//存储顶点和它映射到vector的下标的关系
};

V表示的是顶点的类型，W表示的是权值的类型，Direction中false表示的是无向，而true表示的是有向，int_MAX表示的是初始化为无穷大。 

在邻接矩阵里面我们需要实现的函数是：找顶点的下标的函数，然后添加边的函数。

代码如下：

//找到顶点对应的下标
	size_t GetIndex(const V& v)
	{
		if (_index.find(v) == _index.end())
		{
			cout << "要添加的边的顶点不存在" << endl;
			return -1;
		}
		return _index[v];
	}
	void AddEdge(const V& src, const V& dest, const W& w)//向图中添加边(源点,目标点,以及权值)
	{
		size_t srci = GetIndex(src);
		size_t desti = GetIndex(dest);
		_edge[srci][desti] = w;
		if (Direction == false) //这里判断的是有向图还是无向图
			_edge[desti][srci] = w;
	}

完整代码：

//邻接矩阵版本
template<class V, class W, W int_MAX = INT_MAX, bool Direction = false>
class Graph
{
public:
	//图的创建方法: 1. IO输入(不方便测试) 2. 样例写在文件中,读取文件 3. 手动添加边
	Graph(const V* a,size_t n)
	{
		_vertex.reserve(n);
		for (int i = 0; i < n; i++)
		{
			_vertex.push_back(a[i]);
			_index[a[i]] = i;
		}
		_edge.resize(n);
		for (int i = 0; i < n; i++)
			_edge[i].resize(n, int_MAX);
	}
	//找到顶点对应的下标
	size_t GetIndex(const V& v)
	{
		if (_index.find(v) == _index.end())
		{
			cout << "要添加的边的顶点不存在" << endl;
			return -1;
		}
		return _index[v];
	}
	void AddEdge(const V& src, const V& dest, const W& w)//向图中添加边(源点,目标点,以及权值)
	{
		size_t srci = GetIndex(src);
		size_t desti = GetIndex(dest);
		_edge[srci][desti] = w;
		if (Direction == false)
			_edge[desti][srci] = w;
	}
	void Print()
	{
		//打印顶点
		for (int i = 0; i < _edge[0].size(); i++)
			cout << "[" << i << "]" << "->" << _vertex[i] << endl;
		cout << endl;
		//打印矩阵
		for (int i = 0; i < _edge[0].size(); i++)
		{
			for (int j = 0; j < _edge[0].size(); j++)
			{
				if (_edge[i][j] == int_MAX)
					cout << "* ";
				else cout << _edge[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}
private:
	vector<V> _vertex; //图的顶点集合
	vector<vector<W>> _edge;//图的边的集合
	unordered_map<V, int> _index;//存储顶点和它映射到vector的下标的关系
};

void TestGraph()
{
	Graph<char, int, -1, true> g("0123", 4);
	g.AddEdge('0', '1', 1);
	g.AddEdge('0', '3', 4);
	g.AddEdge('1', '3', 2);
	g.AddEdge('1', '2', 9);
	g.AddEdge('2', '3', 8);
	g.AddEdge('2', '1', 5);
	g.AddEdge('2', '0', 3);
	g.AddEdge('3', '2', 6);
	g.Print();
}

输出结果如下：

5.2 邻接表的模拟实现

基本框架：

template <class W>
	struct LinkEdge
	{
		int _srcIndex;	//起始点下标
		int _dstIndex;	//要连接的下标
		W _w;			//权值
		LinkEdge* _next;    //下一个链接的边
		LinkEdge(const W& w)
			:_srcIndex(-1)
			,_dstIndex(-1)
			,_w(w)
			,_next(nullptr)
		{}
	};
template <class V,class W,bool Direcation=false>
	class Table {
	public:
		typedef LinkEdge<W> Edge;
		Table(const V* ver,size_t n)
		{
			//外部传进来几个顶点以及顶点的个数
			_ver.resize(n);
			for (int i = 0; i < n; i++)
			{
				_ver[i] = ver[i];
				_umapIndex[ver[i]] = i;
			}

			//邻接表开辟好空间
			_Table.resize(n, nullptr);
		}
	private:
		vector<V> _ver;//用来存储顶点
		unordered_map<V, int> _umapIndex;//用来存储顶点、下标的映射关系
		vector<Edge*> _Table;//边的集合的临接表
	};

和邻接矩阵类似，需要知道下标函数和添加边的函数

template <class V,class W,bool Direcation=false>
	class Table {
	public:
		//得到下标
		int GetIndex(const V& v)
		{
			auto it = _umapIndex.find(v);
			if (it == _umapIndex.end())
			{
				cout << "这个值没有对应的下标，即查找下标出错" << endl;
				return -1;
			}
			else return _umapIndex[v];
		}
		//添加边进去
		void AddEdge(const V& src, const V& dst,const W& w)
		{
			//先找到下标
			int srci = GetIndex(src);
			if (srci == -1) return;
			int dsti = GetIndex(dst);
			if (dsti == -1) return;

			//找到之后开始链接--头插法
			Edge* newedge = new Edge(w);
			newedge->_srcIndex = srci;
			newedge->_dstIndex = dsti;
			newedge->_next = _Table[srci];
			_Table[srci] = newedge;
			
			//判断有向还是无向图
			if (Direcation == false)
			{
				Edge* newedge = new Edge(w);
				newedge->_srcIndex = dsti;
				newedge->_dstIndex = srci;
				newedge->_next = _Table[dsti];
				_Table[dsti] = newedge;
			}
		}
	};

整体代码：

template <class V,class W,bool Direcation=false>
	class Table {
	public:
		typedef LinkEdge<W> Edge;
		Table(const V* ver,size_t n)
		{
			//外部传进来几个顶点以及顶点的个数
			_ver.resize(n);
			for (int i = 0; i < n; i++)
			{
				_ver[i] = ver[i];
				_umapIndex[ver[i]] = i;
			}

			//邻接表开辟好空间
			_Table.resize(n, nullptr);
		}
		//得到下标
		int GetIndex(const V& v)
		{
			auto it = _umapIndex.find(v);
			if (it == _umapIndex.end())
			{
				cout << "这个值没有对应的下标，即查找下标出错" << endl;
				return -1;
			}
			else return _umapIndex[v];
		}
		//添加边进去
		void AddEdge(const V& src, const V& dst,const W& w)
		{
			//先找到下标
			int srci = GetIndex(src);
			if (srci == -1) return;
			int dsti = GetIndex(dst);
			if (dsti == -1) return;

			//找到之后开始链接--头插法
			Edge* newedge = new Edge(w);
			newedge->_srcIndex = srci;
			newedge->_dstIndex = dsti;
			newedge->_next = _Table[srci];
			_Table[srci] = newedge;
			
			//判断有向还是无向图
			if (Direcation == false)
			{
				Edge* newedge = new Edge(w);
				newedge->_srcIndex = dsti;
				newedge->_dstIndex = srci;
				newedge->_next = _Table[dsti];
				_Table[dsti] = newedge;
			}
		}
		void Print()
		{
			//先打印下标映射关系
			for (size_t i = 0; i < _ver.size(); i++)
			{
				cout << "[" << _ver[i] << "]" << ": " << i << endl;
			}

			//然后打印边
			for (size_t i = 0; i < _Table.size(); i++)
			{
				cout << i << "->";
				Edge* cur = _Table[i];
				while (cur)
				{
					cout << "[" << cur->_dstIndex <<"]" << "->";
					cur = cur->_next;
				}
				cout << endl;
			}
		}
	private:
		vector<V> _ver;//用来存储顶点
		unordered_map<V, int> _umapIndex;//用来存储顶点、下标的映射关系
		vector<Edge*> _Table;//边的集合的临接表
	};
	void TestGraph()
	{
		string a[] = { "张三", "李四", "王五", "赵六" };
		Table<string, int> g1(a, 4);
		g1.AddEdge("张三", "李四", 100);
		g1.AddEdge("张三", "王五", 200);
		g1.AddEdge("王五", "赵六", 30);
		g1.Print();
	}

6.总结

这里两种图的存储结构的模拟实现都进行了讲解，但是后面真正使用的更多的是在邻接矩阵的基础上，所以一定要非常熟练邻接矩阵的相关实现。且邻接矩阵也是为了后续的图的遍历、最小生成树和最短路径的算法打下基础。一定要好好掌握。