【c++】【笔记】 <判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简...
储存结构采用邻接矩阵，详细可以看我上一个帖子~思路：递归判断与当前顶点i的相邻【顶点w到顶点j是否存在一条长度为k-1的路径】
详细代码：
```
//入口
template<classT>
bool Exist_path_len(MatrixGraph<T> &undigraph, int i, int j, int len) {
for (int i = 1; i <= undigraph.vertex_num; i++) {
visit = 0;
}
return exist_path_len(undigraph,i, j, len);
}
template<classT>
bool exist_path_len(MatrixGraph<T> &undigraph, int i, int j, int len) {
if ((i == j) && len == 0)return true; //i到i长为0的路径
else if(len>0){
visit = 1;//以本次运行为起点的递归该点都为已访问顶点（防止存在环）
for (int w = 1; w <= undigraph.vertex_num; w++) {
if (visit == 0 && undigraph.vertex_ != -1 && undigraph.EdgeMatrix != 0) {
//如果该顶点不构成环
if (!visit) {
if (exist_path_len(undigraph, w, j, len - 1))return true;//如果w，j之间存在一条长度为k-1的路径j
}
}
}
visit = 0;//允许被访问过的顶点出现在另一路径中 (本次递归到终点则修改访问状态)
}
return false;
}
```
运行主程序：
```
int a[] = { 10,2,5,3,4,6,8,11,34,1,1 };
MatrixGraph<int> undigraph = CreatUndigraph<int>(a);
//生成邻接矩阵
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
undigraph.EdgeMatrix = 1;
cout << endl;
int i = 0;
int j, k;
while (i != -1) {
cout << "输入路径长度：";
cin >> k;
cout << "输入顶点1：";
cin >> i;
cout << "输入顶点2：";
cin >> j;
cout << i << "与" << j << "中是否存在一条长为" << k << "的简单路径：" << Exist_path_len(undigraph, i, j, k) << endl;
cout << endl;
}
```
生成的无向图：
运行结果：
滚去继续码下一个算法~
感谢分享，一起学习总结 数据结构，已经还给老师了。 tianruo1987 发表于 2020-11-25 17:19
数据结构，已经还给老师了。
哈哈那就一起review一遍{:301_978:} 感谢分享，先收藏，C++基础太弱还在自学中，这个有些代码都不懂了 gms 发表于 2020-11-25 17:59
感谢分享，先收藏，C++基础太弱还在自学中，这个有些代码都不懂了
去补一下c++模板类的用法就行啦
页:
[1]