当前位置:   article > 正文

【数据结构】图

【数据结构】图

图的存储方式

邻接矩阵

优点

1.适合存稠密图
2.邻接矩阵判断两个顶点的连接关系,并取到权值时间复杂度为o(1)

缺点

1.如果顶点比较多,边比较少时,矩阵中存储了大量的0成为系数矩阵,比较浪费空间。
2.并且要求两个节点之间的路径不是很好求。

实现

namespace matrix
{
	template<class V, class W,W MAX_W=INT_MAX, bool Direction=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]);
				_indexMap[a[i]] = i;
			}
			_matrix.resize(n);
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				_matrix[i].resize(n, MAX_W);
			}
		}

		size_t GetVertexIndex(const V& v)
		{
			auto it = _indexMap.find(v);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				throw invalid_argument("顶点不存在");
				return -1;
			}
		}

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

			_matrix[srci][desti] = w;
			if (Direction == false)
			{
				_matrix[desti][srci] = w;
			}
		}

		void Print()
		{
			//顶点
			int n = _vertexs.size();
			for (size_t i = 0; i < n; i++)
			{
				cout << i << "->" << _vertexs[i] << endl;
			}
			cout << endl;

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

		//void BFS(const V& src)
		//{
		//	size_t srci = GetVertexIndex(src);
		//	int n = _matrix.size();
		//	queue<int> q;
		//	q.push(srci);
		//	vector<bool> vis(_vertexs.size(),false);
		//	vis[srci] = true;

		//	while (!q.empty())
		//	{
		//		int front = q.front();
		//		q.pop();
		//		cout << front << "->" << _vertexs[front] << " ";

		//		//邻接顶点入队列
		//		for (size_t i = 0; i < n; i++)
		//		{
		//			if (_matrix[front][i] != MAX_W&&!vis[i])
		//			{
		//				q.push(i);
		//				vis[i] = true;
		//			}
		//		}
		//	}
		//}
		

		void BFS2(const V& src)
		{
			size_t srci = GetVertexIndex(src);
			int n = _matrix.size();
			queue<int> q;
			q.push(srci);
			vector<bool> vis(_vertexs.size(), false);
			vis[srci] = true;

			int count = 0;
			while (!q.empty())
			{
				int m = q.size();
				for (size_t i = 0; i <m; i++)
				{
					int front = q.front();
					q.pop();
					
					cout << count << "层朋友:" << _vertexs[front] << " ";

					//邻接顶点入队列
					for (size_t i = 0; i < n; i++)
					{
						if (_matrix[front][i] != MAX_W && !vis[i])
						{
							q.push(i);
							vis[i] = true;
						}
					}
				}
				count++;
				cout << endl;
			}
		}

		void _DFS(size_t srci, vector<bool>& vis)
		{
			cout << srci << ":" << _vertexs[srci] << endl;
			vis[srci] = true;

			//找一个srci没有访问过的点,去深度遍历
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				if (_matrix[srci][i] != MAX_W && vis[i] == false)
				{
					_DFS(i, vis);
				}
			}
		}


		void DFS(const V& src)
		{
			size_t srci = GetVertexIndex(src);
			vector<bool> vis(_vertexs.size(), false);

			_DFS(srci, vis);

			//如果不连通,还有检查vis哪里有false,循环遍历一遍
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				if (!vis[i])
					_DFS(i,vis);
			}
		}



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

	void Test_Graph1()
	{
		Graph<char, int, INT_MAX, 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();

		g.BFS2('0');
	}

	void Test_Graph2()
	{
		string a[] = { "张三", "李四", "王五", "赵六","周七","勾八"};
		Graph<string, int> g1(a, 6);
		g1.AddEdge("张三", "李四", 100);
		g1.AddEdge("张三", "王五", 200);
		g1.AddEdge("王五", "赵六", 30);
		g1.AddEdge("王五", "李四", 80);
		g1.AddEdge("李四", "勾八", 50);

		//g1.BFS2("张三");
		g1.DFS("王五");
	}

}


  • 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
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221

邻接表

用vector保存所有顶点,使用链表挂在每一个顶点下面,形成一个类似哈希桶的结构。

优点

1.适合存稀疏图
2.适合查找一个顶点连接出去的边

缺点

不适合确定两个顶点是否相连及权值

实现

namespace link_table
{
	template<class W>
	struct Edge
	{
		int _dsti;
		//int _srci;
		W _w;
		Edge<W>* _next=nullptr;

		Edge(const int dsti,const W& w)
			:_dsti(dsti)
			,_w(w)
			,_next(nullptr)
		{}
	};

	template<class V,class W,bool Direction=false>
	class Graph
	{
		typedef Edge<W> Edge;
	public:
		Graph(const V* a, size_t n)
		{
			_vertexs.reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				_vertexs.push_back(a[i]);
				_indexMap[a[i]] = i;
			}

			_tables.resize(n,nullptr);
		}

		size_t GetVertexIndex(const V& v)
		{
			auto it = _indexMap.find(v);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				throw invalid_argument("顶点不存在");
				return -1;
			}
		}

		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);

			Edge* eg=new Edge(dsti,w) ;//构造一条边
			eg->_next = _tables[srci];
			_tables[srci] = eg;

			if (Direction == false)
			{
				Edge* eg = new Edge(srci, w);
				eg->_next = _tables[dsti];
				_tables[dsti] = eg;
			}
		}


		void Print()const
		{
			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* cur = _tables[i];
				while (cur)
				{
					cout << _vertexs[cur->_dsti] << "[" << cur->_dsti << "]"<<cur->_w<<"->";
					cur = cur->_next;
				}
				cout << " nullptr" << endl;
			}
		}



	private:
		vector<V> _vertexs;//顶点集合
		map<V, int> _indexMap;//点和下标映射关系
		vector<Edge*> _tables;//边的集合
	};

	void test_link_tables()
	{
		string a[] = { "张三", "李四", "王五", "赵六"};
		Graph<string, int> g1(a, 4);
		g1.AddEdge("张三", "李四", 100);
		g1.AddEdge("张三", "王五", 200);
		g1.AddEdge("王五", "赵六", 30);

		g1.Print();
	}
}
  • 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

基本概念

完全图:在有n个顶点的无向图中,若有n *(n-1)/2条边,即任意两个顶点之间有且仅有一条边,则称此图为无向完全图,比如上图G1;在n个顶点的有向图中,若有n *(n-1)条边,即任意两个顶点之间有且仅有方向相反的边,则称此图为有向完全图。

顶点的度:顶点v的度是指与它相关联的边的条数,记作deg(v)。在有向图中,顶点的度等于该顶点的入度与出度之和,其中顶点v的入度是以v为终点的有向边的条数,记作indev(v);顶点v的出度是以v为起始点的有向边的条数,记作outdev(v)。因此:dev(v) = indev(v) + outdev(v)。注意:对于无向图,顶点的度等于该顶点的入度和出度,即dev(v) = indev(v) = outdev(v)

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

生成树:一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边

最小生成树

连通图中的每一棵生成树,都是原图的一个极大无环子图,即:从其中删去任何一条边,生成树就不在连通;反之,在其中引入任何一条新边,都会形成一条回路。
若连通图由n个顶点组成,则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条:

  1. 只能使用图中的边来构造最小生成树
  2. 只能使用恰好n-1条边来连接图中的n个顶点
  3. 选用的n-1条边不能构成回路
    构造最小生成树的方法:Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。
    贪心算法:是指在问题求解时,总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的的选择,而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。

Kruskal算法

简单来说,该算法是在全局的边中采用贪心算法,先构建一个无边的顶点集合,然后从权值最小的边开始,一条一条选,若两个顶点来自不同的连通分量,则加入到顶点集合中,(使用并查集来保证两个顶点来自不同的连通分量)。
在这里插入图片描述

代码实现

struct Edge
		{
			size_t _srci;
			size_t _dsti;
			W _w;

			Edge(size_t srci, size_t dsti, const W& w)
				:_srci(srci)
				, _dsti(dsti)
				, _w(w)
			{}

			bool operator>(Edge e2)const
			{
				return _w > e2._w;
			}
		};

		W Kruskal(Self& minTree)
		{
			//初始化minTree
			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(_vertexs.size());
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				minTree._matrix[i].resize(_vertexs.size(), MAX_W);
			}


			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
			int n = _matrix.size();

			for (size_t i = 0; i < n; i++)
			{
				for (size_t j = 0; j < n; j++)
				{
					if (i < j && _matrix[i][j] != MAX_W)
					{
						minq.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}

			//选出n-1条边
			UnionFindSet ufs(n);
			W totalW = W();
			int size = 0;
			while (!minq.empty())
			{
				Edge min = minq.top();
				minq.pop();

				if (!ufs.IsInSet(min._srci, min._dsti))
				{
					cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] <<
						":" << _matrix[min._srci][min._dsti] << endl;
					minTree._AddEdge(min._srci, min._dsti, min._w);
					ufs.Union(min._srci, min._dsti);
					totalW += min._w;
					size++;
				}
			}

			if (size == n - 1)
			{
				return totalW;
			}
			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
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73

这里首先创建一个Edge结构体用来存起始顶点和权值,采用优先级队列辅助每次取出最小的元素(用一个仿函数控制为权值比较的小堆),然后进行n-1次循环,每次把选取的Edge的顶点下标放进并查集中,最终若为最小生成树则返回权值和

Prim算法

从任意一个根节点开始,从这个起点出发选择一条轻量级的边,然后把这两个点归到集合A中,剩下的点在集合B中,再从集合B中选择一条小边再加入到集合A,循环往复,直到选出n-1条不成环的边。

代码实现

W Prim(Self& minTree, const V& src)
		{
			size_t srci = GetVertexIndex(src);
			//初始化minTree
			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			int n = _vertexs.size();
			minTree._matrix.resize(_vertexs.size());
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				minTree._matrix[i].resize(_vertexs.size(), MAX_W);
			}

			unordered_set<int> X;
			unordered_set<int> Y;

			X.insert(srci);
			for (size_t i = 0; i < n; i++)
			{
				if (i != srci)
				{
					Y.insert(i);
				}
			}

			//从X到Y集合中连最小边
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
			for (size_t i = 0; i < n; i++)
			{
				if (_matrix[srci][i] != MAX_W)
				{
					minq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}

			size_t size = 0;
			W totalW = W();
			while (!minq.empty())
			{
				Edge min = minq.top();
				minq.pop();

				if (X.count(min._dsti))
				{
					cout << "构成环" << _vertexs[min._srci] << ":" << _vertexs[min._dsti] << endl;
					continue;
				}

				minTree._AddEdge(min._srci, min._dsti,min._w);
				X.insert(min._dsti);
				Y.erase(min._dsti);
				totalW += min._w;
				size++;
				if (size == n - 1)
					break;

				for (size_t i = 0; i < n; i++)
				{
					if (_matrix[min._dsti][i] != MAX_W&&X.count(i)==0)
					{
						minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
					}
				}
			}

			if (size == n - 1)
				return totalW;
			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
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/451534
推荐阅读
相关标签
  

闽ICP备14008679号