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

发布于:2024-11-28 ⋅ 阅读:(32) ⋅ 点赞:(0)

1.前言

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

本章重点:

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

2.图的基本概念

图是由顶点集合及顶点间的关系组成的一种数据结构: G = (V E) ,其中:
顶点集合 V = {x|x 属于某个数据对象集 } 是有穷非空集合
E = {(x,y)|x,y 属于 V} 或者 E = {<x, y>|x,y 属于 V && Path(x, y)} 是顶点间关系的有穷集合,也叫
做边的集合
(x, y) 表示 x y 的一条双向通路,即 (x, y) 是无方向的; Path(x, y) 表示从 x y 的一条单向通路,即
Path(x, y) 是有方向的。
顶点和边: 图中结点称为顶点 ,第 i 个顶点记作 vi 两个顶点 vi vj 相关联称作顶点 vi 和顶点 vj 之间
有一条边 ,图中的第 k 条边记作 ek ek = (vi vj) <vi vj>

上述说了这么多抽象概念,相信很多人都不太理解。直接上例子

例:

首先明确一点,二叉树也是图的一种。 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. 与图相关的专业名词

完全图:在 n 个顶点的无向图中 ,若 n * (n-1)/2 条边 ,即 任意两个顶点之间有且仅有一条边
则称此图为 无向完全图 ,比如上图 G1 ;在 n 个顶点的有向图 中,若 n * (n-1) 条边 ,即 任意两个
顶点之间有且仅有方向相反的边 ,则称此图为 有向完全图 ,比如上图 G4
邻接顶点:在 无向图中 G 中,若 (u, v) E(G) 中的一条边,则称 u v 互为邻接顶点 ,并称 (u,v)
附于顶点 u v ;在 有向图 G 中,若 <u, v> E(G) 中的一条边,则称顶点 u 邻接到 v ,顶点 v 邻接自顶
u ,并称边 <u, v> 与顶点 u 和顶点 v 相关联
顶点的度 顶点 v 的度是指与它相关联的边的条数,记作 deg(v) 。在有向图中, 顶点的度等于该顶
点的入度与出度之和 ,其中顶点 v 入度是以 v 为终点的有向边的条数 ,记作 indev(v); 顶点 v 出度
是以 v 为起始点的有向边的条数 ,记作 outdev(v) 。因此: dev(v) = indev(v) + outdev(v) 。注
意:对于 无向图,顶点的度等于该顶点的入度和出度 ,即 dev(v) = indev(v) = outdev(v)

例如:

路径 :在图 G = (V E) 中,若 从顶点 vi 出发有一组边使其可到达顶点 vj ,则称顶点 vi 到顶点 vj 的顶
点序列为从顶点 vi 到顶点 vj 的路径
路径长度 :对于 不带权的图,一条路径的路径长度是指该路径上的边的条数 ;对于 带权的图,一
条路 径的路径长度是指该路径上各个边权值的总和

例如:

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

简单路径与回路 若路径上各顶点 v1 v2 v3 vm 均不重复,则称这样的路径为简单路
若路 径上第一个顶点 v1 和最后一个顶点 vm 重合,则称这样的路径为回路或环

例如:

子图 设图 G = {V, E} 和图 G1 = {V1 E1} ,若 V1 属于 V E1 属于 E ,则称 G1 G 的子图

例如:

连通图 :在 无向图 中,若从顶点 v1 到顶点 v2 有路径,则称顶点 v1 与顶点 v2 是连通的。 如果图中任
意一 对顶点都是连通的,则称此图为连通图。也就是说图中可以任意选两个点都可以到达。
强连通图 :在 有向图 中,若在 每一对顶点 vi vj 之间都存在一条从 vi vj 的路径,也存在一条从 vj
vi 的路径,就称之为强连通图

例如:连通图:

强连通图:

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

4. 图的存储结构

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

4.1 邻接矩阵

因为节点与节点之间的关系就是连通与否,即为 0 或者 1 ,因此 邻接矩阵 ( 二维数组 ) 即是:先用一
个数组将定点保存,然后采用矩阵来表示节点与节点之间的关系 。如有一个n*n的矩阵,那么数组arr[i][j]表示i顶点到j顶点边的值,如果不是直接相连,那就初始化为最初值,否则就是边的权值。

由于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.总结

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