【数据结构】图Graph的邻接矩阵，邻接表及深度、广度遍历

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】图Graph的邻接矩阵，邻接表及深度、广度遍历，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

图的分类

有/无向图

如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。
下面介绍图的两种存储结构

1、邻接矩阵

用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵

邻接矩阵的思想图

代码实现

  1. 	int GetIndex(const V& v)//获取顶点
  2. 	{
  3. 		for (size_t i=0;i<_size;i++)
  4. 		{
  5. 			if(_vertex[i]==v)
  6. 				return i;
  7. 		}
  8. 		throw std::invalid_argument("顶点赋值错误");
  9. 	}
  10. 	void AddEdge(const V& src,const V& dst,const W& w)//增加矩阵中的点
  11. 	{
  12. 		size_t srcIndex=GetIndex(src);
  13. 		size_t dstIndex=GetIndex(dst);
  14. 		_matrix[srcIndex][dstIndex]=w;
  15. 		if(_isDirection==false)
  16. 			_matrix[dstIndex][srcIndex]=w;
  17. 	}

2、邻接表

图的邻接矩阵存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。

邻接表的思想图


邻接表的代码实现

  1. int GetIndex(const V& v)
  2. 	{
  3. 		for (int i=0;i<_vertex.size();i++)
  4. 		{
  5. 			if(_vertex[i]==v)
  6. 				return i;
  7. 		}
  8. 		throw std::invalid_argument("顶点赋值错误");
  9. 	}
  10. 	void _AddEdge(size_t src,size_t dst,const W& w)
  11. 	{
  12. 		// _table[src][dst]._w=w;
  14. 		Node* cur=new Node(src,dst,w);
  15. 		cur->Next=_table[src];
  16. 		_table[src]=cur;
  18. 	}
  19. 	void AddEdge(const V& src,const W& w)
  20. 	{
  21. 		int srcIndex=GetIndex(src);
  22. 		int dstIndex=GetIndex(dst);
  23. 		if (_isDirection)
  24. 		{
  25. 			_AddEdge(srcIndex,dstIndex,w);
  26. 		}
  27. 		else
  28. 		{
  29. 			_AddEdge(srcIndex,w);
  30. 			_AddEdge(dstIndex,srcIndex,w);
  31. 		}
  32. 	}

邻接表的深度优先遍历，类似于二叉树的前序遍历

一个节点知道遍历到无路可走才遍历旁边的节点


代码实现，这里用vector实现

  1. void DFS(const V& v)
  2. 	{
  3. 		vector<bool> visted(_vertex.size(),false);
  4. 		cout<<v;
  5. 		_DFS(GetIndex(v),visted);
  6. 		for(size_t i=0;i<_vertex.size();i++)
  7. 		{
  8. 			if(visted[i]==false)
  9. 			{
  10. 				cout<<_vertex[i];
  11. 				visted[i]=true;
  12. 				_DFS(i,visted);
  13. 			}
  14. 		}
  15. 		cout<<"NULL"<<endl;
  16. 	}
  17. 	void _DFS(size_t src,vector<bool>& visted)
  18. 	{
  19. 		
  20. 		visted[src]=true;
  21. 		Node* cur=_table[src];
  22. 		
  23.         cout<<"["<<src<<"]->";
  24. 		while (cur)
  25. 		{
  26. 			
  27. 			if(visted[cur->_dst]==false)
  28. 			{
  29. 				cout<<_vertex[cur->_dst];
  30. 				visted[cur->_dst]=true;
  31. 				_DFS(cur->_dst,visted);
  32. 			}
  33. 			cur=cur->Next;
  34. 		}
  36. 	}

邻接表的广度优先遍历

一个节点把它周围的节点全部都遍历完，才会进行前进遍历

代码实现，这里用队列实现，队列有先进先出的特点，符合此算法

  1. void _BFS(size_t src,vector<bool>& visted)
  2. 	{
  3. 		visted[src]=true;
  4. 		cout<<"["<<src<<"]->";
  5. 		queue<size_t> q;
  6. 		q.push(src);
  7. 		
  8. 		while (!q.empty())
  9. 		{
  10. 			 src=q.front();
  11. 			 q.pop();
  12. 			 Node* cur=_table[src];
  14. 			 while (cur)
  15. 			 {
  16. 				 if(visted[cur->_dst]==false)
  17. 				 {
  18. 				cout<<_vertex[cur->_dst]<<"["<<cur->_dst<<"]"<<"-> ";
  19. 				 visted[cur->_dst]=true;
  20. 				 q.push(cur->_dst);
  21. 				 }
  22. 				 cur=cur->Next;
  23. 				 
  24. 			 }
  26. 		}
  27. 		cout<<endl;
  28. 	}
  29. 	void BFS(const V& v)
  30. 	{
  31. 		vector<bool> visted(_vertex.size(),false);
  32. 		cout<<v;
  33. 		_BFS(GetIndex(v),visted);
  34. 	}

附全部代码及其测试
临街矩阵 

  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. using namespace std;
  5. template<class V,class W>
  6. class GraphMatrix
  7. {
  8. public:
  9. 	GraphMatrix(V* vertex,size_t size,bool isDirection=false,const int invalid=0 )
  10. 		:_vertex(new V[size]),_size(size),_isDirection(isDirection)
  11. 	{
  12. 		_matrix=new W*[size];
  13. 		for(size_t i=0;i<size;i++)
  14. 		{
  15. 			_vertex[i]=vertex[i];
  16. 			_matrix[i]=new W[size];
  17. 			for (size_t j=0;j<size;j++)
  18. 			{
  19. 				_matrix[i][j]=invalid;
  20. 			}
  21. 		}
  23. 	}
  24. 	~GraphMatrix()
  25. 	{
  26. 		delete[] _vertex;
  27. 		delete[] _matrix;
  28. 		_size=0;
  29. 	}
  30. 	int GetIndex(const V& v)//获取顶点
  31. 	{
  32. 		for (size_t i=0;i<_size;i++)
  33. 		{
  34. 			if(_vertex[i]==v)
  35. 				return i;
  36. 		}
  37. 		throw std::invalid_argument("顶点赋值错误");
  38. 	}
  39. 	void AddEdge(const V& src,const W& w)//增加矩阵中的点
  40. 	{
  41. 		size_t srcIndex=GetIndex(src);
  42. 		size_t dstIndex=GetIndex(dst);
  43. 		_matrix[srcIndex][dstIndex]=w;
  44. 		if(_isDirection==false)
  45. 			_matrix[dstIndex][srcIndex]=w;
  46. 	}
  47. 	void PrintMaxtix()
  48. 	{
  49. 		for(size_t i=0;i<_size;i++)
  50. 		{
  51. 			for(size_t j=0;j<_size;j++)
  52. 			{
  53. 				cout<<_matrix[i][j]<<"     ";
  54. 			}
  55. 			cout<<endl;
  56. 		}
  57. 	}
  58. protected:
  59. 	V* _vertex;
  60. 	W** _matrix;
  61. 	size_t _size;
  62. 	bool _isDirection;
  63. };
  64. void TestGraphMatrix()
  65. {
  66. 	string v[4]={"西安","宝鸡","咸阳","延安"};
  67. 	GraphMatrix<string,size_t> gm(v,4);//无向图
  68. 	cout<<"无向图邻接矩阵："<<endl;
  69. 	gm.AddEdge("西安",7);
  70. 	gm.AddEdge("西安",200);
  71. 	gm.AddEdge("西安","延安",500);
  72. 	gm.AddEdge("宝鸡",100);
  73. 	gm.AddEdge("宝鸡",200);
  74. 	gm.AddEdge("咸阳",100);
  75. 	gm.PrintMaxtix();
  76. 	GraphMatrix<string,size_t> gm1(v,4,true);//有向图
  77. 	cout<<"有向图邻接矩阵："<<endl;
  78. 	gm1.AddEdge("西安",7);
  79. 	gm1.AddEdge("西安",200);
  80. 	gm1.AddEdge("西安",500);
  81. 	gm1.AddEdge("宝鸡",100);
  82. 	gm1.AddEdge("宝鸡",200);
  83. 	gm1.AddEdge("咸阳",100);
  84. 	gm1.PrintMaxtix();
  85. }
邻接表及其遍历 

  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6. template<class V,class W>
  7. class GraphLink
  8. {
  9. 	struct Node 
  10. 	{
  11. 		W _w;
  12. 		size_t _src;
  13. 		size_t _dst;
  14. 		Node* Next;
  15. 		Node(int src=0,int dst=0,const W& w=W())
  16. 			:_src(src),_dst(dst),_w(w),Next(NULL)
  17. 		{}
  18. 	};
  19. public:
  20. 	GraphLink(const V* vertex,int size,bool isDirection=false)
  21. 		:_isDirection(isDirection)
  22. 	{
  23. 		_vertex.resize(size);
  24. 		_table.resize(size);
  25. 		
  26. 		for(size_t i=0;i<size;i++)
  27. 		{
  28. 			_vertex[i]=vertex[i];
  29. 		}
  31. 	}
  32. 	int GetIndex(const V& v)
  33. 	{
  34. 		for (int i=0;i<_vertex.size();i++)
  35. 		{
  36. 			if(_vertex[i]==v)
  37. 				return i;
  38. 		}
  39. 		throw std::invalid_argument("顶点赋值错误");
  40. 	}
  41. 	void _AddEdge(size_t src,w);
  42. 		}
  43. 	}
  44. 	void DFS(const V& v)
  45. 	{
  46. 		vector<bool> visted(_vertex.size(),visted);
  47. 			}
  48. 			cur=cur->Next;
  49. 		}
  51. 	}
  52. 	void _BFS(size_t src,visted);
  53. 	}
  54. 	void PrintLink()
  55. 	{
  56. 		for (size_t i=0;i<_vertex.size();++i)
  57. 		{
  58. 	     cout<<_vertex[i]<<"["<<i<<"]->";
  59. 		  Node* cur=_table[i];
  60. 		  while (cur)
  61. 		  {
  62. 			  cout<<_vertex[cur->_dst]<<" ["<<cur->_dst<<"]"<<cur->_w<<"->";
  63. 			  cur=cur->Next;
  64. 		  }
  65. 		  cout<<"NULL"<<endl;
  66. 		}
  68. 	}
  69. protected:
  70. 	vector<V> _vertex;
  71. 	vector<Node*> _table;
  72. 	bool _isDirection;
  73. };
  74. void TestGraphLink()
  75. {
  76. 	string v[4]={"西安","延安"};
  77. 	GraphLink<string,4);//无向图邻接表
  78. 	cout<<"无向图邻接表："<<endl;
  79. 	gm.AddEdge("西安",100);
  80. 	gm.PrintLink();
  81. 	cout<<"无向图DFS遍历："<<endl;//深度优先遍历
  82. 	gm.DFS("西安");
  83. 	gm.DFS("宝鸡");
  84. 	gm.DFS("咸阳");
  85. 	gm.DFS("延安");
  86. 	cout<<"无向图BFS遍历："<<endl;//广度优先遍历
  87. 	gm.BFS("西安");
  88. 	gm.BFS("宝鸡");
  89. 	gm.BFS("咸阳");
  90. 	gm.BFS("延安");
  91. 	GraphLink<string,true);//有向图邻接表
  92. 	cout<<"有向图邻接表："<<endl;
  93. 	gm1.AddEdge("西安",100);
  94. 	gm1.PrintLink();
  95. 	cout<<"有向图DFS遍历："<<endl;//深度优先遍历
  96. 	gm1.DFS("西安");
  97. 	gm1.DFS("宝鸡");
  98. 	gm1.DFS("咸阳");
  99. 	gm1.DFS("延安");
  100. 	cout<<"有向图BFS遍历："<<endl;//广度优先遍历
  101. 	gm1.BFS("西安");
  102. 	gm1.BFS("宝鸡");
  103. 	gm1.BFS("咸阳");
  104. 	gm1.BFS("延安");
  105. }

测试代码 

  1. #include "Graph.h"
  2. #include "GraphLink.h"
  3. #include<stdlib.h>
  4. int main()
  5. {
  6. 	TestGraphMatrix();
  7. 	TestGraphLink();
  8. 	system("pause");
  9. 	return 0;
  10. }
测试结果

猜你在找的数据结构相关文章

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test