【c++】【笔记】 <判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简...

false_554

储存结构采用邻接矩阵，详细可以看我上一个帖子~

思路：递归判断与当前顶点i的相邻【顶点w到顶点j是否存在一条长度为k-1的路径】

详细代码：

//入口
template<class  T>
bool Exist_path_len(MatrixGraph<T> &undigraph, int i, int j, int len) {
    for (int i = 1; i <= undigraph.vertex_num; i++) {
        visit[i] = 0;
    }
    return exist_path_len(undigraph,i, j, len);
}

template<class  T>
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[i] = 1;//以本次运行为起点的递归该点都为已访问顶点（防止存在环）
        for (int w = 1; w <= undigraph.vertex_num; w++) {
            if (visit[w] == 0 && undigraph.vertex_[w] != -1 && undigraph.EdgeMatrix[i][w] != 0) {
                //如果该顶点不构成环
                if (!visit[w]) {
                    if (exist_path_len(undigraph, w, j, len - 1))return true;//如果w，j之间存在一条长度为k-1的路径j
                }
            }
        }
        visit[i] = 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][2] = 1;
    undigraph.EdgeMatrix[2][1] = 1;
    undigraph.EdgeMatrix[1][3] = 1;
    undigraph.EdgeMatrix[3][1] = 1;
    undigraph.EdgeMatrix[1][4] = 1;
    undigraph.EdgeMatrix[4][1] = 1;
    undigraph.EdgeMatrix[2][3] = 1;
    undigraph.EdgeMatrix[3][2] = 1;
    undigraph.EdgeMatrix[4][6] = 1;
    undigraph.EdgeMatrix[6][4] = 1;
    undigraph.EdgeMatrix[6][8] = 1;
    undigraph.EdgeMatrix[8][6] = 1;
    undigraph.EdgeMatrix[5][8] = 1;
    undigraph.EdgeMatrix[8][5] = 1;
    undigraph.EdgeMatrix[5][9] = 1;
    undigraph.EdgeMatrix[9][5] = 1;
    undigraph.EdgeMatrix[3][5] = 1;
    undigraph.EdgeMatrix[5][3] = 1;
    undigraph.EdgeMatrix[3][7] = 1;
    undigraph.EdgeMatrix[7][3] = 1;
    undigraph.EdgeMatrix[3][10] = 1;
    undigraph.EdgeMatrix[10][3] = 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;
    }

生成的无向图：


运行结果：


滚去继续码下一个算法~

AZ2020

感谢分享，一起学习总结

tianruo1987

数据结构，已经还给老师了。

false_554

tianruo1987 发表于 2020-11-25 17:19
数据结构，已经还给老师了。

哈哈那就一起review一遍

gms

感谢分享，先收藏，C++基础太弱还在自学中，这个有些代码都不懂了

false_554

gms 发表于 2020-11-25 17:59
感谢分享，先收藏，C++基础太弱还在自学中，这个有些代码都不懂了

去补一下c++模板类的用法就行啦