数据结构与算法c++如何解决这个问题

#include <iostream>
using namespace std;

typedef char VerTexType;                      //假设顶点的数据类型为字符型 
typedef int ArcType;   
#define MVNum 100                           //最大顶点数
#define MaxInt 32767                        //表示极大值，即∞

//----------------图的邻接矩阵---------------------
typedef struct{ 
    VerTexType vexs[MVNum];                    //顶点表 
    ArcType arcs[MVNum][MVNum];              //邻接矩阵 
    int vexnum,arcnum;                        //图的当前点数和边数 
}AMGraph;

//辅助数组Edges的定义
struct{
    VerTexType Head;                        //边的始点
    VerTexType Tail;                        //边的终点
    ArcType lowcost;                        //边上的权值
}Edge[(MVNum * (MVNum - 1)) / 2];

int Vexset[MVNum];                            //辅助数组Vexset的定义

int LocateVex(AMGraph G , VerTexType v){
    //确定点v在G中的位置
    for(int i = 0; i < G.vexnum; ++i)
        if(G.vexs[i] == v)
            return i;
        return -1;
}//LocateVex

void CreateUDN(AMGraph &G){ 
    //采用邻接矩阵表示法，创建无向网G 
    int i , j , k;
    cout <<"请输入总顶点数，总边数，以空格隔开:";
    cin >> G.vexnum >> G.arcnum;                        //输入总顶点数，总边数
    cout << endl;
    
    cout << "输入点的名称，如a" << endl;

    for(i = 0; i < G.vexnum; ++i){   
        cout << "请输入第" << (i+1) << "个点的名称:";
        cin >> G.vexs[i];                                //依次输入点的信息 
    }
    cout << endl;
    for(i = 0; i < G.vexnum; ++i)                        //初始化邻接矩阵，边的权值均置为极大值MaxInt 
        for(j = 0; j < G.vexnum; ++j) 
            G.arcs[i][j] = MaxInt; 
    cout << "输入边依附的顶点及权值，如a b 6" << endl;
    for(k = 0; k < G.arcnum;++k){                        //构造邻接矩阵 
        VerTexType v1 , v2;
        ArcType w;
        cout << "请输入第" << (k + 1) << "条边依附的顶点及权值:";
        cin >> v1 >> v2 >> w;                           //输入一条边依附的顶点及权值
        i = LocateVex(G, v1);  j = LocateVex(G, v2);    //确定v1和v2在G中的位置，即顶点数组的下标 
        G.arcs[i][j] = w;                                //边<v1, v2>的权值置为w 
        G.arcs[j][i] = G.arcs[i][j];                    //置<v1, v2>的对称边<v2, v1>的权值为w 
        Edge[k].lowcost = w;
        Edge[k].Head = v1;
        Edge[k].Tail = v2;
    }//for
}//CreateUDN

用图论解决一个问题：利用我给出的代码构造一个无向网，网中各结点除了有自身信息和指针域外，还有一个值，该值为工程量。要求用户再输入网中各节点的工程量，然后输入起点和所有边的总权值应大于的一个数。遍历无向图，当遍历过程中边的总权值大于了用户输入的那个数，停止遍历。经过多次遍历找出遍历过程中点的总工程量最小的那条路径并输出

在你代码基础上修改：两个步骤：
上结果：

上代码：

#include <iostream>
#include <climits>  
using namespace std;
typedef char VerTexType;   //假设顶点的数据类型为字符型 
typedef int ArcType;     
#define MVNum 100          //最大顶点数
#define MaxInt 32767       //表示极大值,即∞
 //定义变量
int path_sum = 0;       //记录路径总工程量 
int min_path_sum = INT_MAX;    //使用INT_MAX替代MAXINT    //记录最小路径总工程量
int visit_vex[MVNum];      //记录已访问的节点


//图的邻接矩阵                   
typedef struct{          
    VerTexType vexs[MVNum];    //顶点表
    ArcType arcs[MVNum][MVNum]; //邻接矩阵
    int vexnum,arcnum;         //图的当前点数和边数
    int eng_amount[MVNum];     //节点工程量
}AMGraph; 
//辅助数组Edges的定义
struct{                    
    VerTexType Head;         //边的始点
    VerTexType Tail;         //边的终点
    ArcType lowcost;         //边上的权值
}Edge[(MVNum * (MVNum - 1)) / 2]; 
int Vexset[MVNum];         //辅助数组Vexset的定义 
int LocateVex(AMGraph G , VerTexType v){
    //确定点v在G中的位置
    for(int i = 0; i < G.vexnum; ++i)
        if(G.vexs[i] == v)
            return i;
        return -1;
}//LocateVex 
void CreateUDN(AMGraph &G){
    //采用邻接矩阵表示法,创建无向网G
    int i , j , k;
    cout<<"请输入总顶点数,总边数,以空格隔开:";
    cin >> G.vexnum >> G.arcnum;  //输入总顶点数,总边数
    cout << endl;
    cout << "输入点的名称,如a" << endl;
    for(i = 0; i < G.vexnum; ++i){  
        cout << "请输入第" << (i+1) << "个点的名称:";
        cin >> G.vexs[i];       //依次输入点的信息
    }
    cout << endl;
    //初始化邻接矩阵,边的权值均置为极大值MaxInt 
    for(i = 0; i < G.vexnum; ++i)
        for(j = 0; j < G.vexnum; ++j)
            G.arcs[i][j] = MaxInt; 
    cout << "输入边依附的顶点及权值,如a b 6" << endl;
    for(k = 0; k < G.arcnum;++k){    //构造邻接矩阵                      
        VerTexType v1 , v2;
        ArcType w;
        cout << "请输入第" << (k + 1)<<"条边依附的顶点及权值:";
        cin >> v1 >> v2 >> w;        //输入一条边依附的顶点及权值
        i = LocateVex(G, v1); 
        j = LocateVex(G, v2);       //确定v1和v2在G中的位置,即顶点数组的下标
        G.arcs[i][j] = w;           //边<v1, v2>的权值置为w 
        G.arcs[j][i] = G.arcs[i][j]; //置<v1, v2>的对称边<v2, v1>的权值为w 
        Edge[k].lowcost = w;
        Edge[k].Head = v1;
        Edge[k].Tail = v2;
    }//for 
}//CreateUDN

AMGraph G;  

VerTexType start;  
int sum_value; 
//DFS遍历找最小路径                       
void DFS(int v) {
        visit_vex[v] = 1;
        path_sum += G.eng_amount[v];   //路径上节点工程量相加
    
        //到达叶子节点或者边总权值大于输入值,比较当前路径总工程量
        if(v == start || path_sum > sum_value) {  
            min_path_sum = min(min_path_sum, path_sum); 
        }
      
        //递归遍历相邻节点
        for(int w=0; w<G.vexnum; w++) {
            if(visit_vex[w] == 0 && G.arcs[v][w] != INT_MAX && w != v) {  
                DFS(w);    
            }
        }
        path_sum -= G.eng_amount[v];   //回退,路径总工程量减去当前节点的工程量
        visit_vex[v] = 0;
}
int main() {
    
    CreateUDN(G);         //构造无向网
  //输入每个节点的工程量        
    cout << "输入每个节点的工程量:" << endl;
    for(int i=0; i<G.vexnum; i++) {
        cout << "请输入第" << i+1 << "个节点的工程量:";
        cin >> G.eng_amount[i]; 
    }
    //输入起点和边总权值大于的数    
    VerTexType start;
    cout << "请输入起点:";
    cin >> start;
    int sum_value;
    cout << "请输入边总权值大于的数:";
    cin >> sum_value; 
   

    for(int i=0; i<G.vexnum; i++) visit_vex[i] = 0;
  
    
  
    DFS(LocateVex(G, start)); 
         //从起点开始深度优先遍历 
    cout << "最小路径总工程量为:" << min_path_sum << endl;  
}

#include <iostream>
#include <vector>
using namespace std;

typedef char VerTexType;
typedef int ArcType;
#define MVNum 100
#define MaxInt 32767

typedef struct {
    VerTexType vexs[MVNum];
    ArcType arcs[MVNum][MVNum];
    int vexnum, arcnum;
} AMGraph;

struct Edge {
    VerTexType Head;
    VerTexType Tail;
    ArcType lowcost;
};

int Vexset[MVNum];

int LocateVex(AMGraph G, VerTexType v) {
    for (int i = 0; i < G.vexnum; ++i)
        if (G.vexs[i] == v)
            return i;
    return -1;
}

void CreateUDN(AMGraph& G) {
    int i, j, k;
    cout << "请输入总顶点数，总边数，以空格隔开:";
    cin >> G.vexnum >> G.arcnum;
    cout << endl;

    cout << "输入点的名称，如a" << endl;

    for (i = 0; i < G.vexnum; ++i) {
        cout << "请输入第" << (i + 1) << "个点的名称:";
        cin >> G.vexs[i];
    }
    cout << endl;
    for (i = 0; i < G.vexnum; ++i)
        for (j = 0; j < G.vexnum; ++j)
            G.arcs[i][j] = MaxInt;
    cout << "输入边依附的顶点及权值，如a b 6" << endl;
    for (k = 0; k < G.arcnum; ++k) {
        VerTexType v1, v2;
        ArcType w;
        cout << "请输入第" << (k + 1) << "条边依附的顶点及权值:";
        cin >> v1 >> v2 >> w;
        i = LocateVex(G, v1);  j = LocateVex(G, v2);
        G.arcs[i][j] = w;
        G.arcs[j][i] = G.arcs[i][j];
        Edge[k].lowcost = w;
        Edge[k].Head = v1;
        Edge[k].Tail = v2;
    }
}

void DFS(AMGraph G, int start, ArcType limit, vector<VerTexType>& path, ArcType& minCost, vector<VerTexType>& minPath) {
    path.push_back(G.vexs[start]);
    if (limit <= 0 || path.size() >= G.vexnum) {
        if (limit <= 0 && minCost > 0 && path.size() == G.vexnum) {
            minCost = limit;
            minPath = path;
        }
        return;
    }
    for (int i = 0; i < G.vexnum; ++i) {
        if (G.arcs[start][i] != MaxInt && find(path.begin(), path.end(), G.vexs[i]) == path.end()) {
            ArcType newLimit = limit - G.arcs[start][i];
            if (newLimit > 0 && (minCost <= 0 || newLimit < minCost)) {
                DFS(G, i, newLimit, path, minCost, minPath);
            }
        }
    }
    path.pop_back();
}

void findMinCostPath(AMGraph G, ArcType limit) {
    vector<VerTexType> path;
    vector<VerTexType> minPath;
    ArcType minCost = -1;

    for (int i = 0; i < G.vexnum; ++i) {
        DFS(G, i, limit, path, minCost, minPath);
    }

    if (minCost > 0) {
        cout << "最小总工程量路径为：";
        for (int i = 0; i < minPath.size(); ++i) {
            cout << minPath[i];
            if (i != minPath.size() - 1)
                cout << " -> ";
        }
        cout << endl;
    }
    else {
        cout << "找不到满足条件的路径" << endl;
    }
}

int main() {
    AMGraph graph;
    CreateUDN(graph);

    ArcType limit;
    cout << "请输入边的总权值应大于的一个数：";
    cin >> limit;

    findMinCostPath(graph, limit);

    return 0;
}

答案参考ChapGPT Plus . 希望对你有帮助
这段代码是用来创建一个无向网的邻接矩阵表示的数据结构，并且实现了一些辅助函数和结构体来辅助操作。

要解决你描述的问题，可以在代码中添加以下函数：

// 遍历无向图，找出遍历过程中点的总工程量最小的路径
void TraverseGraph(AMGraph G, int start, int targetWeight) {
    int currentWeight = 0; // 当前遍历路径的权值总和
    int minWeight = MaxInt; // 最小权值总和
    vector<VerTexType> minPath; // 最小权值路径
    vector<VerTexType> currentPath; // 当前遍历路径

    // 初始化辅助数组Vexset
    for (int i = 0; i < G.vexnum; ++i)
        Vexset[i] = 0;

    // 从起点开始遍历
    TraverseDFS(G, start, targetWeight, currentWeight, minWeight, minPath, currentPath);
    
    // 输出最小权值路径
    if (minWeight < MaxInt) {
        cout << "最小权值路径为:";
        for (int i = 0; i < minPath.size(); ++i)
            cout << minPath[i] << " ";
        cout << endl;
        cout << "总工程量为:" << minWeight << endl;
    } else {
        cout << "没有找到满足条件的路径" << endl;
    }
}

// 深度优先搜索遍历图
void TraverseDFS(AMGraph G, int v, int targetWeight, int currentWeight, int &minWeight, vector<VerTexType> &minPath, vector<VerTexType> &currentPath) {
    currentPath.push_back(G.vexs[v]);
    Vexset[v] = 1;
    currentWeight += G.vexs[v].工程量; // 假设工程量的值保存在结点的成员变量"工程量"中

    // 达到目标权值时更新最小权值路径和总工程量
    if (currentWeight > targetWeight && currentWeight < minWeight) {
        minWeight = currentWeight;
        minPath = currentPath;
    }

    // 继续深度优先搜索
    for (int i = 0; i < G.vexnum; ++i) {
        if (G.arcs[v][i] < MaxInt && Vexset[i] == 0) {
            TraverseDFS(G, i, targetWeight, currentWeight, minWeight, minPath, currentPath);
        }
    }

    // 回溯，恢复状态
    currentPath.pop_back();
    Vexset[v] = 0;
    currentWeight -= G.vexs[v].工程量;
}

然后，在主函数中调用这个函数来解决问题：

int main() {
    AMGraph G;
    CreateUDN(G);
    int targetWeight;
    cout << "请输入边的总权值应大于的一个数:";
    cin >> targetWeight;
    int start;
    cout << "请输入起点:";
    cin >> start;
    TraverseGraph(G, start, targetWeight);
    return 0;
}

这样，

用户就可以输入无向网的节点信息和工程量，并输入起点和总权值的阈值，程序会输出在遍历过程中点的总工程量最小的路径。

引用gpt回答 有帮助的采纳一下哟

#include <iostream>
using namespace std;

typedef char VerTexType;  
typedef int ArcType;    
#define MVNum 100           
#define MaxInt 32767        

typedef struct{
    VerTexType vexs[MVNum];    
    ArcType arcs[MVNum][MVNum];  
    int vexnum,arcnum;          
}AMGraph;

struct{
    VerTexType Head;          
    VerTexType Tail;          
    ArcType lowcost;           
}Edge[(MVNum * (MVNum - 1)) / 2];  

int Vexset[MVNum];        

int LocateVex(AMGraph G , VerTexType v){
    //确定点v在G中的位置
    for(int i = 0; i < G.vexnum; ++i)
        if(G.vexs[i] == v)
            return i;  
        return -1;  
}

void CreateUDN(AMGraph &G){
    //创建无向网G
    int i , j , k;
    cout << "请输入总顶点数,总边数,以空格隔开:";
    cin >> G.vexnum >> G.arcnum;  

    cout << "输入点的名称,如a" << endl;
    for(i = 0; i < G.vexnum; ++i){         
        cout << "请输入第" << (i+1) << "个点的名称:";  
        cin >> G.vexs[i];  
    }  

    for(i = 0; i < G.vexnum; ++i)    
        for(j = 0; j < G.vexnum; ++j)
            G.arcs[i][j] = MaxInt;  

    cout << "输入边依附的顶点及权值,如a b 6" << endl;

    for(k = 0; k < G.arcnum;++k){      
        VerTexType v1 , v2;  
        ArcType w;
        cin >> v1 >> v2 >> w;         
        i = LocateVex(G, v1);  
        j = LocateVex(G, v2);    
        G.arcs[i][j] = w;          
        G.arcs[j][i] = G.arcs[i][j]; 
        Edge[k].lowcost = w;
        Edge[k].Head = v1;
        Edge[k].Tail = v2;
    }
}  
int main(){
    AMGraph G;
    CreateUDN(G);  //构造无向网G

    int sum;
    cout << "请输入边的总权值应大于的数:";
    cin >> sum;

    int min_sum = MaxInt;    //最小路径总权值
    int path[MVNum];        //记录最小路径
    int cnt = 0;            //记录路径中已有的点数

    cout << "请输入起点:";
    VerTexType start;
    cin >> start;
    int v = LocateVex(G, start);  //确定起点在G中的位置

    path[cnt++] = v;           //将起点加入路径
    int total = G.vexs[v].value; //路径总权值初始化为起点权值  

    bool *visited = new bool[G.vexnum];  //创建访问标记数组 
    for(int i = 0; i < G.vexnum; i++)
        visited[i] = false;
    visited[v] = true;                  //标记起点已访问

    while(cnt < G.vexnum){
        int j;
        for(j = 0; j < G.vexnum; j++)    //从起点出发,找第一个邻接未访问顶点
            if(G.arcs[v][j] != MaxInt && !visited[j])
                break; 
        if(j == G.vexnum) break;        //若找不到,则跳出循环
        v = j;                          //转到第一个邻接未访问顶点      
        visited[v] = true;              //标记该顶点已访问
        total += G.vexs[v].value;      //路径总权值增加该顶点权值
        path[cnt++] = v;               //将该顶点加入路径    

        if(total > sum) break;         //当路径总权值大于输入值sum时,跳出循环
    }

    if(total < min_sum ){             //比较当前路径与最短路径总权值
        min_sum = total;
        for(int i=0; i<cnt; i++)      //记录最短路径的顶点
            cout << G.vexs[path[i]] << " ";
    } 
    cout << endl;
    delete []visited;
}

这段代码实现了一个邻接矩阵存储的无向网的创建，下面按照注释，简要介绍一下每一个函数的实现：

1. typedef char VerTexType：定义了顶点的数据类型为字符型，即每个顶点用一个字符来表示。

2. typedef int ArcType：定义了边的权值类型为整型。

3. #define MVNum 100：定义了最大顶点数为 100。

4. #define MaxInt 32767：定义了一个极大值常量，用于初始化边的权重。

5. typedef struct {...} AMGraph：定义了一个邻接矩阵表示的无向网，包含顶点表和邻接矩阵两个部分，其中 vexnum 表示当前图中的顶点数，arcnum 表示当前图中的边数。

6. struct {...} Edge[(MVNum * (MVNum - 1)) / 2]：定义了辅助数组 Edge，用于在 Prim 算法的实现过程中存储临时的边数据，后面介绍 Prim 算法时会用到。

7. int Vexset[MVNum]：定义了辅助数组 Vexset，用于在 Kruskal 算法的实现过程中辅助判断两个顶点是否处于同一个连通分量中，后面介绍 Kruskal 算法时会用到。

8. int LocateVex(AMGraph G, VerTexType v)：该函数用于定位某一顶点在图中的位置，输入参数为图 G 和顶点名称 v，返回值为整型位置下标。

9. void CreateUDN(AMGraph &G)：该函数用于创建一个无向网图，首先输入总顶点数和总边数，然后依次输入每个顶点的名称和每条边的的起点、终点、权重，最后构造出相应的邻接矩阵。需要注意的是，该函数的建立方式与输入方式需要根据实际数据来定制，比如输入方式可以改为从文件中读取等。

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7670937
• 这篇博客你也可以参考下：指针知识，用实参做参数，实现最小值，输入三个数到数组中，找出数组中的最小值
• 除此之外, 这篇博客: 指针和数组试题解析（重置版）中的 小编，在这里想说一下，c语言的最后一节 C预处理，可能还需要一些时间，因为小编，昨天才下载了虚拟机 和 linux 系统，还没开始安装。所以无法着手写，因为 C预处理，vs2013很难表达，也就意味可能会讲不清楚。所以这篇文章可能需要点时间，再加上小编初期的文章，是没有排版的（而且可能有些错误，请大家以重置版为准），所以这几天我就把这些重新写。有兴趣的朋友可以看看。（ps：如果哪一天没有更新，意味着小编正在努力学习，为了能给大家呈现一片详细好懂的文章。） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

•  
   
   

• 您还可以看一下 姚海陆老师的中小型企业创业初期选择、选购域名、虚拟主机、服务器攻略大全课程中的 03-如何在选购服务器时规避风险节省成本小节, 巩固相关知识点
  

参考下：

#include <iostream>  
#include <vector>  
  
using namespace std;  
  
typedef char VerTexType;                      // 假设顶点的数据类型为字符型   
typedef int ArcType;     
#define MVNum 100                           // 最大顶点数  
#define MaxInt 32767                        // 表示极大值，即∞  
  
// ----------------- 图的邻接矩阵 -----------------  
typedef struct {  
    VerTexType vexs[MVNum];                    // 顶点表   
    ArcType arcs[MVNum][MVNum];              // 邻接矩阵   
    int vexnum, arcnum;                        // 图的当前点数和边数   
} AMGraph;  
  
// 辅助数组Edges的定义  
struct {  
    VerTexType Head;                        // 边的始点  
    VerTexType Tail;                        // 边的终点  
    ArcType lowcost;                        // 边上的权值  
} Edge[(MVNum * (MVNum - 1)) / 2];  
  
int Vexset[MVNum];                            // 辅助数组Vexset的定义  
  
int LocateVex(AMGraph G, VerTexType v) {  
    // 确定点v在G中的位置  
    for (int i = 0; i < G.vexnum; ++i) {  
        if (G.vexs[i] == v) {  
            return i;  
        }  
    }  
    return -1;  
}// LocateVex  
  
void CreateUDN(AMGraph &G) {  
    // 采用邻接矩阵表示法，创建无向网G   
    int i, j, k;  
    cout << "请输入总顶点数，总边数，以空格隔开:";  
    cin >> G.vexnum >> G.arcnum;                        // 输入总顶点数，总边数  
    cout << endl;  
  
    cout << "输入点的名称，如a" << endl;  
  
    for (i = 0; i < G.vexnum; ++i) {   // 输入点的信息   
        cout << "请输入第" << (i + 1) << "个点的名称:";  
        cin >> G.vexs[i];  
    }  
    cout << endl;  
    for (i = 0; i < G.vexnum; ++i) {              // 初始化邻接矩阵，边的权值均置为极大值MaxInt   
        for (j = 0; j < G.vexnum; ++j) {  
            G.arcs[i][j] = MaxInt;  
        }  
    }  
    cout << "输入边依附的顶点及权值，如a b 6" << endl;  
    for (k = 0; k < G.arcnum; ++k) {              // 构造邻接矩阵   
        VerTexType v1, v2;  
        ArcType w;  
        cout << "请输入第" << (k + 1) << "条边依附的顶点及权值:";  
        cin >> v1 >> v2 >> w;                   // 输入一条边依附的顶点及权值  
        int i = LocateVex(G, v1);  int j = LocateVex(G, v2);    // 确定v1和v2在G中的位置，即顶点数组的下标   
        G.arcs[i][j] = w;                        // 边<v1, v2>的权值置为w   
        G.arcs[j][i] = G.arcs[i][j];  
    }  
}  
  
void DFS(AMGraph G, VerTexType v, int cost) {  
    // 深度优先搜索遍历无向图G，返回路径总权值最小的路径上的顶点集合PathSet  
    static vector<VerTexType> PathSet;           // PathSet为静态变量，用于存储路径上的顶点集合   
    static vector<int> CostSet;                  // CostSet为静态变量，用于存储路径上的权值之和   
    static bool visited[MVNum] = { false };      // visited数组用于记录每个顶点是否被访问过   
    visited[v] = true;                           // 将当前顶点标记为已访问过

#如有帮助，恭请采纳