C++--数据结构--图的相关概念及模拟实现--高阶0712-创新互联

1. 图的基本概念

图(G)是由顶点(V)集合及顶点间的关系(边 E)组成的一种数据结构;

目前创新互联已为上1000+的企业提供了网站建设、域名、虚拟主机、网站托管、服务器托管、企业网站设计、广汉网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。

顶点:图中的结点,第i个顶点记作vi。  两个顶点vi和vj相关称作vi和vj之间有一条边。

有向图:顶点对是有序的,顶点对称为顶点x到顶点y的一条 边(弧),和是两条不同的边。

无向图:顶点对(x, y) 是无序的,顶点对(x,y)称为顶点x和顶点y相关联的一条边,这条边没有特定方向,(x, y)和(y,x) 是同一条边。

完全图:

  • 无向完全图:任意两个顶点之间有且仅有一条边。

  • 有向完全图:任意两个 顶点之间有且仅有方向相反的边。

邻接顶点:

无向图:u、v互为邻接顶点,边(u,v)依附于顶点u和v

有向图:顶点u邻接到v,顶点v邻接自顶点u,边(u,v)与顶点u,v相关联

顶点的度:顶点V的度是指与他相关联的边的条数。

度为3

度为2

路径:从顶点vi出发有一组边使其可到达顶点vj,则称顶点vi到顶点vj的顶 点序列为从顶点vi到顶点vj的路径。

路径长度:对于不带权的图,一条路径的路径长度是指该路径上的边的条数;对于带权的图,一 条路径的路径长度是指该路径上各个边权值的总和。

简单路径与回路:路径上各顶点v1、v2、v3...均不重复,则为简单路径。路径上第一个顶点和最后一个顶点重合,则称为回路。

子图:图G1包含图G2的所有顶点和所有路径,则G2是G1的子图。

连通图:在无向图从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图为连通图。

强连通图:在有向图中,在每一对顶点vi和vj之间都存在从vi到vj的路径,也存在从vj到vi的路径,则此图称为强连通图。

生成树:一个连通图的最小连通子图称为该图的生成树。

2. 图的存储结构 2.1 邻接矩阵

因为节点与节点之间的关系就是连通与否,即为0或者1,因此邻接矩阵(二维数组)即是:先用一 个数组将定点保存,然后采用矩阵来表示节点与节点之间的关系。

注意:

无向图的邻接矩阵是对称的,第i行(列)元素之和,就是顶点i的度。

有向图的邻接矩阵则不一 定是对称的,第i行(列)元素之和就是顶点i的出(入)度。

如果边带有权值,并且两个节点之间是连通的,上图中的边的关系就用权值代替,如果两个顶点不通,则使用无穷大代替。 

2.2 邻接矩阵的模拟实现
namespace matrix
{
	//V ->顶点的数据类型  W ->权重 一般都是int
	templateclass Graph
	{
	public:
		Graph() = default;
		Graph(const V* a, size_t n)
		{
			_vertexs.reserve(n); //_vertexsV* a
			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);
		
		//添加边
		void AddEdge(const V& src, const V& dst, const W& w);
        
        //等等其他函数 会在下文中详细实现函数
	private:
		vector_vertexs;//顶点集合 比如名字 下标0放的是张三 下标1放的是 ......
		map_indexMap;//顶点映射下标  张三的对应的下标是0 ....
		vector>_matrix;//邻接矩阵
	};
}

获取顶点对应的下标

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);
			_matrix[srci][dsti] = w;
			if (Direction == false) //如果是无向图 A-B 和B-A一样 还需要反着再来一次
			{
				_matrix[dsti][srci] = w;
			}
		}

打印

void Print()
		{
			//先打印每个下标对应的是哪个顶点
			for (size_t i = 0; i< _vertexs.size(); 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++)
			{
				printf("%4d", i);//纵坐标
				for (size_t j = 0; j< _matrix[i].size(); j++)
				{
					if (_matrix[i][j] == MAX_W)
					{
						printf("%4c",'*');
					}
					else
					{
						printf("%4d", _matrix[i][j]);
					}
				}
				cout<< endl;
			}
		}

测试代码及结果

邻接矩阵的缺陷:如果要查看一个顶点相连的边的关系,需要O(n)的时间复杂度。

2.2 邻接表

使用数组表示顶点的集合,使用链表表示边的关系。

namespace link_table
{
    //存储关系的链表结构体
	templatestruct Edge
	{
		//int _srci;
		int _dsti;  // 目标点的下标
		W _w;		// 权值
		Edge* _next;

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

	templateclass Graph
	{
		typedef EdgeEdge;
	public:
		Graph(const V* a, size_t n);//同上
		size_t GetVertexIndex(const V& v);//同上
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);

			// 1->2
			Edge* eg = new Edge(dsti, w);
			eg->_next = _tables[srci];
			_tables[srci] = eg;
			
			// 2->1
			if (Direction == false)
			{
				Edge* eg = new Edge(srci, w);
				eg->_next = _tables[dsti];
				_tables[dsti] = eg;
			}
		}
		void Print()
		{
			// 顶点
			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 
                    <<":"<_w<<"]->";
					cur = cur->_next;
				}
				cout<<"nullptr"<_vertexs;			// 顶点集合
		map_indexMap;		// 顶点映射下标
		vector_tables;		// 邻接表
	};


}

邻接表不常用,我们下面实现的成员函数,依旧以邻接矩阵为主体实现。

3. 图的遍历 3.1 广度优先遍历
void BFS(const V& src) //广度优先遍历 
		{
			size_t srci = GetvertexIndex(src);
			queueq;
			vectorvisited(_vertexs.size(), false);//每个顶点都没有被访问过
			q.push(srci);
			visited[srci] = true;
			size_t n = _vertexs.size();
			
				
			while (!q.empty())
			{
                int levelsize = q.size();
				for (int i = 0; i< levelsize; i++)
				{
					int front = q.front();
					q.pop();
					cout<< front<< ":"<< _vertexs[front]<<" ";
					//把front的邻接节点放入队列
					for (size_t j = 0; j< n; j++)
					{
						if(_matrix[front][j]!=MAX_W)
						{
							if (visited[j] == false)
							{
								q.push(j);
								visited[j] = true;
							}
						}
					}
				}
				cout<< endl;
			}
			cout<< endl;

		}

测试代码及打印结果

3.2 深度优先遍历
void _DFS(size_t srci, vector& visited)
		{
			cout<< srci<< ":"<< _vertexs[srci]<< endl;
			visited[srci] = true;

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

		}

		void DFS(const V& src)
		{
			size_t srci = GetVertexIndex(src);
			vectorvisited(_vertexs.size(), false);

			_DFS(srci, visited);
		}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


分享题目:C++--数据结构--图的相关概念及模拟实现--高阶0712-创新互联
文章来源:http://scyanting.com/article/dddcci.html