• 【高阶数据结构】并查集和图

    目录

    1.数据结构--并查集

    2.数据结构--图

    1.图的基础概念

    2.图的简单实现

    2.1.邻接矩阵的图实现

    2.2.邻接表的图实现

    2.3.图的DFS和BFS

    2.4.最小生成树

    2.4.1.Kruskal(克鲁斯卡尔算法)

    2.4.2.Prim（普里姆算法）

    2.5.最短路径

    2.5.1.Dijkstra(迪杰斯特拉算法)

    2.5.2.Bellman-Ford（贝尔曼-福特算法）

    2.5.3.Floyd-Warshall（弗洛伊德算法）

    1.数据结构--并查集

    概念：将n个不同的元素划分成一些不相交的集合。

    1. 开始时，每个元素自成一个单元素集合；初始化
    2. 然后按一定的规律将归于同一组元素的集合合并；合并
    3. 在此过程中要反复用到查询某一个元素归属于那个集合的运算：查询                           适合于描述这类问题的抽象数据类型称为并查集(union-find set)

    概念图：

    实现：Count：遍历数组元素有多少个负数，就有几个集合

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6.  
    7. template<class T>
    8. class UnionFindSet {
    9. public:
    10. 	int Find(T val)
    11. 	{
    12. 		int index = _find_index[val];
    13. 		while (_v[index] >= 0)
    14. 			index = _v[index];
    15. 		return index;
    16. 	}
    17. 	bool Union(T x, T y)
    18. 	{
    19. 		int xi = Find(x);
    20. 		int yi = Find(y);
    21. 		//是否已经联合了
    22. 		if (xi == yi)
    23. 			return false;
    24. 		_v[xi] += _v[yi];
    25. 		_v[yi] = xi;
    26. 		return true;
    27. 	}
    28. 	//有多少个集合
    29. 	int Count()
    30. 	{
    31. 		int count = 0;
    32. 		for (auto e : _v)
    33. 		{
    34. 			if (e < 0)
    35. 				count++;
    36. 		}
    37. 		return count;
    38. 	}
    39. public:
    40. 	UnionFindSet(const vector& tmp)
    41. 	{
    42. 		for (int i = 0; i < tmp.size(); i++)
    43. 			_find_index[tmp[i]] = i;
    44. 		_v.resize(tmp.size(), -1);
    45. 	}
    46. 	~UnionFindSet()
    47. 	{}
    48. private:
    49. 	//
    50. 	vector _v;
    51. 	//哈希数组的数据和下标
    52. 	unordered_mapint> _find_index;
    53. };

     测试：

    1. #include
    2. #include"UnionFindSet.h"
    3. #include
    4.  
    5. using namespace std;
    6.  
    7. int main()
    8. {
    9. 	vector<int> v{ 1,23,432,5345,8,712,44,534,645,73,862,3 };
    10. 	UnionFindSet<int> ufs(v);
    11.  
    12. 	ufs.Union(1, 534);
    13. 	ufs.Union(1, 534);
    14. 	ufs.Union(73, 534);
    15. 	ufs.Union(1, 4);
    16. 	ufs.Union(23, 8);
    17. 	ufs.Union(862, 73);
    18. 	ufs.Union(3,3);
    19. 	cout << ufs.Count() << endl;
    20. 	return 0;
    21. }

    可以试试这个题：使用并查集做 

    Leetcode：省份数量

    1. class UnionFindSet{
    2.     public:
    3.     int Find(int x)
    4.     {
    5.         //找到下标
    6.         int index = _find_index[x];
    7.         while(_v[index] >= 0)
    8.         {
    9.             index = _v[index]  ;
    10.         }
    11.         return index;
    12.     }
    13.  
    14.     bool Union(int x, int y)
    15.     {
    16.         int xi = Find(x);
    17.         int yi = Find(y);
    18.         //已经联合
    19.         if(xi == yi)
    20.             return false;
    21.         _v[xi] += _v[yi];
    22.         _v[yi] = xi;
    23.         return true;
    24.     }
    25.     int Count()
    26.     {
    27.         int count = 0;
    28.         for(auto e : _v)
    29.         {
    30.             if(e < 0)
    31.                 count++;
    32.         }
    33.         return count;
    34.     }
    35.     public:
    36.     UnionFindSet(const vector<int>& v)
    37.     {
    38.         _v.resize(v.size(), -1);
    39.         for(int i = 0; isize();i++)
    40.             _find_index[i] = i;
    41.     }
    42.     private:
    43.     vector<int> _v;
    44.     unordered_map<int, int> _find_index;
    45. };
    46.  
    47. class Solution {
    48. public:
    49.     int findCircleNum(vectorint>>& isConnected) {
    50.         int n = isConnected.size();
    51.         vector<int> v;
    52.         for(int i =0; i
    53.         {
    54.             v.push_back(i);
    55.         }
    56.         UnionFindSet ufs(v);
    57.         for(int i = 0; i
    58.         {
    59.             for(int j=0; j
    60.             {
    61.                 if(isConnected[i][j] == 1)
    62.                 {
    63.                     ufs.Union(i,j);
    64.                 }
    65.             }
    66.         }
    67.         return ufs.Count();
    68.     }
    69. };

    2.数据结构--图

    1.图的基础概念

    图(graph)：由顶点(vertex)集合和顶点之间的关系(edge)构成，即G = （V, E）; 

    1. 顶点：图内的任意顶点；
    2. 边：连接两个顶点；
    3. 边的权值：连接两个顶点的边的值；

    无向图和有向图

    1. 无向图：两个顶点之间的边无方向，两个边的权值用一个数值表示 ; 所以为强关系图：例如：qq和微信的互相为好友关系
    2. 有向图：两个顶点之间的边有方向，代表的是一个顶点到另一个顶点的权值  ; 所以为弱关系图：例如  抖音关注主播，主播不会同时关注你

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

     顶点的度：顶点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，v3，…，vm均不重复（不构成回路的路径），则称这样的路径为简单路径。若路径上第一个顶点v1和最后一个顶点vm重合，则称这样的路径为回路或环。 

    生成树：一个连通图的最小连通子图（整个图连通 ，任一顶点都可以找到另一顶点）称作该图的生成树。有n个顶点的连通图的生成树有n个顶点 和n-1条边。 

    2.图的简单实现

    2.1.邻接矩阵的图实现

    优势：使用邻接矩阵可以快速查找（时间复杂度O(1)）两个顶点是否有边且边的权值；劣势：查找顶点的度时（时间复杂度为O（N））;

    设计理念：有n个顶点，创建一个n*n的二维矩阵来放置两个顶点边的权值，为空可以使用一个权值的最大值或者最小值；

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include"UnionFindSet.h"
    9.  
    10. using namespace std;
    11.  
    12. //V顶点类型，W权值类型
    13. namespace Matrix {
    14. 	template<class V, class W, bool Direction = false, W W_MAX = INT_MAX>
    15. 	class Graph {
    16. 	public:
    17. 		typedef Graph Self;
    18. 		int Find(const V& v)
    19. 		{
    20. 			auto it = _find_index.find(v);
    21. 			if (it == _find_index.end())
    22. 				return -1;
    23. 			return it->second;
    24. 		}
    25. 		bool AddEdge(const V& src, const V& des, const W& weight)
    26. 		{
    27. 			int si = Find(src);
    28. 			int di = Find(des);
    29. 			//错误顶点
    30. 			if (si == -1 || di == -1)
    31. 				return false;
    32. 			_matrix[si][di] = weight;
    33. 			if (Direction == false)
    34. 				_matrix[di][si] = weight;
    35. 			return true;
    36. 		}
    37. 		void Print()
    38. 		{
    39. 			for (int i = 0; i < _matrix.size(); i++)
    40. 			{
    41. 				for (int j = 0; j < _matrix.size(); j++)
    42. 				{
    43. 					if (_matrix[i][j] == W_MAX)
    44. 						printf("%5c", '*');
    45. 					else
    46. 						printf("%5d", _matrix[i][j]);
    47. 				}
    48. 				cout << endl;
    49. 			}
    50. 		}
    51. 	public:
    52. 		Graph(const vector& v)
    53. 		{
    54. 			int n = v.size();
    55. 			_vertexs.resize(n);
    56. 			//初始化顶点集合和  顶点和下标的映射
    57. 			for (int i = 0; i < n; i++)
    58. 			{
    59. 				_vertexs[i] = v[i];
    60. 				_find_index[v[i]] = i;
    61. 			}
    62. 			//初始邻接矩阵
    63. 			_matrix.resize(n, vector(n, W_MAX));
    64. 		}
    65. 		Graph() = default;
    66. 		~Graph()
    67. 		{}
    68. 	private:
    69. 		//顶点集合
    70. 		vector _vertexs;
    71. 		//查找顶点下标
    72. 		unordered_mapint> _find_index;
    73. 		vector> _matrix;
    74.  
    75. 	};
    76. }
    77. void test()
    78. {
    79.     vector a{ "张三", "李四", "王五", "赵六", "周七" };
    80.     Matrix::Graphint, false> g1(a);
    81.     g1.AddEdge("张三", "李四", 100);
    82.     g1.AddEdge("张三", "王五", 200);
    83.     g1.AddEdge("王五", "赵六", 30);
    84.     g1.AddEdge("王五", "周七", 30);
    85.     g1.Print();
    86.  
    87.     g1.Print();
    88. }
    89. int main()
    90. {
    91.     test();
    92.     return 0 ;
    93. }

    2.2.邻接表的图实现

    优势：查找顶点的度时（时间复杂度为O（1），添加一个计数），更节省空间;劣势：使用邻接表查找两个顶点是否有边且边的权值（最差情况：时间复杂度O(N)），插入效率低：需要遍历链表，看是否已存在

    设计理念：有n个顶点，创建有n个元素的指针矩阵，插入一个新边 遍历链表看是否存在；

    1. namespace List {
    2. 	template<class W>
    3. 	class Node {
    4. 	public:
    5. 		int _des;
    6. 		//权值
    7. 		W _weight;
    8. 		Node* _next;
    9. 		Node(int des, W w):_des(des),_weight(w),_next(nullptr)
    10. 		{}
    11. 	};
    12. 	template<class V, class W, bool Direction = false>
    13. 	class Graph{
    14. 	public:
    15. 		int Find(const V& v)
    16. 		{
    17. 			auto it = _find_index.find(v);
    18. 			if (it == _find_index.end())
    19. 				return -1;
    20. 			return it->second;
    21. 		}
    22. 		bool AddEdge(const V& src, const V& des, const W& weight)
    23. 		{
    24. 			//获取下标
    25. 			int si = Find(src);
    26. 			int di = Find(des);
    27. 			//不存在元素，fail；
    28. 			if (si == -1 || di == -1)
    29. 				return false;
    30. 			//邻接表添加边
    31. 			//数组指针是否为nullptr
    32. 			if (_table[si] == nullptr){
    33. 				//创建对象
    34. 				Node* new_node = new Node(di, weight);
    35. 				new_node->_next = _table[si];
    36. 				_table[si] = new_node;
    37. 				//无向图
    38. 				if (Direction == false) {
    39. 					Node* new_node = new Node(si, weight);
    40. 					new_node->_next = _table[di];
    41. 					_table[di] = new_node;
    42. 				}
    43.  
    44. 			}
    45. 			else {//需要和邻接表内元素比较，是否已添加
    46. 				Node* nd = _table[si];
    47. 				while (nd)
    48. 				{
    49. 					if (nd->_des == di)
    50. 						return false;
    51. 					else
    52. 						nd = nd->_next;
    53. 				}
    54. 				//还未添加过
    55. 				Node* new_node = new Node(di, weight);
    56. 				new_node->_next = _table[si];
    57. 				_table[si] = new_node;
    58. 				//无向图
    59. 				if (Direction == false) {
    60. 					Node* new_node = new Node(si, weight);
    61. 					new_node->_next = _table[di];
    62. 					_table[di] = new_node;
    63. 				}
    64. 			}
    65. 			return true;
    66.  
    67. 		}
    68. 		void Print()
    69. 		{
    70. 			for (int i = 0; i < _table.size(); i++)
    71. 			{
    72. 				cout << _vertexs[i] << ": ";
    73. 				Node* nd = _table[i];
    74. 				while (nd)
    75. 				{
    76. 					cout << _vertexs[nd->_des] << " " << nd->_weight << "   ";
    77. 					nd = nd->_next;
    78. 				}
    79. 				cout << endl;
    80. 			}
    81. 		}
    82. 	public:
    83. 		Graph(const vector& v)
    84. 		{
    85. 			int n = v.size();
    86. 			_vertexs.reserve(n);
    87. 			for (int i = 0; i < n; i++)
    88. 			{
    89. 				_vertexs.push_back(v[i]);
    90. 				_find_index[v[i]] = i;
    91. 			}
    92. 			_table.resize(n, nullptr);
    93. 		}
    94. 	private:
    95. 		//顶点集合
    96. 		vector _vertexs;
    97. 		//顶点和下标的哈希
    98. 		unordered_mapint> _find_index;
    99. 		//邻接表
    100. 		vector*> _table;
    101. 	};
    102. }
    103. void test()
    104. {
    105.     vector a{ "张三", "李四", "王五", "赵六", "周七" };
    106.     List::Graphint, false> g1(a);
    107.     g1.AddEdge("张三", "李四", 100);
    108.     g1.AddEdge("张三", "王五", 200);
    109.     g1.AddEdge("王五", "赵六", 30);
    110.     g1.AddEdge("王五", "周七", 30);
    111.     g1.Print();
    112.  
    113.     g1.Print();
    114. }
    115. int main()
    116. {
    117.     test();
    118.     return 0 ;
    119. }

    2.3.图的DFS和BFS

    我使用的是邻接表的图，来实现的，邻接矩阵也差不多，把代码插入List::graph类中就可以用了；

    1. 		void _DFS(int pos, vector<bool>& visited)
    2. 		{
    3. 			visited[pos] = true;
    4. 			Node* nd = _table[pos];
    5. 			while (nd)
    6. 			{
    7. 				cout << _vertexs[pos] <<  _vertexs[nd->_des] << "  ";
    8. 				if (visited[nd->_des] == false)
    9. 					_DFS(nd->_des, visited);
    10. 				nd = nd->_next;
    11. 			}
    12. 		}
    13. 		void DFS(const V& v)
    14. 		{
    15. 			int pos = _find_index[v];
    16. 			vector<bool> visited(_table.size(), false);
    17. 			_DFS(pos, visited);
    18.  
    19. 		}
    20. 		void BFS(const V& v)
    21. 		{
    22. 			int pos = _find_index[v];
    23. 			vector<bool> visited(_table.size(), false);
    24. 			queue<int> q;
    25. 			q.push(pos);
    26. 			while (!q.empty())
    27. 			{
    28. 				int size = q.size();
    29. 				while (size--)
    30. 				{
    31. 					pos = q.front();
    32. 					visited[pos] = true;
    33. 					q.pop();
    34. 					Node* nd = _table[pos];
    35. 					while (nd)
    36. 					{
    37. 						cout << _vertexs[pos] << _vertexs[nd->_des] << "  ";
    38. 						if (visited[nd->_des] == false)
    39. 							q.push(nd->_des);
    40. 						nd = nd->_next;
    41. 					}
    42. 					
    43. 				}
    44. 			}
    45. 		}

    2.4.最小生成树

    后续5种算法都使用Matrix::Graph类

    最小生成树通常使用的都是无向图；

    • 最小生成树：有n个顶点，使用n-1条边，使用所有顶点连通，那么肯定是不构成回路的（构成回路不可能所有连通）；
    2.4.1.Kruskal(克鲁斯卡尔算法)

    贪心思想：

    1. 将所有边加入优先级队列；
    2. 拿出堆顶边（最小），使用并查集来判断是否构成回路；
    3. 每一条边都有两个顶点，将边的两个顶点使用并查集合并；
    4. 可能   不能构成最小生成树，所以结束条件为优先级队列不为空；
    5. 使用一个变量记录有多少边，最后为n-1条就是最小生成树；

    并查集代码：在最上面

    1.         //贪心思想，选权值最小的边，使用并查集判断是否构成回路
    2. 		W Kruskal(Self& minTree)
    3. 		{
    4. 			//初始化生成树
    5. 			int n = _vertexs.size();
    6. 			minTree._vertexs = _vertexs;
    7. 			minTree._find_index = _find_index;
    8. 			minTree._matrix.resize(n, vector(n, W_MAX) );
    9.  
    10. 			//优先级队列保存边
    11. 			priority_queue, vector>, greater>> pq;
    12.  
    13. 			//添加所有边进优先级队列
    14. 			for (int i = 0; i < n; i++)
    15. 			{
    16. 				for (int j = i + 1; j < n; j++)
    17. 				{
    18. 					if (_matrix[i][j] != W_MAX)
    19. 						pq.push(Edge (i, j, _matrix[i][j]) );
    20. 				}
    21. 			}
    22.  
    23. 			//有n-1条边
    24. 			int count = 0;
    25. 			UnionFindSet ufs(_vertexs);
    26. 			int totalW = 0;
    27. 			while (!pq.empty())
    28. 			{
    29. 				Edge eg= pq.top();
    30. 				pq.pop();
    31. 				bool ret = ufs.Union(_vertexs[eg._src], _vertexs[eg._des]);
    32. 				if (ret == true){//不构成回路
    33. 					cout << _vertexs[eg._src] << ' ' << _vertexs[eg._des] << ' ' << eg._weight << endl;
    34. 					minTree.AddEdge(_vertexs[eg._src], _vertexs[eg._des], eg._weight);
    35. 					count++;
    36. 					totalW += eg._weight;
    37. 				}
    38. 				else {//
    39. 					cout << "构成环  " << _vertexs[eg._src] << ' ' << _vertexs[eg._des] << ' ' << eg._weight << endl;
    40. 				}
    41. 			//构成的总权值
    42. 			}
    43. 			if (count == n - 1)//能构成生成树
    44. 				return totalW;
    45. 			else//不能构成
    46. 				return W();
    47. 		}

    测试代码：

    1. void TestGraphMinTree()
    2. {
    3. 	const char* ch = "abcdefghi";
    4. 	vector<char> v;
    5. 	for (int i = 0; i < strlen(ch); i++)
    6. 	{
    7. 		v.push_back(ch[i]);
    8. 	}
    9. 	Matrix::Graph<char, int> g(v);
    10. 	g.AddEdge('a', 'b', 4);
    11. 	g.AddEdge('a', 'h', 8);
    12. 	g.AddEdge('b', 'c', 8);
    13. 	g.AddEdge('b', 'h', 11);
    14. 	g.AddEdge('c', 'i', 2);
    15. 	g.AddEdge('c', 'f', 4);
    16. 	g.AddEdge('c', 'd', 7);
    17. 	g.AddEdge('d', 'f', 14);
    18. 	g.AddEdge('d', 'e', 9);
    19. 	g.AddEdge('e', 'f', 10);
    20. 	g.AddEdge('f', 'g', 2);
    21. 	g.AddEdge('g', 'h', 1);
    22. 	g.AddEdge('g', 'i', 6);
    23. 	g.AddEdge('h', 'i', 7);
    24.  
    25. 	Matrix::Graph<char, int> kminTree;
    26. 	cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
    27. 	kminTree.Print();
    28. }
     2.4.2.Prim（普里姆算法）

    贪心思想：

    1. 确定一个顶点，将这个顶点的所有边加入优先级队列，这个顶点被设置为已使用；
    2. 拿出堆顶的边，看两个顶点是否已使用，已使用代表构环；
    3. 不构环将这个顶点的所有边，插入优先级队列，这个顶点被设置为已使用；
    4. 重复这个过程，我使用哈希表来判断顶点的，使用一个bool的数组应该更好；
    5. 使用一个变量记录有多少边，最后为n-1条就是最小生成树；
    1.         //贪心思想，按已选择的点延伸，使用set保存已使用，不使用使用过的就一定不会构环
    2. 		//不使用并查集是因为已使用节点都是连通的
    3. 		W Prim(Self &minTree, const V& val)
    4. 		{
    5. 			int n = _vertexs.size();
    6. 			//初始化mintree
    7. 			minTree._vertexs = _vertexs;
    8. 			minTree._find_index = _find_index;
    9. 			minTree._matrix.resize(n, vector(n, W_MAX));
    10. 			
    11. 			int pos = _find_index[val];
    12. 			//保存已使用
    13. 			unordered_set visited;
    14. 			visited.insert(pos);
    15.  
    16. 			priority_queue, vector>, greater> > pq;//
    17. 			for (int j = 0; j < n; j++) {
    18. 				if(_matrix[pos][j] != W_MAX)
    19. 				pq.push(Edge(pos, j, _matrix[pos][j]));
    20. 			}
    21. 			int count = 0;//边数量
    22. 			W TotalW = 0;//权值大小
    23. 			while (!pq.empty())
    24. 			{
    25. 				//获取当前最小
    26. 				Edge dg = pq.top();
    27. 				pq.pop();
    28. 				int des = dg._des;
    29. 				if(visited.count(des))//存在,不可用
    30. 					cout << "构成环  " << _vertexs[dg._src] << ' ' << _vertexs[dg._des] << ' ' << dg._weight << endl;
    31. 				else {
    32. 					for (int j = 0; j < n; j++)//添加新边
    33. 					{
    34. 						if(_matrix[des][j] != W_MAX)
    35. 						pq.push(Edge(des, j, _matrix[des][j]));
    36. 					}
    37. 					visited.insert(des);//已使用
    38. 					minTree._matrix[dg._src][dg._des] = dg._weight;//生成树添边
    39. 					TotalW += dg._weight;
    40. 					count++;
    41. 					cout << _vertexs[dg._src] << ' ' << _vertexs[dg._des] << ' ' << dg._weight << endl;
    42. 				}
    43.  
    44.  
    45. 			}
    46. 			if (count == n - 1)
    47. 				return TotalW;
    48. 			else
    49. 				return W();
    50. 		}

    测试代码： 

     

    1. void TestGraphMinTree()
    2. {
    3. 	const char* ch = "abcdefghi";
    4. 	vector<char> v;
    5. 	for (int i = 0; i < strlen(ch); i++)
    6. 	{
    7. 		v.push_back(ch[i]);
    8. 	}
    9. 	Matrix::Graph<char, int> g(v);
    10. 	g.AddEdge('a', 'b', 4);
    11. 	g.AddEdge('a', 'h', 8);
    12. 	g.AddEdge('b', 'c', 8);
    13. 	g.AddEdge('b', 'h', 11);
    14. 	g.AddEdge('c', 'i', 2);
    15. 	g.AddEdge('c', 'f', 4);
    16. 	g.AddEdge('c', 'd', 7);
    17. 	g.AddEdge('d', 'f', 14);
    18. 	g.AddEdge('d', 'e', 9);
    19. 	g.AddEdge('e', 'f', 10);
    20. 	g.AddEdge('f', 'g', 2);
    21. 	g.AddEdge('g', 'h', 1);
    22. 	g.AddEdge('g', 'i', 6);
    23. 	g.AddEdge('h', 'i', 7);
    24.  
    25. 	Matrix::Graph<char, int> kminTree;
    26. 	cout << "Prim:" << g.Prim(kminTree, 'a') << endl;
    27. 	kminTree.Print();
    28. }

    2.5.最短路径

    最短路径通常使用的都是有向图；

    2.5.1.Dijkstra(迪杰斯特拉算法)

    贪心思想：此算法的缺点：只能用做不带负权的图（负权就是小于0），因为不带负权已确定的路径值不可能更小（一个数加正数不可能更小）；优势：性能最好（时间:O(N^2),邻接矩阵）

    1. 根据传入的顶点，将这个将他的路径值设为0；
    2. 进行遍历找到路径值最小且未使用的顶点，顶点设为已使用
    3. 遍历这个min顶点的所有边，如果这个min顶点路径值+这条边的值  < 目标顶点的路径值，更新目标顶点的路径值和  它的父亲为 这个min顶点；
    4. 循环此过程；
    1. void Dijkstra(const V& v, vector& dest, vector<int>& parentPath )
    2. 		{
    3. 			int n = _vertexs.size();
    4. 			//起始点下标
    5. 			int src = _find_index[v];
    6. 			//和初始点的最短路径
    7. 			dest.resize(n, W_MAX);
    8. 			//顶点父亲下标
    9. 			parentPath.resize(n, -1);
    10.  
    11. 			dest[src] = W();//起始点置为0
    12. 			vector<bool> visited(n, false);
    13. 			//执行n次
    14. 			for (int i = 0; i < n; i++)
    15. 			{
    16. 				int minW = W_MAX, minI = src;
    17. 				//找到当前最小顶点且未使用
    18. 				for (int j = 0; j < n; j++)
    19. 				{
    20. 					if (visited[j] == false && dest[j] < minW)
    21. 					{
    22. 						minI = j;
    23. 						minW = dest[j];
    24. 					}
    25. 				}
    26. 				//设为已使用的值，不可能更小
    27. 				visited[minI] = true;
    28.  
    29. 				//延伸是否能找到更小顶点权值
    30. 				for (int j = 0; j < n; j++)
    31. 				{
    32. 					//满足未使用，两个顶点右边
    33. 					if (visited[j] == false && _matrix[minI][j] != W_MAX)
    34. 					{
    35. 						//新路径值更小
    36. 						if (dest[minI] + _matrix[minI][j] < dest[j])
    37. 						{
    38. 							//设置路径值和父顶点下标
    39. 							dest[j] = dest[minI] + _matrix[minI][j];
    40. 							parentPath[j] = minI;
    41. 						}
    42. 					}
    43. 				}
    44. 			}
    45. 		}

    测试代码：

    1. void TestGraphDijkstra()
    2. {
    3. 	const char* ch = "syztx";
    4. 	vector<char> v;
    5. 	for (int i = 0; i < strlen(ch); i++)
    6. 	{
    7. 		v.push_back(ch[i]);
    8. 	}
    9. 	Matrix::Graph<char, int, true, INT_MAX > g(v);
    10. 	g.AddEdge('s', 't', 10);
    11. 	g.AddEdge('s', 'y', 5);
    12. 	g.AddEdge('y', 't', 3);
    13. 	g.AddEdge('y', 'x', 9);
    14. 	g.AddEdge('y', 'z', 2);
    15. 	g.AddEdge('z', 's', 7);
    16. 	g.AddEdge('z', 'x', 6);
    17. 	g.AddEdge('t', 'y', 2);
    18. 	g.AddEdge('t', 'x', 1);
    19. 	g.AddEdge('x', 'z', 4);
    20.  
    21. 	vector<int> dest;
    22. 	vector<int> parentPath;
    23. 	g.Dijkstra('s', dest, parentPath);
    24. }
    2.5.2.Bellman-Ford（贝尔曼-福特算法）

    暴力思想：将邻接矩阵遍历n-1次；时间复杂度:O(N^3)，优势：解决带负权的图问题

    1. 将传入的顶点的路径值设为0；
    2. 遍历整个邻接矩阵，当前顶点不为初始值且两者有边，当前顶点路径值 + 边的权值  < 目标顶点路径值，更新目标顶点的路径值和父亲；
    3. 遍历n - 1次，每个顶点最多有n - 1条边（除自己），如果一次遍历没有顶点路径值变小，结束循环；
    4. 如果带负权回路，可以无限小，没有结果，return false；
    1.         bool BellmanFord(const V& v, vector& dest, vector<int>& parentPath)
    2. 		{
    3. 			int n = _vertexs.size();
    4. 			int src = _find_index[v];//初始位置
    5.  
    6. 			dest.resize(n, W_MAX);
    7. 			parentPath.resize(n, -1);
    8.  
    9. 			//初始化初始位置
    10. 			dest[src] = 0;
    11.  
    12. 			//为什么是n-1次：任意顶点到其他所有顶点最多n-1次，再多说明构成负权回路
    13. 			for (int k = 0; k < n - 1; k++)
    14. 			{
    15. 				bool quit = true;
    16. 				//遍历权值邻接矩阵
    17. 				for (int i = 0; i < n; i++)
    18. 				{
    19. 					for (int j = 0; j < n; j++)
    20. 					{
    21.                         //有边且本身不为初始值
    22. 						if (_matrix[i][j] != W_MAX && dest[i] != W_MAX && dest[i] + _matrix[i][j] < dest[j])
    23. 						{
    24. 							//设置更小的路径值和父顶点下标
    25. 							dest[j] = dest[i] + _matrix[i][j];
    26. 							parentPath[j] = i;
    27. 							quit = false;
    28. 						}
    29. 					}
    30. 				}
    31. 				if (quit)
    32. 					break;
    33. 			}
    34.  
    35. 			//判断是否构成负权回路
    36. 			for (int i = 0; i < n; i++)
    37. 			{
    38. 				for (int j = 0; j < n; j++)
    39. 				{
    40. 					if (_matrix[i][j] != W_MAX && dest[i] != W_MAX && dest[i] + _matrix[i][j] < dest[j])
    41. 						return false;
    42. 				}
    43. 			}
    44. 			return true;
    45. 		}

    测试代码：

    1. void TestGraphBellmanFord()
    2. {
    3. 	const char* ch = "syztx";
    4. 	vector<char> v;
    5. 	for (int i = 0; i < strlen(ch); i++)
    6. 	{
    7. 		v.push_back(ch[i]);
    8. 	}
    9. 	Matrix::Graph<char, int, true, INT_MAX> g(v);
    10. 	g.AddEdge('s', 't', 6);
    11. 	g.AddEdge('s', 'y', 7);
    12. 	g.AddEdge('y', 'z', 9);
    13. 	g.AddEdge('y', 'x', -3);
    14. 	g.AddEdge('z', 's', 2);
    15. 	g.AddEdge('z', 'x', 7);
    16. 	g.AddEdge('t', 'x', 5);
    17. 	g.AddEdge('t', 'y', 8);
    18. 	g.AddEdge('t', 'z', -4);
    19. 	g.AddEdge('x', 't', -2);
    20. 	vector<int> dist;
    21. 	vector<int> parentPath;
    22. 	if (g.BellmanFord('s', dist, parentPath))
    23. 	{
    24. 	}
    25. 	else
    26. 	{
    27. 		cout << "存在负权回路" << endl;
    28. 	}
    29. }
    2.5.3.Floyd-Warshall（弗洛伊德算法）

    动态规划思想：时间复杂度：O(N^3);可以算出所有节点为起始点的最短路径；

    1. 初始化路径值1.自己初始化为0   2.两顶点存在边初始化为边的权值；
    2. 顶点i 到 j 存在一个顶点k，满足Edge(i, k) + Edge(k, j)  < Edge(i, j);说明有更小的路径值；
    1. 		void FloydWarShall(vector>& vvDest, vectorint>>& vvParentPath)
    2. 		{
    3. 			int n = _vertexs.size();
    4. 			vvDest.resize(n);
    5. 			vvParentPath.resize(n);
    6. 			//初始化
    7. 			for (int i = 0; i < n; i++)
    8. 			{
    9. 				vvDest[i].resize(n, W_MAX);
    10. 				vvParentPath[i].resize(n, -1);
    11. 			}
    12. 			//直接相连的顶点添加入二维数组
    13. 			for (int i = 0; i < n; i++)
    14. 			{
    15. 				for (int j = 0; j < n; j++)
    16. 				{
    17. 					if (_matrix[i][j] != W_MAX)
    18. 					{
    19. 						vvDest[i][j] = _matrix[i][j];
    20. 						vvParentPath[i][j] = i;
    21. 					}
    22. 					else
    23. 					{
    24. 						vvParentPath[i][j] = -1;
    25. 					}
    26. 					if (i == j) 
    27. 					{
    28. 						vvParentPath[i][j] = -1;
    29. 						vvDest[i][j] = 0;
    30. 					}
    31. 				}
    32. 			}
    33. 			
    34. 			//动规思想：i 到 j之间存在一个k，并且i到k + k到j  < i 到 j
    35. 			for (int k = 0; k < n; k++)
    36. 			{
    37. 				for (int i = 0; i < n; i++)
    38. 				{
    39. 					for (int j = 0; j < n; j++)
    40. 					{
    41. 						if (vvDest[i][k] != W_MAX && vvDest[k][j] != W_MAX && vvDest[i][k] + vvDest[k][j] < vvDest[i][j])
    42. 						{
    43. 							
    44. 							vvDest[i][j] = vvDest[i][k] + vvDest[k][j];
    45. 							vvParentPath[i][j] = vvParentPath[k][j];
    46. 						}
    47. 					}
    48. 				}
    49. 			}
    50.  
    51. 		}

    测试代码：

    1. void TestFloydWarShall()
    2. {
    3. 	const char* ch = "12345";
    4. 	vector<char> v;
    5. 	for (int i = 0; i < strlen(ch); i++)
    6. 	{
    7. 		v.push_back(ch[i]);
    8. 	}
    9. 	Matrix::Graph<char, int, true, INT_MAX> g(v);
    10. 	g.AddEdge('1', '2', 3);
    11. 	g.AddEdge('1', '3', 8);
    12. 	g.AddEdge('1', '5', -4);
    13. 	g.AddEdge('2', '4', 1);
    14. 	g.AddEdge('2', '5', 7);
    15. 	g.AddEdge('3', '2', 4);
    16. 	g.AddEdge('4', '1', 2);
    17. 	g.AddEdge('4', '3', -5);
    18. 	g.AddEdge('5', '4', 6);
    19. 	vectorint>> vvDist;
    20. 	vectorint>> vvParentPath;
    21. 	g.FloydWarShall(vvDist, vvParentPath);
    22.  
    23. }

  • 相关阅读:
    c++ 函数的参数是否可以为auto
    Dockerfile详解
    codeforces：E. Madoka and The Best University【因数list + 分析拆解 + 公因数特性 + 欧拉函数】
    计算机毕业设计SSM茶叶产品质量安全可追溯系统【附源码数据库】
    Day09-尚品汇-detail路由组件展示商品售卖属性-剪裁
    C++ 类和对象篇(六) 拷贝构造函数
    Eureka简介及简单使用
    c# npoi创建数据有效性约束制定列和单元格分别设置
    JavaScript基本功之迭代器(iterator)的使用和原理
    03OpenCV图像的掩膜操作
  • 原文地址：https://blog.csdn.net/m0_72964546/article/details/134025706