• 数据结构＜7＞ 图

    文章目录

    图的定义

    图是一种非线性结构，前面说过的一种非线性结构就是树，树是由节点组成的具有跟单额分层结构，各个顶点之间是父子关系，一个顶点最多有一个父节点，但是可以有0个到任意多个子节点。
    图的节点与树不同，图的每个节点可以与任意个其他顶点相连。各个顶点之间的关系是任意的。由此我们也可看出图的表示范围是要比树大的，树是一种特殊的图。

    图的基本概念

    **图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)，也就是顶点和边。这里的G代表Graph，V代表vertex（顶点），e代表edge（边）。 **

    顶点集合V = {x|x属于某个数据对象集}是有穷非空集合，比如顶点可以是一组人名，地名，等等类似的对象集。

    边的集合 E = {(x,y)|x,y属于V}或者E = {|x,y属于V && Path(x, y)}是顶点间关系的有穷集合。
    (x, y)表示x到y的一条双向通路，即(x, y)是无方向的；Path(x, y)表示从x到y的一条单向通路，即Path(x, y)是有方向的。有方向的边一般使用来表示。因此根据边的有方向和无方向就分出两种图：无向图和有向图
    在这里插入图片描述

    顶点之间通过直线相连的就是无向图，G1和G2
    顶点之间通过箭头相连的就是有向图，G3和G4，这里的箭头表示单方向通路。

    在讨论图之前我们需要记住下面的几条规则：

    1. 不考虑顶点有直接与自身相连的边（自环）
    2. 无向图中两个顶点不能有多条边相连（一条就是双向通路）

    完全图（complate graph） 在由n个顶点组成的无向图中，有n*(n - 1) / 2条边就是完全图，即每个顶点都和剩下的n-1个顶点直接相连。有向图中则需要n*(n - 1)条边，因为每条边是单向的。

    权值（weight） 一条边所具有的数值关系称为权重，权重可以表示例如：两个顶点之间的距离，所需时间，等等。带权图又被叫做网络（network）
    在这里插入图片描述

    **邻接顶点（adjacent vertex）**如果（u，v）是图的一条边，那么u和v就是互为邻接顶点，如果是有向图
    就称顶点u邻接到顶点v。顶点v邻接字顶点u。

    **子图（subgraph）**子图就是顶点数目保持不变，减少边的数量，设图G = {V, E}和图G1 = {V1，E1}，若V1属于V且E1属于E，则称G1是G的子图。
    在这里插入图片描述

    顶点的度（degree）与顶点v相关联的边的数量，就称为是v的度 ，在有向图中，顶点的度代表的的是出度和入度的边的数量之和，在无向图中顶点的度就是顶点连接出去的边的数量。

    路径（path）：在图G = (V， E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。经过的顶点序列为（vi，vp1，vp2，…，vpm，vj）
    路径长度（path length）：对于无权图，路径长度就是边的数目，对于带权图就是路径上各条边的权值之和。
    简单路径与回路（cycle）：如果路径中经过的顶点序列（vi，vp1，vp2，…，vpm，vj）中没有重复顶点则称该路径为简单路径。若是路径中起点与终点是重合的，这样的路径就是回路。
    在这里插入图片描述

    连通图与连通分量：在无向图中如果一个顶点与另一个顶点有路径相连（不一定是直接相连，可能经过中间节点），那么这两个顶点就是连通的，如果一个顶点与剩下的n-1个顶点都是连通的，那么这个图就是连通图。在非连通图中的最大连通子图就是连通分量。
    强连通图与强连通分量： 在有向图中，如果每一对vi顶点到vj顶点之间有一条路径，从vj顶点到vi顶点之间也有一条路径就称此图是强连通图。
    非强连通图的最大连通子图就是强连通分量。

    生成树（spanning tree）： 在一个无向连通图中，生成树就是他的最小连通子图，假设图中有n个顶点，那么生成树应该是有n-1条边构成。如果是有向图则可能是由若干有向树组成的森林。

    图的存储结构

    图的存储结构常用的有两种：邻接矩阵和邻接表。

    邻接矩阵

    使用矩阵来存储顶点之间的关系，矩阵的行列数就是顶点的个数，比如我们可以使用0，1来表示i和j顶点是不是连通的。
    在这里插入图片描述

    邻接矩阵的特点：

    1. 邻接矩阵非常适合稠密图（边多的图）因为不管有多少条边，邻接矩阵的大小都是固定的n*n，如果边比较稀疏，就会造成大量的空间浪费。
    2. 邻接矩阵可以在O(1)的时间内判断两个顶点的连接关系，并且拿到两顶点间边的权值。
    3. 邻接矩阵不适合查找一个顶点连接出去的所有边，因为要遍历矩阵的一行或者一列，时间复杂度是O(N)。

    注意：

    1. 如果是无向图，那么他的邻接矩阵是对称的，无向图的就不一定是对称的了。因为edge[i][j]表示的是从i到j的边并不一定从j到i还有通路。
    2. 如果图是一个带权图，那么邻接矩阵里面可以保存权值。比如有向图里面从i到j的边权值是10，那么edge[i][j] = 10;

    邻接表存储无向图的时候是一个对称矩阵，因此我们可以使用矩阵压缩，将一个矩阵从二维压缩到一维，可以减少是一半的空间消耗。这里不多介绍。

    下面是图存放在邻接矩阵的代码，关于图的生成有很多方式，比如一个顶点一个顶点的添加，然后连接起来。也可以读文件来生成图表我们这里使用的是初始化给出顶点的个数，然后再连接。

    #pragma once
#include
#include
#include
#include
#include
#include
#include
#include"UnionFindSet.h"

namespace Matrix
{
	template< class W>
	struct Edge
	{
		int _srci;	//存储顶点的下标
		int _desti;
		W _w;		//权值

		Edge(int srci,int desti,const W& w)
			:_srci(srci)
			,_desti(desti)
			,_w(w)
		{}
		//重载 > 用于适配仿函数的比较器
		bool operator>(const Edge<W>& e) const
		{
			return _w > e._w;
		}
	};

	//V表示vertex（顶点）
	//W表示weight（权值）
	template<class V,class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Edge<W> Edge;
		typedef Graph<V, W, MAX_W, false> Self;
	public:
		Graph() = default;		//让编译器自动生成一个默认构造函数

		Graph(int n,const V* val)
		{
			_vertex.reserve(n);
			for (int i = 0; i < n; i++)
			{
				_vertex.push_back(val[i]);	//初始化顶点集合
				_indexMap[val[i]] = i;		//建立顶点和下标的映射关系，方便在O(1)的时间内查找到顶点的下标
			}
			_matrix.resize(n);
			for (int i = 0; i < n; i++)
			{
				_matrix[i].resize(n, MAX_W);
			}
		}

		//查找顶点对应的下标
		size_t FindVertexIndex(const V& src)
		{
			auto ret = _indexMap.find(src);
			if (ret == _indexMap.end())
			{
				cout << "查询的顶点下标不存在" << endl;
				assert(false);
				return -1;
			}
			return ret->second;		//ret是一个iterator --> pair
		}

		//手动添加边(通过两个顶点和连接之间的权值添加边)
		void AddEdge(const V& src,const V& dest,const W& val)
		{
			size_t srci = FindVertexIndex(src);
			size_t desti = FindVertexIndex(dest);

			_AddEdge(srci, desti, val);
		}
		void _AddEdge(size_t srci, size_t desti, const W& val)
		{
			_matrix[srci][desti] = val;
			if (Direction == false)
			{
				_matrix[desti][srci] = val;
			}
		}

		void Print() const
		{
			//先打印出顶点集合
			for (size_t i = 0; i < _vertex.size(); i++)
			{
				cout << _vertex[i] << " 下标： " << i << endl;
			}
			cout << endl;
			//打印顶点与下标的映射
			for (auto item : _indexMap)
			{
				cout << item.first << " 映射-> " << item.second << endl;
			}
			cout << endl;
			//打印邻接矩阵
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				for (size_t j = 0; j < _matrix[i].size(); j++)
				{
					if (i == j)
						cout << "0 ";
					else if (_matrix[i][j] == MAX_W)
						cout << "# ";
					else
						cout << _matrix[i][j] << " ";
				}
				cout << endl;
			}
		}
	private:
		vector<V> _vertex;//顶点集合
		unordered_map<V, int> _indexMap;//顶点与下标映射
		vector<vector<W>> _matrix; //邻接矩阵
	};
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121

    这就是使用邻接矩阵来存储图的结构代码。这里的边我独立了一个类出来，方便后序对边进行操作，边里面放的就是起点和终点的下标，以及边的权值。

    邻接表

    邻接表，就是单链表的组合，首先根据顶点数，n个顶点就开辟n个空间的指针数组，每个数组用来存放节点的指针，这里的节点是指邻接表这里的单链表的节点。

    邻接表这里我们将每个顶点连接出去的边都创建成一个节点（节点里面存放终点顶点的下标，边的权值和next指针）然后将这些节点连接成单链表。
    在这里插入图片描述

    这里使用邻接表存放的是无向图
    针对有向图我们可能需要两个表，入边表和出边表。但是实际中很少存两个邻接表，一般都是存一个出边表。
    在这里插入图片描述

    邻接表的特点：

    1. 适合稀疏图，邻接表适合存边比较少的图，这样可以减少每个单链表的长度提高效率，同时减少了需要开辟的节点数目。
    2. 适合查找一个顶点连接的邻接顶点。
    3. 不适合用来判断两个顶点是否相连。（这种操作需要遍历起点的链表查找终点是不是在链表内，也要查找终点的链表看是不是起点也在其链表内。）

    注意：有向图中每条边在邻接表中只出现一次，与顶点vi对应的链表所含结点的个数，就是该顶点的出度，也称出度表，要得到vi顶点的入度，必须检测其他所有顶点对应的链表，看有多少边顶点的dest取值是i。

    namespace LinkTable
{
	template<class W>
	struct LinkNode
	{
		size_t _index;
		W _w;
		LinkNode<W>* _next;

		LinkNode(size_t index,const W& w)
			:_index(index)
			,_w(w)
			,_next(nullptr)
		{}
	};
	template<class V,class W,bool Direction = false>
	class Graph
	{
		typedef LinkNode<W> Node;
	public:
		Graph() = default;

		Graph(int n, const V* val)
		{
			_vertex.reserve(n);
			for (int i = 0; i < n; i++)
			{
				_vertex.push_back(val[i]);
				_indexMap[val[i]] = i;
			}
			_linktable.resize(n, nullptr);
		}
		
		size_t FindVertexIndex(const V& src)
		{
			auto ret = _indexMap.find(src);
			if (ret == _indexMap.end())
			{
				cout << "查询的顶点下标不存在" << endl;
				assert(false);
				return -1;
			}
			return ret->second;
		}

		void AddEdge(const V& src, const V& dest, const W& w)
		{
			size_t srci = FindVertexIndex(src);
			size_t desti = FindVertexIndex(dest);

			Node* newnode = new Node(desti, w);
			newnode->_next = _linktable[srci];
			_linktable[srci] = newnode;
			if (Direction == false)
			{
				Node* newnode = new Node(srci, w);
				newnode->_next = _linktable[desti];
				_linktable[desti] = newnode;
			}
		}

		void Print()const
		{
			//先打印出顶点集合
			for (size_t i = 0; i < _vertex.size(); i++)
			{
				cout << _vertex[i] << " 下标： " << i << endl;
			}
			cout << endl;
			//打印顶点与下标的映射
			for (auto item : _indexMap)
			{
				cout << item.first << " 映射-> " << item.second << endl;
			}
			cout << endl;
			//打印邻接表
			for (size_t i = 0; i < _linktable.size(); i++)
			{
				cout << _vertex[i] << ": ";
				Node* tmp = _linktable[i];
				while (tmp)
				{
					cout << "[ " << _vertex[tmp->_index] << " 权值：" << tmp->_w << " ]->";
					tmp = tmp->_next;
				}
				cout << "nullptr" << endl;
			}
		}

	private:
		vector<V> _vertex;
		unordered_map<V, int> _indexMap;
		vector<Node*> _linktable;
	};
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95

    邻接表的插入操作是类似于邻接矩阵的，只是增加边的时候将修改邻接矩阵改成了单链表的头插。

    图的遍历

    这里需要注意的是图的遍历针对的是图的顶点，并不是图的边。

    图的遍历就是给定一个起始顶点v0，然后从该顶点开始遍历所有的顶点，为了保证所有的顶点都能访问到，需要一个数组来存放所有顶点的访问标志，如果图不是连通图，无论是BFS还是DFS都是不可能一次就访问完所有的顶点的。所以这时我们就可以遍历标志数组，找到没有访问的顶点，以此为起点再次进行BFS或者是DFS。

    深度优先搜索(DFS)

    深度优先搜索这里我们可以回忆一下以前遍历树的时候，前序遍历就是一个类似的深度优先搜索，不断向深处走，走到底部再回溯。

    这里有一个例子，形象的描述的DFS
    在这里插入图片描述

    现在有如下一个图，我们对其进行DFS
    在这里插入图片描述

    如图所画的路程，我们是先往深处走，假设A是第一层，B，C，D就是第二层，DFS的顺序是先向深走，回溯的时候再访问其他节点。
    我们在进行DFS过程中所有访问过的顶点和经过的边，连接起来，他们构成了一个连通无环图，也就是树，这个树我们称为原图的深度优先生成树，简称是DFS树。因为DFS遍历了n个顶点，所以DFS树包含了n-1条边。下图就是DFS树。
    在这里插入图片描述

    下面我们来看一下DFS的代码。

    		//采用递归方式进行深度优先
		void DFS(const V& v)
		{
			size_t vi = FindVertexIndex(v);

			vector<bool> visited;
			visited.resize(_vertex.size(), false);

			_DFS(vi, visited);
			//处理非连通图一次遍历访问不了所有的顶点
			for (int i = 0; i < visited.size(); i++)
			{
				if (visited[i] == false)
					_DFS(i, visited);
			}
		}

		void _DFS(size_t vi, vector<bool>& visited)
		{
			cout << "[ index: " << vi << " val: " << _vertex[vi] <<" ] " << endl;
			visited[vi] = true;
			for (size_t i = 0; i < _vertex.size(); i++)
			{
				if (_matrix[vi][i] != MAX_W && visited[i] == false)
					_DFS(i, visited);
			}
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    这里的图使用的邻接矩阵，从此开始，包括后面的所有算法我用的都是邻接矩阵来保存图。
    关于DFS的时间复杂度：如果使用邻接表存储图，连着linkTable单链表就可以一次取出顶点v所有邻接顶点，假设共有n个顶点，e条边，所以我们存放在linkTable里面的节点最多就有2e个，所以我们扫描边查找邻接顶点的时间为O(e)，每个顶点最多遍历一次，所以总的时间复杂度就是O(n + e)。
    如果使用的是邻接矩阵，我们每次遍历到一个顶点要查找他的邻接顶点都需要遍历矩阵的一行或者一列，总计n个节点，总时间复杂度就是O(n^2)。

    广度优先搜索(BFS)

    广度优先遍历就是逐层访问，每一层有多少顶点，就先把这一层的顶点访问完，然后再访问下一层，BFS过程如下图：
    在这里插入图片描述

    如果还是不理解广度优先的访问顺序可以看下面这个例子

    在这里插入图片描述

    实现层序遍历的方法类似于在树哪里的层序遍历，为了实现逐层访问我们需要一个对列来暂时存放节点。
    从对列中拿出一个节点就将该节点的邻接顶点放入队列，同时也需要visited数组标记，防止重复访问。

    		void BFS(const V& src)
		{
			int srci = FindIndex(src);
			int n = _vertex.size();

			vector<bool> visited(n, false);
			queue<int> que;
			que.push(srci);
			visited[srci] = true;
			int levelsize = 1;

			while (!que.empty())
			{
				for (int k = 0; k < levelsize; k++)
				{
					int vi = que.front();
					que.pop();
					cout << "[ index : " << vi << " val: " << _vertex[vi] << "] ";
					for (int i = 0; i < n; i++)
					{
						if (_matrix[vi][i] != MAX_W && visited[i] == false)
						{
							que.push(i);
							visited[i] = true;
						}
					}
				}
				cout << endl;
				levelsize = que.size();
			}
			
			//检查是否访问完了所有的顶点
			for (size_t i = 0; i < visited.size(); i++)
			{
				if (visited[i] == false)
					BFS(_vertex[i]);
			}
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    这里我们是将顶点入栈的时候就标记为true，不是在访问的时候标记，因为访问的时候标记会有问题，比如此时队列内仍有顶点，访问完当前顶点，将当前顶点邻接顶点放入对列的时候，可能遇到邻接顶点已经在对列内了，但是还没访问所以没有标记，就将重复的顶点入了对列，就会造成重复访问了某个顶点。

    最小生成树

    通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不在连通；反之，在其中引入任何一条新边，都会形成一条回路。若连通图由n个顶点组成，则其生成树必含n个顶点和n-1条边。
    通过不同的遍历算法可以得到不同的生成树，从不同的顶点出发得到的生成树也是有所不同的，最小生成树就是针对于带权图里面的所有生成树中，权值之和最小的哪一棵树。同时最小生成树并不唯一。

    构造最小生成树有三条规则：

    1. 只能使用图中的边来构造最小生成树
    2. 只能使用恰好n-1条边来连接图中的n个顶点
    3. 选用的n-1条边不能构成回路

    构造最小生成树这里介绍两种算法：Kruskal算法和Prim算法。他们都是使用的贪心思想。
    贪心算法的思想就是，对于每次求解都是选取当前最优解，最后求出全局最优解。但是贪心算法并不一定对于所有的情况都有用，有时候贪心会失效。

    Kruskal算法(全局贪心)

    在一个带权图中，前人证明，权值最小的那条边必然会出现在至少一颗最小生成树中，权值第二小的那条边也会至少被一颗最小生成树采用，但是从第三条开始就不一定了。

    kruskal算法的思想就是：首先构造一个n个顶点不含任何边的图，每个顶点自成一个连通分量，然后不断选边，选的边的权值都是最小的，然后判断加入这条边后，最小生成树有没有构成回路，有则放弃这条边继续选最小的。直到所有顶点都在同一个连通分量（最大连通子图）上。

    这里将所有的边排序我们可以使用优先级队列（堆），判环的操作可以使用并查集，如果某条边的起点和终点在同一个集合内，那么插入这条边就会构成环。

    这是Kruskal选边的流程
    在这里插入图片描述

    		//克鲁斯卡尔算法（整体贪心）
		W Kruskal(Self& mintree)
		{
			//最小生成树初始化
			mintree._vertex = _vertex;
			mintree._indexMap = _indexMap;
			mintree._matrix.resize(_vertex.size());
			for (size_t i = 0; i < _vertex.size(); i++)
			{
				mintree._matrix[i].resize(_vertex.size(), MAX_W);
			}
			//初始化优先级队列
			priority_queue<Edge, vector<Edge>, greater<Edge>> pq;		//使用优先级队列对边的权值进行排序，
																		//这里可以使用库仿函数然后重载operator>
																		//也可直接自己写一个仿函数专门比较边的权值
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				for (size_t j = 0; j < _matrix.size(); j++)
				{
					//无向图是对称矩阵，只需要上三角即可
					if (i <= j && _matrix[i][j] != MAX_W)
					{
						pq.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}
			//需要一个并查集来判环
			UnionFindSet ufs(_vertex.size());

			int n = _vertex.size();
			int count = 0;		//记录最小生成树中边的数量
			W total = W();		//最小生成树的权值和
			while (count < n - 1 && !pq.empty())
			{
				Edge min = pq.top();		//每次取最小的权值的边
				pq.pop();
				if (!ufs.InSet(min._srci, min._desti))		//判断是不是构成了环
				{
					ufs.Union(min._srci, min._desti);
					mintree._AddEdge(min._srci, min._desti, min._w);
					total += min._w;
					count++;
				}
			}
			if (count == n - 1)
			{
				return total;
			}
			else
			{
				return W();
			}
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    Kruskal使用的思想是整体贪心，将边按照权值排序，然后依次拿最小的边插入到最小生成树中。

    关于时间复杂度的计算，分为邻接矩阵和邻接表
    邻接矩阵：构建最小堆的时候要遍历整个矩阵，时间复杂度是O(N2)，如果从空堆开始插入e条边，时间复杂度是O(eloge)，在构造最小生成树的过程中会进行e此出堆操作，时间复杂度是O(eloge)，并查集会进行2e此find，时间复杂度是O(elogn)，以及会进行n-1此合并集合的操作时间复杂度是O(n)。最后总的时间复杂度就是O(n2 + eloge + elogn + n)所以计算完后就是O(n^2 + eloge);
    邻接表：邻接表与邻接矩阵的唯一区别就是在遍历所有的边的时间复杂度是O(n + e)，查询某个顶点所连接的边的时间复杂度是O(e)。因此邻接表的时间复杂度就是O(n + e + eloge + elogn + n)最后简化后就是O(n + eloge)

    Prim算法(局部贪心)

    Prim算法的主要思想是将图的顶点分成两个结合，假设一个X集合和一个Y集合，X集合里面保存的是当前生成树所选中的顶点，Y集合保存的是未被选中的顶点。其实时X里面只有一个起点，X集合和Y集合至少存在一条边连接，这连接X集合和Y集合的边就叫做桥，我们每次选权值最小的那一条桥，然后将桥的终点(在Y集合的顶点)添加到X集合，将桥添加到最小生成树的边中，直到最后，X集合有n个顶点，最小生成树边有n-1条即可。

    这是Prim选边的过程
    在这里插入图片描述

    		//普利姆算法(局部贪心) src是给定的起点
		W Prim(Self& mintree, const V& src)
		{
			size_t srci = FindVertexIndex(src);
			//最小生成树初始化
			mintree._vertex = _vertex;
			mintree._indexMap = _indexMap;
			mintree._matrix.resize(_vertex.size());
			for (size_t i = 0; i < _vertex.size(); i++)
			{
				mintree._matrix[i].resize(_vertex.size(), MAX_W);
			}
			//初始化两个集合
			int n = _vertex.size();
			vector<bool> X(n, false);
			vector<bool> Y(n, true);
			X[srci] = true;			//X保存已经选了的顶点
			Y[srci] = false;		//Y保存没有选的顶点
			//优先级队列保存起点连接出去的所有边（并且进行排序）
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
			for (int i = 0; i < n; i++)
			{
				if (_matrix[srci][i] != MAX_W)
				{
					minq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}
			
			int count = 0;
			W total = W();
			//进行选边操作
			while (count < n - 1 && !minq.empty())
			{
				Edge min = minq.top();
				minq.pop();
				//min.srci一定在X集合，所以desti要在Y集合才能不构成环
				if (Y[min._desti] == true)
				{
					X[min._desti] = true;
					Y[min._desti] = false;
					mintree._AddEdge(min._srci, min._desti, min._w);
					cout << "choice this is :" << _vertex[min._srci] << " -> " << _vertex[min._desti] << endl;
					count++;
					total += min._w;
					for (int i = 0; i < n; i++)
					{
						//将新进入X集合点的和Y集合有连接的边插入队列
						if (_matrix[min._desti][i] != MAX_W && Y[i] == true)
						{
							minq.push(Edge(min._desti, i, _matrix[min._desti][i]));
						}
					}
				}
				else
				{
					//这些边的目的地节点已经出现在X集合不可选了，否则构成环
					cout << "Ban choice this :" << _vertex[min._srci ]<< " -> " << _vertex[min._desti ]<< endl;
				}
			}
			if (count == n - 1)
				return total;
			else
				return W();
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64

    Prim算法的迭代次数是n-1次选出了n-1个顶点，时间复杂度是O（n），每次迭代平均将2e/n条边插入最小堆（出现2e因为是无向图，可能会遇到从i到j和从j到i），总计e条边边从最小堆中删除，堆的插入和删除时间复杂度都是O（loge）所以总的时间复杂度就是O（n + eloge）

    最短路径

    关于最短路，我们先看一个实际场景，比如：交通运输线路是一个带权图，现在我们要从A市到其他市要求出所有最短的路径。
    所谓的最短路径问题就是指：从带权图中的某个顶点出发到达另一终点的的最短路径，最短就是指，这条路径上的权值之和市最小的。
    最短路径问题主要是针对有向图的
    最短路径有三种算法：

    1. 非负权值的单源最短路径算法（Dijkstra）
    2. 任意权值的单源最短路径算法（Bellman-Ford）
    3. 任意权值的多源最短路径算法（Floyd）

    Dijkstra算法

    算法思想是贪心思想。
    首先设集合S存放的是已经确定最短路径的顶点，初始状态的时候S中没有点，用辅助数组dist记录从起点到其他点的路径权值和，一开始为MAX_W，pPath数组记录每个点的路径的父节点。
    然后进行n次循环，每次循环都是取dist数组中，不在S集合内的，权值和最小的点。将该点添加进S集合确定其最小路径。然后用该点连接出去的边，去松弛更新其他不在S集合内的顶点的权值，更新的时候不仅要更新dist里面的权值，还要更新pPath里面顶点的父节点。

    下面是Dijkstra算法更新的过程
    在这里插入图片描述

    		//单源最短路径（无负权值）贪心思想
		void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			size_t srci = FindVertexIndex(src);
			int n = _vertex.size();
			//dist记录节点的路径权值（从起点srci到其他顶点）
			dist.resize(n, INT_MAX);
			dist[srci] = 0;
			//pPath记录顶点路径的父节点的下标
			pPath.resize(n, -1);
			//pPath[srci] = 0;

			//S记录已经确定最短路径的顶点
			vector<bool> S(n, false);


			for (int i = 0; i < n; i++)
			{
				int min = INT_MAX;
				int index = 0;
				//选出路径权值最小的顶点且未在集合S内，并找到其下标
				for (int j = 0; j < n; j++)
				{
					if (S[j] == false && dist[j] < min)
					{
						index = j;
						min = dist[j];
					}
				}
				//选出当前最小顶点将其放进S集合，然后进行松弛更新
				S[index] = true;
				//遍历该选出的顶点的所有连接出去的边，若连接的顶点没有在S集合中且该顶点的值可以松弛更新
				for (int p = 0; p < n; p++)
				{
					if (S[p] == false && _matrix[index][p] != INT_MAX && dist[index] + _matrix[index][p] < dist[p])
					{
						dist[p] = dist[index] + _matrix[index][p];
						pPath[p] = index;
					}
				}
			}
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    Dijkstra算法的时间复杂度计算：首先要选出n个顶点，外循环n次，内循环是进行选顶点和松弛更新，时间都是n，所以总的时间复杂度是O（n^2)。
    注意：Dijkstra算法图中不能有负权值顶点否则贪心失效，因为如果有负权值可能会导致本来权值大的点，因为其连接出去的边是负权值，导致其是一个更优的顶点，此时贪心就失效了。

    Bellman-Ford算法

    Bellman-Ford算法实际是一种暴力算法。
    算法思想：每次都是遍历整个邻接矩阵，更新各个顶点的dist数组里面的权值，因为可能会出现更新了某个顶点的权值之后，该顶点连接的其他顶点也会受到影响，所以不能只能更新一次。
    最外层其实只需要更新n-2次即可，因为，每个顶点的路径可能经过的顶点最少是直接从起点连接到终点，经过零个顶点，最多就是经过了其他所有的顶点，n-2个，所以每次更新导致的某个顶点发生变化影响了其他顶点，这些顶点数最多就是n-2个，所以需要安排n-2次以上的最外层循环接近该问题。

    要注意，如果图中存在负权值回路，那么什么算法也是没有用的。
    下面是BellmanFord算法的执行流程。
    在这里插入图片描述

    		//单源最短路径（支持负权值）（暴力算法）
		bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			size_t srci = FindVertexIndex(src);
			int n = _vertex.size();
			dist.resize(n, MAX_W);
			pPath.resize(n, -1);
			
			dist[srci] = W();
			for (int k = 2; k < n; k++)
			{
				bool swap_flag = false;
				for (int i = 0; i < n; i++)
				{
					for (int j = 0; j < n; j++)
					{
                        //这里的long long是为了防止int溢出导致起点不是第一个，出现溢出错误的问题。
						if (_matrix[i][j] != MAX_W &&
							(long long)dist[i] + _matrix[i][j] < dist[j])
						{
							swap_flag = true;
							dist[j] = dist[i] + _matrix[i][j];
							pPath[j] = i;
						}
					}
				}
				if (swap_flag == false)
					break;
			}

			//再次尝试更新
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (_matrix[i][j] != MAX_W && (long long)dist[i] + _matrix[i][j] < dist[j])
					{
						cout << "出现负权值回路" << endl;
						return false;
					}
				}
			}
			return true;
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    BellmanFoyd算法的时间复杂度计算，针对邻接矩阵总共有三层for循环，内层的if语句执行了n3次所以时间复杂度是O(n3)，如果是邻接表，那么最内层的两for循环可以改成while，循环的总次数就是n2*e，时间复杂度还是接近于O(n3)

    Floyd算法

    Floyd是用来求所有顶点的最短路径的算法，支持负权值的图，如果没有负权值的图，我们可以使用n次循环Dijkstra算法也是可以完成求所有顶点的最短路径的算法的。
    算法思想：整体是一种动态规划思想，初始化时dist[i][j]的值就是i顶点到j顶点的权值，若从i到j不存在边那么就用MAX_W进行初始化，特别注意i == j的位置要初始化权值为0，防止在后序的循环中更新了自己跟自己之间的权值，vvPath初始化如果从i到j没有边那么就是-1，有那么i就是父节点。
    直接在dist数组上进行动态规划修改权值，循环从i到j顶点的权值，在他们的中间不断插入顶点k，如果插入k之后，路径的权值之和要小于直接从i到j，那么此时就找到了更优的路径，就需要更新dist[i][j]的权值同时更新vvPath[i][j]的父节点。因为起点i和终点j是变化的，所以中间顶点k可能是n个顶点中的任意一个，所以必须从0到n循环一次。

    		//多源最短路径算法（如果没有负权值，其实可以通过循环n次每个顶点都进行Dijkstra算法）
		void FloyedWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvPath)
		{
			int n = _vertex.size();
			vvDist.resize(n);
			vvPath.resize(n);
			for (int i = 0; i < n; i++)
			{
				vvDist[i].resize(n, MAX_W);
				vvPath[i].resize(n, -1);
			}
			//将原来的邻接矩阵拷贝到dist，同时更新路径，方便后面直接在此调整，动态规划思想
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (_matrix[i][j] != MAX_W)
					{
						vvDist[i][j] = _matrix[i][j];
						vvPath[i][j] = i;			//记录路径i-->j的起点就是i
					}
					else
					{
						vvPath[i][j] = -1;			//不连通的两个顶点记录成-1
					}
					if (i == j)
					{
						vvPath[i][j] = -1;
						vvDist[i][j] = W();//i和j相等的时候就是一个顶点，自己到自己的权值就是0，如果不初始化的话就是INT_MAX
										   //那么后续可能会被更新成其他值，就会出错了。
										   //初始化成0，那么就永远不会被更新，除非从i到k和从k到j的权值之和是负值，此时就是构
									       //成了负权值回路了。
					}
				}
			}

			//用一个中间顶点来调整，i --> k --> j,
			//原理就是暴力的用每个顶点作为k中间顶点，尝试是不是经过k顶点的路径要比直接从i到j权值要小
			for (int k = 0; k < n; k++)
			{
				for (int i = 0; i < n; i++)
				{
					for (int j = 0; j < n; j++)
					{
						if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W &&
							vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
						{
							vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
							vvPath[i][j] = vvPath[k][j];
						}
					}
				}
			}
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    Floyd算法的时间复杂度的计算明显就是三层循环，一个O(n^3)的算法。
    同样的Floyd算法允许存在负权值的边，但是不允许存在负权值回路，负权值回路本博客提到的所有算法都是无法解决的。

  • 相关阅读:
    四大竞争对手敦促欧盟反垄断行动：阻止谷歌成为默认搜索引擎
    1206、数据备份与恢复、binlog日志、使用binlog日志恢复数据、innobackupex
    洛谷刷题C语言：切蛋糕、概率、Bridž、NOTE、DOMINO
    JavaScript到底应不应该加分号？JavaScript自动插入分号规则详解
    电容笔有什么用？电容笔十大品牌排行
    C++指针笔记
    在Ubuntu 20.04搭建最小实验环境
    【JUC系列】Fork/Join框架之概览
    【React】unmountComponentAtNode卸载组件
    MySQL字符串拼接函数
  • 原文地址：https://blog.csdn.net/qq_62745420/article/details/127568856