m0_73634697 2022-12-16 22:22 采纳率: 33.3%
浏览 70
已结题

利用c++解决图论问题

1、利用随机数原理,随机产生一个二维数组A(30*30),其中对角线元素为零,剩余元素中的50%是∞,其余元素的值为大于0的随机数。
2、将上述二维数组作为图的邻接矩阵,以该数组作为输入,创建一个图形结构,该图使用邻接表作为存储结构。
3、利用DFS或者BFS算法遍历该图,找到图中权值最小的边。
4、设计一个基于Floyd的最短路径算法,计算所有顶点之间的最短路径。

  • 写回答

1条回答 默认 最新

  • ChatGPTᴼᴾᴱᴺᴬᴵ 2022-12-17 07:54
    关注

    由于题太长导致ChatGPT试了好几次才全部答完,可能答案不正确
    1、利用随机数原理,随机产生一个二维数组A(30*30),其中对角线元素为零,剩余元素中的50%是∞,其余元素的值为大于0的随机数。

    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    const int N = 30;            // 定义数组大小为30*30
    const int INF = 0x3f3f3f3f; // 定义∞的值
    
    int main()
    {
        srand(time(NULL)); // 设置随机数种子
        int A[N][N];       // 定义二维数组A
        for (int i = 0; i < N; i++)
        { // 遍历二维数组A
            for (int j = 0; j < N; j++)
            {
                if (i == j)
                { // 对角线元素为零
                    A[i][j] = 0;
                }
                else if (rand() % 2 == 0)
                { // 50%的概率为∞
                    A[i][j] = INF;
                }
                else
                { // 剩余元素的值为大于0的随机数
                    A[i][j] = rand() % 100 + 1;
                }
            }
        }
        // 输出二维数组A
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cout << A[i][j] << " ";
            }
            cout << endl;
        }
        return 0;
    }
    

    2、将上述二维数组作为图的邻接矩阵,以该数组作为输入,创建一个图形结构,该图使用邻接表作为存储结构。

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    const int INF = 0x3f3f3f3f; // 定义∞的值
    
    const int N = 30; // 定义数组大小为30*30
    
    struct Edge
    {                    // 定义边的结构体
        int to, weight; // to表示边的终点,weight表示边的权值
    };
    
    vector<Edge> adj[N]; // 定义邻接表
    
    void addEdge(int u, int v, int w)
    {                              // 添加边的函数
        adj[u].push_back({v, w}); // 将边(u, v)加入邻接表
    }
    
    int main()
    {
        int A[N][N] = {// 定义二维数组A(邻接矩阵)
                       {0, 2, 6, 4, INF, INF, INF},
                       {INF, 0, 3, INF, 2, INF, INF},
                       {INF, INF, 0, INF, INF, 5, INF},
                       {INF, 1, 5, 0, INF, INF, INF},
                       {INF, INF, INF, 3, 0, 2, 6},
                       {INF, INF, INF, INF, INF, 0, 3},
                       {INF, INF, INF, INF, INF, INF, 0}};
        for (int i = 0; i < N; i++)
        { // 遍历二维数组A
            for (int j = 0; j < N; j++)
            {
                if (A[i][j] != INF)
                {                            // 如果A[i][j]不是∞,说明存在边(i, j)
                    addEdge(i, j, A[i][j]); // 将边(i, j)加入邻接表
                    for (int i = 0; i < N; i++)
                    { // 遍历二维数组A
                        for (int j = 0; j < N; j++)
                        {
                            cout << A[i][j] << " "; // 输出A[i][j]
                        }
                        cout << endl; // 输出换行符
                    }
                }
            }
        }
        return 0;
    }
    

    3、利用DFS或者BFS算法遍历该图,找到图中权值最小的边。首先是DFS。

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    const int INF = 0x3f3f3f3f; // 定义∞的值
    
    const int N = 30; // 定义数组大小为30*30
    
    struct Edge
    {                    // 定义边的结构体
        int to, weight; // to表示边的终点,weight表示边的权值
    };
    
    vector<Edge> adj[N]; // 定义邻接表
    
    void addEdge(int u, int v, int w)
    {                              // 添加边的函数
        adj[u].push_back({v, w}); // 将边(u, v)加入邻接表
    }
    
    void dfs(int u, vector<bool> &visited, int &min_weight)
    {                       // 定义DFS遍历的函数
        visited[u] = true; // 标记顶点u为已访问
        for (const Edge &e : adj[u])
        { // 遍历顶点u的所有出边
            int v = e.to;
            int w = e.weight;
            if (!visited[v])
            {                                     // 如果顶点v未被访问过
                min_weight = min(min_weight, w); // 更新最小边权值
                dfs(v, visited, min_weight);     // 递归调用DFS遍历
            }
        }
    }
    
    int main()
    {
        int A[N][N] = {// 定义二维数组A(邻接矩阵)
                       {0, 2, 6, 4, INF, INF, INF},
                       {INF, 0, 3, INF, 2, INF, INF},
                       {INF, INF, 0, INF, INF, 5, INF},
                       {INF, 1, 5, 0, INF, INF, INF},
                       {INF, INF, INF, 3, 0, 2, 6},
                       {INF, INF, INF, INF, INF, 0, 3},
                       {INF, INF, INF, INF, INF, INF, 0}};
        for (int i = 0; i < N; i++)
        { // 遍历二维数组A
            for (int j = 0; j < N; j++)
            {
                if (A[i][j] != INF)
                {                            // 如果A[i][j]不是∞,说明存在边(i, j)
                    addEdge(i, j, A[i][j]); // 将边(i, j)加入邻接表
                }
            }
        }
        int min_weight = INF;                              // 定义最小边权值初始值为∞
        vector<bool> visited(N, false);                      // 定义访问数组,初始值全部为false
        dfs(0, visited, min_weight);                      // 从顶点0开始遍历图
        cout << "Minimum weight: " << min_weight << endl; // 输出最小边权值
        return 0;
    }
    

    其次是BFS

    #include <iostream>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    const int INF = 0x3f3f3f3f; // 定义∞的值
    
    const int N = 30; // 定义数组大小为30*30
    
    struct Edge
    {                    // 定义边的结构体
        int to, weight; // to表示边的终点,weight表示边的权值
    };
    
    vector<Edge> adj[N]; // 定义邻接表
    
    void addEdge(int u, int v, int w)
    {                              // 添加边的函数
        adj[u].push_back({v, w}); // 将边(u, v)加入邻接表
    }
    
    void bfs(int u, int &min_weight)
    {                                    // 定义BFS遍历的函数
        queue<int> q;                    // 定义队列
        vector<bool> visited(N, false); // 定义访问数组,初始值全部为false
        visited[u] = true;                // 标记顶点u为已访问
        q.push(u);                        // 将顶点u加入队列
        while (!q.empty())
        {                       // 当队列不为空时
            int x = q.front(); // 取出队首元素
            q.pop();           // 弹出队首元素
            for (const Edge &e : adj[x])
            { // 遍历顶点x的所有出边
                int v = e.to;
                int w = e.weight;
                if (!visited[v])
                {                                     // 如果顶点v未被访问过
                    visited[v] = true;                 // 标记顶点v为已访问
                    min_weight = min(min_weight, w); // 更新最小边权值
                    q.push(v);                         // 将顶点v加入队列
                }
            }
        }
    }
    
    int main()
    {
        int A[N][N] = {// 定义二维数组A(邻接矩阵)
                       {0, 2, 6, 4, INF, INF, INF},
                       {INF, 0, 3, INF, 2, INF, INF},
                       {INF, INF, 0, INF, INF, 5, INF},
                       {INF, 1, 5, 0, INF, INF, INF},
                       {INF, INF, INF, 3, 0, 2, 6},
                       {INF, INF, INF, INF, INF, 0, 3},
                       {INF, INF, INF, INF, INF, INF, 0}};
        for (int i = 0; i < N; i++)
        { // 遍历二维数组A
            for (int j = 0; j < N; j++)
            {
                if (A[i][j] != INF)
                {                            // 如果A[i][j]不是∞,说明存在边(i, j)
                    addEdge(i, j, A[i][j]); // 将边(i, j)加入邻接表
                }
            }
        }
        int min_weight = INF;                              // 定义最小边权值初始值为∞
        bfs(0, min_weight);                                  // 从顶点0开始遍历图
        cout << "Minimum weight: " << min_weight << endl; // 输出最小边权值
        return 0;
    }
    

    4、设计一个基于Floyd的最短路径算法,计算所有顶点之间的最短路径。

    #include <iostream>
    
    using namespace std;
    
    const int N = 30;            // 定义数组大小为30*30
    const int INF = 0x3f3f3f3f; // 定义∞的值
    
    int main()
    {
        int A[N][N] = {// 定义二维数组A(邻接矩阵)
                       {0, 2, 6, 4, INF, INF, INF},
                       {INF, 0, 3, INF, 2, INF, INF},
                       {INF, INF, 0, INF, INF, 5, INF},
                       {INF, 1, 5, 0, INF, INF, INF},
                       {INF, INF, INF, 3, 0, 2, 6},
                       {INF, INF, INF, INF, INF, 0, 3},
                       {INF, INF, INF, INF, INF, INF, 0}};
        for (int k = 0; k < N; k++)
        { // 遍历所有顶点
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    A[i][j] = min(A[i][j], A[i][k] + A[k][j]); // 更新最短路径
                }
            }
        }
        // 输出最短路径矩阵
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cout << A[i][j] << " ";
            }
            cout << endl;
        }
        return 0;
    }
    

    以上就是ChatGPT给出的答案

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 12月18日
  • 已采纳回答 12月17日
  • 创建了问题 12月16日

悬赏问题

  • ¥50 内网的网页打开的Excel下载到本地
  • ¥15 该网站用的是什么程序模版
  • ¥15 verilog modelsim仿真
  • ¥15 Power BI 里面 帕累托图突出显示前20
  • ¥50 用预估矫正法,分数阶微分方程组传染病的最优控制代码怎么写
  • ¥15 画个数据流程图,手画也行
  • ¥60 AS自带模拟器AVD Root 和 Xposed安装
  • ¥30 哪位搞Android的编程师可以帮我远程一下,悬赏30元
  • ¥15 solidity部署上合约,可以mint,也继承接口了,在区块链也不显示代币名字
  • ¥15 讨论 博士论文交互项怎么讨论?