高阶数据结构-------图

文章目录

• 图
• • • 图的基本概念
    • 图的存储结构
    • • • 邻接矩阵
        • 邻接表
    • 图的遍历
    • • • 广度优先遍历
        • 深度优先遍历
    • 最小生成树
    • • • Kruskal算法
        • Prim算法
    • 最短路径
    • • • 单源最短路径-Dijkstra算法
        • 单源最短路径-Bellman-Ford算法
        • 多源最短路径-Floyd-Warshall算法

图

图的基本概念

图的基本概念

图是由顶点集合和边的集合组成的一种数据结构，记住G = （V， E）。

有向图和无向图：

• 在有向图中，顶点对<x, y> 是有序的，顶点对<x, y> 称为顶点x到顶点y的一条边，<x, y> 和<y, x>是两条不同的边。
• 在无向图中，顶点对（x，y）是无序的，顶点对（x，y）称为顶点x和顶点y相关联的一条边，这条边没有特定的方向，（x，y）和（y， x）是同一条边。

如下图：

完全图：

• 在有n个顶点的无向图中，若有n*（n-1）/2条边，即任意两个顶点之间都有直接相连的边，则称此图为无向完全图。
• 在有n个顶点的有向图中，若有n*（n-1）条边，即任意两个顶点之间都有双向的边，则称此图为有向完全图。

如下图：

邻接顶点：

• 在无向图中，若（u，v）是图中的一条边，则称u和v互为邻接顶点，并称边（u，v）依附于顶点u和顶点v。
• 在有向图中，若<u, v>是图中的一条边，则称顶点u邻接到顶点v，顶点v邻接自顶点u，并称边<u, v>与顶点u和顶点v相关联。

顶点的度：

• 在有向图中，顶点的度等于该顶点的入度与出度之和，顶点的入度是以该顶点为终点的边的条数，顶点的出度是以该顶点为起点的边的条数。
• 在无向图中，顶点的度等于该顶点相关联的边的条数，同时也等于该顶点的入度和出度。

路径与路径长度：

• 若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到vj的路径。
• 对于不带权的图，一条路径的长度是指该路径上的边的条数，对于带权图，一条路径的长度是指该路径上各个边权值的总合。

带权图示例：

简单路径与简单回路：

• 若路径上的各个顶点均不相同，则称这样的路径为简单路径。
• 若路径上第一个顶点与最后一个顶点相同，则称这样的路径为回路或环。

如下图：

子图：

• 设图G = （V，E）和图G1 = （V1， E1），若V1属于V且E1属于E，则称G1是G的子图。

如下图：

连通图和强连通图：

• 在无向图中，若从顶点 v 1 v1v1 到顶点 v 2 v2v2 有路径，则称顶点 v 1 v1v1 与顶点 v 2 v2v2 是连通的，如果图中任意一对顶点都是连通的，则称此图为连通图。
• 在有向图中，若每一对顶点 v i vivi 和 v j vjvj 之间都存在一条从 v i vivi 到 v j vjvj 的路，也存在一条从 v j vjvj 到 v i vivi 的路，则称此图是强连通图。

生成树与最小生成树：

• 一个连通图的最小连通子图称为该图的生成树，有n个顶点的连通图的生成树有n个顶点和n-1条边。
• 最小生成树指的是一个图的生成树当中，总权值最小的生成树。

图的相关应用场景

图常见的表示场景如下：

• 交通网络：图中的每个顶点表示一个地点，图中的边表示这两个地点之间是否有直接相连的公路，边的权值可以是这两个地点之间的距离、高铁时间等。
• 网络设备拓扑：图中的每个顶点表示网络中的一个设备，图中的边表示这两个设备之间是否可以互传数据，边的权值可以是这两个设备之间传输数据所需的时间、丢包的概率等。
• 社交网络：图中的每个顶点表示一个人，图中的边表示这两个人是否互相认识，边的权值可以是这两个人之间的亲密度、共同好友个数等。

关于有向图和无向图：

• 交通网络对应的图可以是有向图，也可以是无向图，无向图对应就是双向车道，有向图对应就是单向车道。
• 网络设备拓扑对应的图通常是无向图，两个设备之间有边表示这两个设备之间可以互相收发数据。
• 社交网络对应的图可以是有向图，也可以是无向图，无向图通常表示一些强社交关系，比如QQ、微信等（一定互为好友），有向图通常表示一些弱社交关系，比如微博、抖音（不一定互相关注）。

图的其他相关作用：

• 在交通网络中，根据最短路径算法计算两个地点之间的最短路径，根据最小生成树算法得到将各个地点连通起来所需的最小成本。
• 在社交网络中，根据广度优先搜索得到两个人之间的共同好友进行好友推荐，根据入边表和出边表得知有哪些粉丝以及关注了哪些博主。

图与树的联系与区别

图与树的主要联系与区别如下：

• 树是一种有向无环且连通的图（空树除外），但图并不一定是树。
• 有 n 个结点的树必须有 n − 1 条边，而图中边的数量不取决于顶点的数量。
• 树通常用于存储数据，并快速查找目标数据，而图通常用于表示某种场景。

图的存储结构

图由顶点和边组成，存储图本质就是将图中的顶点和边存储起来。

邻接矩阵

邻接矩阵

1. 用一个数组存储顶点集合，顶点所在位置的下标作为该顶点的编号（所给顶点可能不是整形）。
2. 用一个二维数组matrix存储边的集合，其中matrix[i][j]表示编号为i和j的两个顶点之间的关系。

如下图：

说明一下：

• 对于不带权的图，两个顶点之间要么相连，要么不想连，可以用0和1表示，matrix[i][j]为1表示编号i和j的两个顶点相连，为0表示不相连。
• 对于带权图，连接两个顶点的边会带有一个权值，可以用这个权值来设置对于matrix[i][j]的值，如果两个顶点不相连，则使用不会出现的权值进行设置即可（图中为无穷大）。
• 对于无向图来说，顶点i和顶点j相连，那么顶点j就和顶点i相连，因此无向图对应的邻接矩阵是一个对称矩阵，即matrix[i][j]的值等于matrix[j][i]的值。
• 在邻接矩阵中，第i行元素中有效权值的个数就是编号为i的顶点的出度，第i列元素中有效元素的个数就是编号为i的顶点的入度。

邻接矩阵的优缺点

邻接矩阵的优点：

• 邻接矩阵适合存储稠密图，因为存储稠密图和稀疏图时所开辟的二维数组大小是相同的，因此图中的边越多，邻接矩阵的优势越明显。
• 邻接矩阵能够O(1)的判断两个顶点是否相连，并获得相连边的权值。

邻接矩阵的缺点：

• 邻接矩阵不适合查找一个顶点连接出去的所有边，需要遍历矩阵中对应的一行，该过程的时间复杂度是O(N)，其中N表示顶点的个数。

邻接矩阵的实现

邻接矩阵所需成员变量：

• 数组vertexs：用于存储顶点集和，顶点所在位置的下标作为该顶点的编号。
• 映射关系indexMap：用于建立顶点与其下标的映射关系，便于根据顶点找到其对应的下标编号。
• 邻接矩阵matrix：用于存储边的集和，matrix[i][j]表示编号i和j的两个顶点之间的关系。

邻接矩阵的实现：

• 为了支持任意类型的顶点类型以及权值，可以将图定义为模板，其中V和W分别表示顶点和权值的类型，MAX_W表示两个顶点没有连接时邻接矩阵中存储的值，将MAX_W的缺省值设置为INT_MAX（权值一般为整型），Direction表示图是否为有向图，将Direction的缺省值设置为false（无向图居多）。
• 在构造函数中完成顶点集和的设置，并建立各个顶点与其下标的映射关系，同时为邻接矩阵开辟空间，将矩阵中的值初始化为MAX_W，表示刚开始时各个顶点之间均不相连。
• 提供一个接口用于添加边，在添加边时先分别获取源顶点和目标顶点对应的下标编号，然后再将邻接矩阵中对应位置设置为边的权值，如果图为无向图，则还需要在邻接矩阵中添加目标顶点到源顶点的边。
• 在获取顶点对应的下标时，先在indexMap中进行查找，如果找到了对应的顶点，则返回该顶点对应的下标编号，如果没有找到对应的顶点，则说明所给顶点不存在，此时可以抛出异常。

代码如下：

//邻接矩阵
namespace matrix
{
	//顶点值，权值类型设置成模板
	template<class V, class W, W MAX_W = INT_MAX, bool direction = false>	//不存在的边设置为无穷大，默认是无向图	
	class Graph
	{
	public:
		//构造
		Graph(const vector<V>& v)
			:_vertexs(v.begin(), v.end())
			,_matrix(v.size(), vector<W>(v.size(), MAX_W))
		{
			for (int i = 0; i < v.size(); i++)
				_indexMap[v[i]] = i;	//建立顶点下标映射
		}
		//顶点值获得下标
		int getIndex(const V& v)	//提供该接口转换顶点和下标，不能直接_indexMap[v]不存在会插入
		{
			auto iter = _indexMap.find(v);	//怕给错了顶点
			if (iter != _indexMap.end())	//存在该顶点
				return iter->second;
			else
			{
				throw invalid_argument("不存在此顶点");
				return -1;
			}
		}
		//增加边
		void addEdge(const V& src, const V& dst, const W& weight)
		{
			int srci = getIndex(src), dsti = getIndex(dst);
			_matrix[srci][dsti] = weight;	//设置边的权值
			if (direction == false)
			{
				_matrix[dsti][srci] = weight;	//无向图
			}
		}
		//打印图
		void print()
		{
			int n = _vertexs.size();
			//先打印顶点
			for (int i = 0; i < n; i++)
			{
				cout << "[" << i << "]->" << _vertexs[i] << endl;
			}
			cout << endl;
			printf("%4c", ' ');
			//打印索引
			for (int i = 0; i < n; i++)
				printf("%4d", i);
			cout << endl;
			for (int i = 0; i < n; i++)
			{
				printf("%4d", i);
				//打印边
				for (int j = 0; j < n; j++)
				{
					if (_matrix[i][j] == MAX_W)
						printf("%4c", '*');
					else
						printf("%4d", _matrix[i][j]);
				}
				cout << endl;
			}
			cout << endl;
		}
	private:
		vector<V> _vertexs;	//顶点表
		vector<vector<W>> _matrix;	//邻接矩阵
		unordered_map<V, int> _indexMap;	//建立顶点和下标映射关系
	};

说明一下：

• 为了方便观察，可以在类中增加一个print接口，用于打印顶点集和和邻接矩阵。
• 后续图的相关算法都会以邻接矩阵为例进行讲解，因为一般只有比较稠密的图才会存在最小生成树和最短路径的问题。

邻接表

邻接表

邻接表存储图的方式如下：

1. 用一个数组存储顶点集和，顶点所在的位置的下标作为该顶点的编号（所给顶点可能不是整型）。
2. 用一个出边表存储各个顶点连接出去的边，出边表中下标为i的位置存储的是从编号为i的顶点连接出去的边。
3. 用一个入边表存储连接各个顶点的边，入边表中下标为i的位置存储的是连接到编号为i的顶点的边。

如下图：

说明一下：

• 出边表和入边表类似于哈希桶，其中每个位置存储的是一个链表，出边表中下标为i的位置的链表中存储的都是从编号为i的顶点连接出去的边，入边表中下标为i的位置的链表存储的都是连接到编号为i的顶点的边。
• 在邻接表中，出边表中下标为i的位置的链表中元素的个数就是编号为i的顶点的出度，入边表中下标为i的位置的链表中元素的个数就是编号为i的顶点的入度。
• 在实现邻接表时，一般只需要用一个出边表来存储从各个顶点连接出去的边即可，因为大多数情况下都是需要从一个顶点出发找与其相连的其它顶点，所以一般不需要存储入边表。

邻接表的优缺点

邻接表的优点：

• 邻接表适合存储稀疏图，因为邻接表存储图时开辟的空间大小取决于边的数量，图中边的数量越少，邻接表存储边时所需的内存空间就越少。
• 邻接表适合查找一个顶点连接出去的所有边，出边表中下标为i的位置的链表中存储的就是从顶点连接出去的所有边。

邻接表的缺点：

• 邻接表不适合确定两个顶点是否相连，需要遍历出边表中源顶点对应位置的链表，该过程的时间复杂度是O(E)，其中E表示从源顶点连接出去的边的数量。

邻接表的实现

链表结点所需成员变量：

• 目标顶点下标dsti：表示边的目标顶点。
• 权值weight：表示边的权值。
• 指针next：连接下一个结点。

代码如下：

//邻接表
namespace link_table
{
	//邻接表中描述一条邻接的点
	//模板类，边的权值类型不确定
	template<class W>
	struct Edge
	{
		int _dsti;	//邻接点的编号
		W _weight;		//邻接点边的权值
		Edge* _next;		//指向下一个点的
		//构造函数
		Edge(int dsti, W weight)
			:_dsti(dsti)
			,_weight(weight)
			,_next(nullptr)		//new出来一个结点，next默认指向空
		{}
	};
}

说明一下：

• 对应出边表来说，下标为i的位置的链表中存储的边的源顶点都是顶点i，所有链表结点中的源顶点成员可以不用存储。

邻接表所需成员变量：

• 数组vertexs：用于存储顶点集和，顶点所在位置的下标作为该顶点的编号。
• 映射关系indexMap：用于建立顶点与其下标的映射关系，便于根据顶点找到其对应的下标编号。
• 邻接表（出边表）linktable：用于存储边的集和，linktable[i]链表中存储的边的源顶点都是顶点i。

邻接表的实现：

• 为了支持任意类型的顶点类型以及权值，可以将图定义为模板，其中V和W分别表示顶点和权值的类型，direction表示图是否为有向图，将direction的缺省值设置为false(无向图居多).
• 在构造函数中完成顶点集和的设置，并建立各个顶点与其对应下标的映射关系，同时为邻接表开辟空间，将邻接表中的值都初始化为空指针，表示刚开始时各个顶点之间均不相连。
• 提供一个接口用于添加边，在添加边时先分别获取源顶点和目标顶点对应的下标编号，然后在源顶点对应的链表中头插一个边结点，如果图为无向图，则还需要在目标顶点对应的链表中头插一个边结点。

代码如下：

//邻接表
namespace link_table
{
	//邻接表中描述一条邻接的点
	//模板类，边的权值类型不确定
	template<class W>
	struct Edge
	{
		int _dsti;	//邻接点的编号
		W _weight;		//邻接点边的权值
		Edge* _next;		//指向下一个点的
		//构造函数
		Edge(int dsti, W weight)
			:_dsti(dsti)
			,_weight(weight)
			,_next(nullptr)		//new出来一个结点，next默认指向空
		{}
	};
	template<class V, class W, bool direction = false>	//默认是无向图，顶点值和权值设置为模板类
	class Graph
	{
		typedef Edge<W> Edge;
	public:
		//构造函数
		Graph(const vector<V>& v)
			:_vertexs(v.begin(), v.end())	//初始化顶点集
			,_linktable(v.size(), nullptr)
		{
			//建立顶点值和下标之间的映射关系
			for (int i = 0; i < v.size(); i++)
				_indexMap[v[i]] = i;
		}
		//顶点值获得下标
		int getIndex(const V& v)	//提供该接口转换顶点和下标，不能直接_indexMap[v]不存在会插入
		{
			auto iter = _indexMap.find(v);	//怕给错了顶点
			if (iter != _indexMap.end())	//存在该顶点
				return iter->second;
			else
			{
				throw invalid_argument("不存在此顶点");
				return -1;
			}
		}
		//增加边
		void addEdge(const V& src, const V& dst, const W& weight)
		{
			int srci = getIndex(src), dsti = getIndex(dst);	//顶点值转下标
			Edge* sdEdge = new Edge(dsti, weight);	//new 一个结点头插到邻接表src位置
			sdEdge->_next = _linktable[srci];
			_linktable[srci] = sdEdge;
			//如果是无向图，反着再来一下
			if (direction == false)
			{
				Edge* dsEdge = new Edge(srci, weight);
				dsEdge->_next = _linktable[dsti];
				_linktable[dsti] = dsEdge;
			}
		}
		//打印图
		void print()
		{
			int n = _vertexs.size();
			for (int i = 0; i < n; i++)
			{
				cout << "["<<i<<"]" << ":" << _vertexs[i] << "->";
				Edge* cur = _linktable[i];
				while (cur)
				{
					cout << "[" << cur->_dsti << "]" << ":" << _vertexs[cur->_dsti] << "W:" << cur->_weight << "->";
					cur = cur->_next;
				}
				cout << "nullptr" << endl;
			}
		}
	private:
		vector<V> _vertexs;		//顶点表
		vector<Edge*> _linktable;	//邻接表
		unordered_map<V, int> _indexMap;	//顶点值下标映射集合
	};
	void testGraph()
	{
		vector<string> v = { "张三", "李四", "王五", "赵六", "田七", "雷儿子" };
		Graph<string, int> g(v);
		g.addEdge("张三", "雷儿子", 100);
		g.addEdge("张三", "李四", 63);
		g.addEdge("王五", "田七", 109);
		g.addEdge("赵六", "雷儿子", 500);
		g.addEdge("张三", "王五", 60);
		g.addEdge("王五", "李四", 10);
		g.print();
	}
}

说明一下：

• 为了方便观察，可以在类中增加一个print接口，用于打印顶点集和和邻接表。

图的遍历

图的遍历指的是遍历图中的顶点，主要有广度优先遍历和深度优先遍历两种方式。

广度优先遍历

广度优先遍历

广度优先遍历又称BFS，其遍历过程类似于二叉树的层序遍历，从起始顶点开始一层一层向外进行遍历。

如下图：

广度优先遍历的实现：

• 广度优先遍历需要借助一个队列和一个标记数组，利用队列先进先出的特点实现一层一层向外遍历，利用标记数组来记录各个顶点是否被访问过。
• 刚开始时将起始顶点入队列，并将起始顶点标记为访问过，然后不断从队列中取出顶点进行访问，并判断该顶点是否有邻接顶点，如果有邻接顶点并且该邻接顶点没有被访问过，则将该邻接顶点入队列，并在入队列后立即将该邻接顶点标记为访问过。

代码如下：

void BFS(const V& src)
{
	int n = _vertexs.size();
	int srci = getIndex(src);	//从起点开始bfs
	queue<int> q;
	vector<bool> vis(n, false);
	q.push(srci);
	vis[srci] = true;
	while (!q.empty())
	{
		int front = q.front();
		q.pop();
		cout << "[" << front << "]" << ":" << _vertexs[front] << "->";
		for (int i = 0; i < n; i++)
		{
			if (_matrix[front][i] != MAX_W && !vis[i])
			{
				q.push(i);
				vis[i] = true;
			}
		}
	}
	cout << "nullptr" << endl;
}

说明一下：

• 为了防止顶点被重复加入队列导致死循环，因此需要一个标记数组，当一个顶点被访问过后就不应该再将其加入队列了。
• 如果当一个顶点从队列中取出访问时才再将其标记为访问过，也可能会存在顶点被重复加入队列的情况，比如当图中的顶点B出队列时，顶点C作为顶点B的邻接顶点并且还没有被访问过（顶点C还在队列中），此时顶点C就会再次被加入队列，因此最好在一个顶点被入队列时就将其标记为访问过。
• 如果所给图不是一个连通图，那么从一个顶点开始进行广度优先遍历，无法遍历完图中的所有顶点，这时可以遍历标记数组，查看哪些顶点还没有被访问过，对于没有被访问过的顶点，则从该顶点处继续进行广度优先遍历，直到图中所有的顶点都被访问过

深度优先遍历

深度优先遍历

深度优先遍历又称DFS，其遍历过程类似于二叉树的先序遍历，从起始顶点开始不断对顶点进行深入遍历。

如下图：

深度优先遍历的实现：

• 深度优先遍历可以通过递归实现，同时也需要借助一个标记数组来记录各个顶点是否被访问过
• 从起始顶点处开始进行递归遍历，在遍历过程中先对当前顶点进行访问，并将其标记为访问过，然后判断该顶点是否有邻接顶点，如果有邻接顶点并且该邻接顶点没有被访问过，则递归遍历该邻接顶点

代码如下：

void _DFS(int srci, vector<bool>& vis)
{
	cout << "[" << srci << "]" << ":" << _vertexs[srci] << "->";
	vis[srci] = true;
	for (int i = 0; i < _vertexs.size(); i++)
	{
		if (_matrix[srci][i] != MAX_W && !vis[i])
			_DFS(i, vis);
	}
}
void DFS(const V& src)
{
	int n = _vertexs.size();
	int srci = getIndex(src);
	vector<bool> vis(n, false);
	_DFS(srci, vis);
}

说明一下：

• 如果所给图不是一个连通图，那么从一个顶点开始进行深度优先遍历，无法遍历完图中的所有顶点，这时可以遍历标记数组，查看哪些顶点还没有被访问过，对于没有被访问过的顶点，则从该顶点处继续进行深度优先遍历，直到图中所有的顶点都被访问过。

最小生成树

最小生成树

关于最小生成树：

• 一个连通图的最小连通子图称为该图的生成树，若连通图由 n nn 个顶点组成，则其生成树必含 n nn 个顶点和 n − 1 n-1n−1 条边，最小生成树指的是一个图的生成树中，总权值最小的生成树。
• 连通图中的每一棵生成树都是原图的一个极大无环子图，从其中删去任何一条边，生成树就不再连通，在其中引入任何一条新边，都会形成一条回路。

说明一下：

• 对于各个顶点来说，除了第一个顶点之外，其他每个顶点想要连接到图中，至少需要一条边使其连接进来，所以由 n nn 个顶点的连通图的生成树有 n nn 个顶点和 n − 1 n-1n−1 条边。
• 对于生成树来说，图中的每个顶点已经连通了，如果再引入一条新边，那么必然会使得被新边相连的两个顶点之间存在一条直接路径和一条间接路径，即形成回路。
• 最小生成树是图的生成树中总权值最小的生成树，生成树是图的最小连通子图，而连通图是无向图的概念，有向图对应的是强连通图，所以最小生成树算法的处理对象都是无向图。

构成最小生成树的准则

1. 构造最小生成树的准则如下：
2. 只能使用恰好 n − 1 n-1n−1 条边来连接图中的 n nn 个顶点。
3. 选用的 n − 1 n-1n−1 条边不能