重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
C++--数据结构--图的相关概念及模拟实现--高阶0712-创新互联
1. 图的基本概念
当前文章：C++--数据结构--图的相关概念及模拟实现--高阶0712-创新互联
链接分享：http://cqcxhl.cn/article/dddcci.html
图（G）是由顶点（V）集合及顶点间的关系（边 E）组成的一种数据结构；
顶点：图中的结点，第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;
} 测试代码及打印结果
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://cqcxhl.cn/article/dddcci.html