利用c++解决图论问题

Question

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

Answer 1

由于题太长导致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给出的答案