当前位置： 首页 > article >正文

【c++高阶DS】图

article 2024/12/25 23:53:38

Alt

🔥个人主页：Quitecoder

🔥专栏：c++笔记仓

Alt

目录

  • 01.并查集
  • 02.图的介绍
  • 03.图的存储结构
    • 03.1.邻接矩阵
    • 03.2.邻接表
    • 03.3.矩阵版本代码实现
    • 03.4.邻接表版本代码实现
  • 完整代码：

01.并查集

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)

比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不同的学校，起先互不相识，每个学生都是一个独立的小团体，现给这些学生进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个数

在这里插入图片描述
毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是：
西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识了，10个人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。

在这里插入图片描述
在这里插入图片描述
从上图可以看出：编号6,7,8同学属于0号小分队，该小分队中有4人(包含队长0)；编号为4和9的同学属于1号小分队，该小分队有3人(包含队长1)，编号为3和5的同学属于2号小分队，该小分队有3个人(包含队长1)

仔细观察数组中内融化，可以得出以下结论：

  1. 数组的下标对应集合中元素的编号
  2. 数组中如果为负数，负号代表根，数字代表该集合中元素个数
  3. 数组中如果为非负数，代表该元素双亲在数组中的下标

在公司工作一段时间后，西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起，两个小圈子的学生相互介绍，最后成为了一个小圈子

在这里插入图片描述
现在0集合有7个人，2集合有3个人，总共两个朋友圈

通过以上例子可知，并查集一般可以解决一下问题：

  1. 查找元素属于哪个集合
    沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)
  2. 查看两个元素是否属于同一个集合
    沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
  3. 将两个集合归并成一个集合
    将两个集合中的元素合并
    将一个集合名称改成另一个集合的名称
  4. 集合的个数
    遍历数组，数组中元素为负数的个数即为集合的个数

代码实现：

class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_ufs(n, -1)
	{}
	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);

		if (root1 == root2)return;

		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}
	int FindRoot(int x)
	{
		int parent = x;
		while (_ufs[parent] >= 0)
		{
			parent = _ufs[parent];
		}
		return parent;
	}
	bool InSet(int x1,int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}

	size_t SetSize()
	{
		size_t size= 0;
		for (int i = 0; i < _ufs.size(); i++)
		{
			if (_ufs[i] < 0) ++size;
		}
		return size;
	}
private:
	vector<int> _ufs;
};

题目链接1：LCR 116. 省份数量
题目描述：在这里插入图片描述

class Solution {
public:   
   int findCircleNum(vector<vector<int>>& isConnected) {
        UnionFindSet ufs(isConnected.size());
        for(int i=0;i<isConnected.size();i++)
        {
            for(int j=0;j<isConnected[i].size();j++)
            {
                if(isConnected[i][j]==1)
                {
                    ufs.Union(i,j);
                }
            }
        }
        return ufs.SetSize();
    }
};

题目链接2：990. 等式方程的可满足性
题目描述：在这里插入图片描述

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        UnionFindSet _ufs(26);
        for(auto& str: equations)
        {
            if(str[1]=='=')
            {
                _ufs.Union(str[0]-'a',str[3]-'a');
            }
        }for(auto& str2: equations)
        {
            if(str2[1]=='!')
            {
                if(_ufs.InSet(str2[0]-'a',str2[3]-'a')) return false;
            }
        }
        return true;
    }
};

02.图的介绍

并查集是后面的铺垫，这里我们对图进行讲解：

图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)，其中：顶点集合V = {x|x属于某个数据对象集}是有穷非空集合；

E = {(x,y)|x,y属于V}或者E = {<x, y>|x,y属于V && Path(x, y)}是顶点间关系的有穷集合，也叫做边的集合。(x, y)表示x到y的一条双向通路，即(x, y)是无方向的；Path(x, y)表示从x到y的一条单向通路，即Path(x, y)是有方向的

在这里插入图片描述
顶点和边：图中结点称为顶点，第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边，图中的第k条边记作ek，ek = (vi，vj)或<vi，vj>

  • 有向图和无向图：在有向图中，顶点对<x, y>是有序的，顶点对<x，y>称为顶点x到顶点y的一条边(弧)，<x, y>和<y, x>是两条不同的边，比如图G3和G4为有向图。在无向图中，顶点对(x, y)是无序的，顶点对(x,y)称为顶点x和顶点y相关联的一条边，这条边没有特定方向，(x, y)和(y，x)是同一条边，比如图G1和G2为无向图。注意：无向边(x, y)等于有向边<x, y>和<y, x>

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

  • 邻接顶点：在无向图中G中，若(u, v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u,v)依附于顶点u和v；在有向图G中，若<u, v>是E(G)中的一条边，则称顶点u邻接到v，顶点v邻接自顶点u，并称边<u, v>与顶点u和顶点v相关联

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

  • 路径：在图G = (V， E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径

  • 路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和
    在这里插入图片描述

简单路径与回路：若路径上各顶点v1，v2，v3，…，vm均不重复，则称这样的路径为简单路径。若路径上第一个顶点v1和最后一个顶点vm重合，则称这样的路径为回路或环
在这里插入图片描述
子图：设图G = {V, E}和图G1 = {V1，E1}，若V1属于V且E1属于E，则称G1是G的子图

在这里插入图片描述

  • 连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的，则称此图为连通图。
  • 强连通图：在有向图中，若在每一对顶点vi和vj之间都存在一条从vi到vj的路径，也存在一条从vj到vi的路径，则称此图是强连通图。
  • 生成树：一个连通图（无向图）的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。

03.图的存储结构

因为图中既有节点，又有边(节点与节点之间的关系)，因此，在图的存储中，只需要保存：节点和边关系即可。节点保存比较简单，只需要一段连续空间即可，那边关系该怎么保存呢

03.1.邻接矩阵

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

在这里插入图片描述

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

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

在这里插入图片描述
邻接矩阵存储方式非常适合稠密图
邻接矩阵O(1)判断两个顶点的连接关系，并取到权值

用邻接矩阵存储图的有点是能够快速知道两个顶点是否连通，缺陷是如果顶点比较多，边比较少时，矩阵中存储了大量的0成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求，同时也不好求一个顶点连接的边数

03.2.邻接表

邻接表：使用数组表示顶点的集合，使用链表表示边的关系。

  1. 无向图邻接表存储
    在这里插入图片描述
    指针数组：自己连接顶点边全都挂在下面
  2. 有向图邻接表存储
    在这里插入图片描述
    注意：有向图中每条边在邻接表中只出现一次，与顶点vi对应的邻接表所含结点的个数，就是该顶点的出度，也称出度表，要得到vi顶点的入度，必须检测其他所有顶点对应的边链表，看有多少边顶点的dst取值是i。

邻接表适合存储稀疏图，也适合查找一个顶点连接出去的边，不适合去确定两个顶点是否相连及权值

03.3.矩阵版本代码实现

template<class V,class W, W MAX_W = INT_MAX,bool Direction = false>
class Graph
{

private:
	vector<V> _vertexs;//顶点集合;
	map<V, int> _indexMap;//顶点映射下标;
	vector<vector<W>> _matrix;// 存储边集合的矩阵
};

构造函数：

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);
	}
}

这是一个带顶点数组 a 和顶点数量 n 的构造函数，作用是：

  • 初始化图的顶点集合 _vertexs。
  • 使用一个映射 _indexMap 存储顶点到索引的映射关系，方便后续操作。
  • 使用二维矩阵 _matrix 初始化边的权值集合

_vertexs.reserve(n)：为顶点集合预留容量，避免后续动态扩展的开销。

遍历顶点数组，将每个顶点添加到 _vertexs，并记录其在数组中的索引到 _indexMap，实现顶点到索引的快速查找

_matrix.resize(n)：将矩阵调整为 n×n大小。
每行使用 resize(n, MAX_W) 将所有初始值设置为 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, consy W& w)
{
	size_t srci = GetVertexIndex(src);
	size_t dsti = GetVertexIndex(dst);
	_matrix[srci][dsti] = w; 
	if (Direction == false)
	{
		_matrix[dsti][srci] = w;
	}
}

这段代码实现了两个关键功能：

  1. GetVertexIndex 函数：查找顶点的索引。
  2. AddEdge 函数：在图中添加边（支持有向图和无向图）。

实现逻辑：

  • 使用 _indexMap.find(v) 在映射 _indexMap 中查找顶点 v。
  • 如果找到，返回对应的索引 it->second。
  • 如果未找到，抛出异常 invalid_argument("不存在的顶点")，提示顶点不存在。

在图中添加一条边，支持有向图和无向图。

输入参数：

  • const V& src：边的起点顶点。
  • const V& dst：边的终点顶点。
  • const W& w：边的权值，引用方式传递，避免复制。

处理方向性：

  • 有向图：只设置 _matrix[srci][dsti]。
  • 无向图：同时设置 _matrix[srci][dsti] 和 _matrix[dsti][srci]。

打印函数：

void Print()
{
	// 打印顶点和下标映射关系
	for (size_t i = 0; i < _vertexs.size(); ++i)
	{
		cout << _vertexs[i] << "-" << i << " ";
	}
	cout << endl << endl;
	cout << "  ";
	for (size_t i = 0; i < _vertexs.size(); ++i)
	{
		cout << 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 << _matrix[i][j] << " ";
			else
				cout << "#" << " ";
		}
		cout << endl;
	}
	cout << endl << endl;
	// 打印所有的边
	for (size_t i = 0; i < _matrix.size(); ++i)
	{
		for (size_t j = 0; j < _matrix[i].size(); ++j)
		{
			if (i < j && _matrix[i][j] != MAX_W)
			{
				cout << _vertexs[i] << "-" << _vertexs[j] << ":" <<
					_matrix[i][j] << endl;
			}
		}
	}
}

进行测试：

在这里插入图片描述

03.4.邻接表版本代码实现

template<class W>
struct LinkEdge
{
    int _srcindex;           // 边的起点索引
    int _dstindex;           // 边的终点索引
    W _w;                    // 边的权值
    LinkEdge<W>* _next;      // 指向下一个边的指针，用于链式存储

    LinkEdge(const W& w)
        : _srcIndex(-1)      // 默认起点索引为 -1
        , _dstIndex(-1)      // 默认终点索引为 -1
        , _w(w)              // 初始化权值
        , _next(nullptr)     // 指向下一个边的指针初始化为 nullptr
    {}
};
template<class V, class W,  bool Direction = false>
class Graph
{
	typedef LinkEdge<W> Edge;
public:
	
private:
	vector<V> _vertexs;//顶点集合;
	map<V, int> _indexMap;//顶点映射下标;
	vector<Edge*> _tables;// 邻接表
};

初始化：

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);
}

增加边：

void AddEdge(const V& src, const V& dst, const W& w)
{
	size_t srci = GetVertexIndex(src);
	size_t dsti = GetVertexIndex(dst);
	Edge* sd_edge = new Edge(w);
	sd_edge->_srcindex = srci;
	sd_edge->_dstindex = dsti;
	sd_edge->_next = _tables[srci];
	_tables[srci] = sd_edge;
	if (Direction == false)
	{
		Edge* ds_edge = new Edge(w);
		ds_edge->_srcIndex = dstindex;
		ds_edge->_dstIndex = srcindex;
		ds_edge->_next = _tables[dstindex];
		_tables[dstindex] = ds_edge;
	}
}

下面是详细的步骤说明，基于图中有四个顶点 ( A, B, C, D )。我们逐步构建它们的邻接表，同时解释代码的详细逻辑。

假设

  1. 图的顶点集合为：[A, B, C, D]。
  2. 图的边集合为：
    • ( A \to B )（权值 1）
    • ( A \to C )（权值 2）
    • ( B \to D )（权值 3）
    • ( C \to D )（权值 4）
  3. 图是 有向图（即 ( Direction = true )）。

初始状态
邻接表 _tables 是一个数组，初始时，每个顶点的邻接表为空：

_tables: [nullptr, nullptr, nullptr, nullptr]
  • ( _tables[0] ) 表示顶点 ( A ) 的邻接表头。
  • ( _tables[1] ) 表示顶点 ( B ) 的邻接表头。
  • ( _tables[2] ) 表示顶点 ( C ) 的邻接表头。
  • ( _tables[3] ) 表示顶点 ( D ) 的邻接表头。

Step 1: 插入边 ( A \to B )（权值 1）

  1. 调用 AddEdge("A", "B", 1)。

  2. 获取顶点索引：

    • GetVertexIndex("A") 返回 0。
    • GetVertexIndex("B") 返回 1。

  3. 创建新边 sd_edge：

    sd_edge->_srcindex = 0;  // A 的索引
sd_edge->_dstindex = 1;  // B 的索引
sd_edge->_w = 1;         // 权值 1
sd_edge->_next = _tables[0];  // 当前 A 的邻接表头（nullptr）
_tables[0] = sd_edge;         // 更新 A 的邻接表头为 sd_edge

  4. 更新邻接表：

    _tables:
[sd_edge, nullptr, nullptr, nullptr]

    此时，邻接表内容为：

    A: B (权值 1) -> nullptr
B: nullptr
C: nullptr
D: nullptr

Step 2: 插入边 ( A \to C )（权值 2）

  1. 调用 AddEdge("A", "C", 2)。

  2. 获取顶点索引：

    • GetVertexIndex("A") 返回 0。
    • GetVertexIndex("C") 返回 2。

  3. 创建新边 sd_edge：

    sd_edge->_srcindex = 0;  // A 的索引
sd_edge->_dstindex = 2;  // C 的索引
sd_edge->_w = 2;         // 权值 2
sd_edge->_next = _tables[0];  // 当前 A 的邻接表头（指向 B 的边）
_tables[0] = sd_edge;         // 更新 A 的邻接表头为 sd_edge

  4. 更新邻接表：

    _tables:
[sd_edge, nullptr, nullptr, nullptr]

    此时，邻接表内容为：

    A: C (权值 2) -> B (权值 1) -> nullptr
B: nullptr
C: nullptr
D: nullptr

Step 3: 插入边 ( B \to D )（权值 3）

  1. 调用 AddEdge("B", "D", 3)。

  2. 获取顶点索引：

    • GetVertexIndex("B") 返回 1。
    • GetVertexIndex("D") 返回 3。

  3. 创建新边 sd_edge：

    sd_edge->_srcindex = 1;  // B 的索引
sd_edge->_dstindex = 3;  // D 的索引
sd_edge->_w = 3;         // 权值 3
sd_edge->_next = _tables[1];  // 当前 B 的邻接表头（nullptr）
_tables[1] = sd_edge;         // 更新 B 的邻接表头为 sd_edge

  4. 更新邻接表：

    _tables:
[sd_edge, sd_edge, nullptr, nullptr]

    此时，邻接表内容为：

    A: C (权值 2) -> B (权值 1) -> nullptr
B: D (权值 3) -> nullptr
C: nullptr
D: nullptr

Step 4: 插入边 ( C \to D )（权值 4）

  1. 调用 AddEdge("C", "D", 4)。

  2. 获取顶点索引：

    • GetVertexIndex("C") 返回 2。
    • GetVertexIndex("D") 返回 3。

  3. 创建新边 sd_edge：

    sd_edge->_srcindex = 2;  // C 的索引
sd_edge->_dstindex = 3;  // D 的索引
sd_edge->_w = 4;         // 权值 4
sd_edge->_next = _tables[2];  // 当前 C 的邻接表头（nullptr）
_tables[2] = sd_edge;         // 更新 C 的邻接表头为 sd_edge

  4. 更新邻接表：

    _tables:
[sd_edge, sd_edge, sd_edge, nullptr]

    此时，邻接表内容为：

    A: C (权值 2) -> B (权值 1) -> nullptr
B: D (权值 3) -> nullptr
C: D (权值 4) -> nullptr
D: nullptr

最终邻接表

最终的邻接表结构如下：

A: C (权值 2) -> B (权值 1) -> nullptr
B: D (权值 3) -> nullptr
C: D (权值 4) -> nullptr
D: nullptr

邻接表的 _tables 数据结构是：

_tables:
[sd_edge (A->C), sd_edge (B->D), sd_edge (C->D), nullptr]

最后完成打印函数;

void Print()
{
	
	for (size_t i = 0; i < _vertexs.size(); ++i)
	{
		cout << _vertexs[i] << "-" << i << " ";
	}
	cout << endl << endl;
	
	for (int i = 0; i < _tables.size(); i++)
	{
		cout << _vertexs[i] << "[" << i << "]->";
		Edge* cur = _tables[i];
		while (cur)
		{
			cout << _vertexs[cur->_dstindex] << "[" << cur->_dstindex << "]" << cur->_w << "->";
			cur = cur->_next;
		}
		cout << "nullptr" << endl;
	}
}

在这里插入图片描述

完整代码：

#pragma once
#include<vector>
#include<map>

using namespace std;

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 dsti = GetVertexIndex(dst);
			_matrix[srci][dsti] = w;
			if (Direction == false)
			{
				_matrix[dsti][srci] = w;
			}
		}
		void Print()
		{
			// 打印顶点和下标映射关系
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << _vertexs[i] << "-" << i << " ";
			}
			cout << endl << endl;
			cout << "  ";
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << 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 << _matrix[i][j] << " ";
					else
						cout << "#" << " ";
				}
				cout << endl;
			}
			cout << endl << endl;
			// 打印所有的边
			for (size_t i = 0; i < _matrix.size(); ++i)
			{
				for (size_t j = 0; j < _matrix[i].size(); ++j)
				{
					if (i < j && _matrix[i][j] != MAX_W)
					{
						cout << _vertexs[i] << "-" << _vertexs[j] << ":" <<
							_matrix[i][j] << endl;
					}
				}
			}
		}
	private:
		vector<V> _vertexs;//顶点集合;
		map<V, int> _indexMap;//顶点映射下标;
		vector<vector<W>> _matrix;// 存储边集合的矩阵
	};
}
namespace LinkTable
{
	template<class W>
	struct LinkEdge
	{
		int _srcindex;
		int _dstindex;
		W _w;//权值
		LinkEdge<W>* _next;
		LinkEdge(const W& w)
			: _srcindex(-1)
			, _dstindex(-1)
			, _w(w)
			, _next(nullptr)
		{}
	};
	template<class V, class W,  bool Direction = false>
	class Graph
	{
		typedef LinkEdge<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* sd_edge = new Edge(w);
			sd_edge->_srcindex = srci;
			sd_edge->_dstindex = dsti;
			sd_edge->_next = _tables[srci];
			_tables[srci] = sd_edge;
			if (Direction == false)
			{
				Edge* ds_edge = new Edge(w);
				ds_edge->_srcindex = dsti;
				ds_edge->_dstindex = srci;
				ds_edge->_next = _tables[dsti];
				_tables[dsti] = ds_edge;
			}
		}
		void Print()
		{
			
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << _vertexs[i] << "-" << i << " ";
			}
			cout << endl << endl;
			
			for (int i = 0; i < _tables.size(); i++)
			{
				cout << _vertexs[i] << "[" << i << "]->";
				Edge* cur = _tables[i];
				while (cur)
				{
					cout << _vertexs[cur->_dstindex] << "[" << cur->_dstindex << "]" << cur->_w << "->";
					cur = cur->_next;
				}
				cout << "nullptr" << endl;
			}
		}
	private:
		vector<V> _vertexs;//顶点集合;
		map<V, int> _indexMap;//顶点映射下标;
		vector<Edge*> _tables;// 邻接表
	};
}
void TestGraph()
{
	matrix::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();
}
void TestGraph2()
{
	string a[] = { "张三", "李四", "王五", "赵六" };
	LinkTable::Graph<string, int> g1(a, 4);
	g1.AddEdge("张三", "李四", 100);
	g1.AddEdge("张三", "王五", 200);
	g1.AddEdge("王五", "赵六", 30);
	g1.Print();
}

http://www.kler.cn/a/451389.html

相关文章：

  • ROM修改进阶教程------修改刷机包init.rc 自启用户自定义脚本的一些基本操作 代码格式与注意事项
  • 在 Java 项目中集成和使用 dl4j 实现通过扫描图片识别快递单信息
  • 快速解决oracle 11g中exp无法导出空表的问题
  • 单片机：实现数码管动态显示（0~99999999）74hc138驱动（附带源码）
  • 活着就好20241225
  • Yolo11改进策略：Head改进|DynamicHead，利用注意力机制统一目标检测头部|即插即用
  • node.js的异步工作之---回调函数与回调地狱
  • 用Python在Excel工作表中创建、修改及删除表格区域
  • C#（事件）2
  • 第79期 | GPTSecurity周报
  • 《智启新材：人工智能重塑分子结构设计蓝图》
  • Krita安装krita-ai-diffusion工具搭建comfyui报错没有ComfyUI_IPAdapter_plus解决办法
  • [Vim][常用操作整理]详细讲解
  • 音视频学习（二十七）：SRT协议
  • Excel 列名称转换问题 Swift 解答
  • LeetCode 343.整数拆分
  • #渗透测试#漏洞挖掘#红蓝攻防#护网#sql注入介绍11基于XML的SQL注入（XML-Based SQL Injection）
  • 考前96天 学习巩固 计算机、数学、英语
  • leetcode 3132. 找出与数组相加的整数 II 中等
  • MySQL追梦旅途之慢查询分析工具mysqldumpslow和pt-query-digest
  • Maximum Crossings (Hard Version)最大交叉次数（困难版本）
  • ROS1入门教程5：简单行为处理
  • 【es6复习笔记】生成器（11）
  • C++-------回溯最大最小算法
  • Word表格批量添加题注代码
  • 反汇编一个简单的C程序