4.3节后习题 - 图的高级应用

一、外汇交易平台套利检测问题

题目描述

某外汇交易平台提供货币兑换汇率表。例如，1美元兑换0.9欧元，1欧元兑换110日元，1日元兑换0.01美元。设计一个算法，判断是否存在通过循环兑换获利的可能（即负权环）。

输入：

货币种类数 n 和兑换关系数 m
接下来 m 行，每行为货币A与货币B汇率，表示1单位A可兑换的B的数量

输出：

"存在套利机会" 或 "无套利机会"

题目分析

分析思路

判断是否存在通过循环兑换获利的可能，等价于在有向图中检测是否存在负权环。

建模思路：

货币兑换关系可建模为有向图：每个货币为顶点，兑换关系A→B的汇率r表示从A到B的边权为log(r)
若存在环A1→A2→…→An→A1，则总兑换倍数为各边权乘积r1*r2*…*rn
若该乘积>1（即总对数和log(r1)+log(r2)+…+log(rn)>0），则存在套利机会，对应图中存在正权环
为了利用最短路径算法检测环，可将边权取负数，转化为检测负权环问题

核心知识点：

图的建模：将货币兑换关系转化为有向图，边权为对数形式的兑换率
Bellman-Ford算法：用于检测图中是否存在负权环，适用于边数较少的场景
SPFA算法：Bellman-Ford的优化版本，利用队列优化松弛操作，可高效检测负权环

解法代码（SPFA算法）

代码实现

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;

const int MAXN = 105;
const int MAXM = 1005;

struct Edge {
    int to;
    double weight;
};

vector<Edge> adj[MAXN];
int n, m;
double dist[MAXN];
int cnt[MAXN]; // 记录每个节点的入队次数
bool inQueue[MAXN];

bool hasNegativeCycle() {
    memset(dist, 0, sizeof(dist)); // 初始距离设为0（假设从任意节点出发均可形成环）
    memset(cnt, 0, sizeof(cnt));
    memset(inQueue, false, sizeof(inQueue));
    queue<int> q;

    // 为了检测所有可能的环，将所有节点加入队列（类似多源最短路径）
    for (int i = 0; i < n; ++i) {
        q.push(i);
        inQueue[i] = true;
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;

        for (const Edge& e : adj[u]) {
            int v = e.to;
            double w = e.weight;
            // 松弛操作：若通过u到v的路径更短（即总对数和更大，对应实际兑换倍数更大）
            if (dist[v] < dist[u] + w) {
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) { // 若一个节点入队次数超过n次，说明存在环
                    return true;
                }
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        double rate;
        cin >> a >> b >> rate;
        // 边权取对数，转换为加法问题：log(a->b) = ln(rate)
        // 检测正权环等价于检测负权环（将边权取反）
        adj[a].push_back({b, log(rate)});
    }

    if (hasNegativeCycle()) {
        cout << "存在套利机会" << endl;
    } else {
        cout << "无套利机会" << endl;
    }
    return 0;
}

算法解析：

建模：将每种货币视为顶点，兑换关系视为有向边，边权为汇率的自然对数log(rate)。若存在环使得各边权之和sum(log(rate)) > 0，则总兑换倍数exp(sum(log(rate))) > 1，存在套利机会。
负权环检测：将边权取反（即存储为-log(rate)），问题转化为检测图中是否存在负权环。使用SPFA算法，通过记录每个节点的入队次数，若某个节点入队次数超过顶点数n，说明存在环。
多源初始化：为了检测所有可能的环，将所有节点作为起点加入队列，确保覆盖所有可能的环结构。

二、六度空间理论验证问题

题目描述

在社交网络中，若两个人的最短好友链长度 ≤6，则称他们满足"六度空间"理论。给定好友关系图（无向无权图），计算所有点对中最短路径的最大值，验证是否 ≤6。

输入：

用户数 n 和好友关系数 m
接下来 m 行，每行为 u v，表示用户 u 和 v 是好友

输出：

最长的最短路径长度。若>6，输出"不符合六度空间"，否则输出"符合"

题目分析

分析思路

给定无向无权图，计算所有点对的最短路径长度，并找到最大值。若最大值≤6，则符合六度空间理论，否则不符合。

由于图是无权的，最短路径可通过**广度优先搜索（BFS）**高效计算，每个节点作为起点进行一次BFS，记录到其他节点的最短距离。

核心知识点：

BFS算法：适用于无权图的最短路径计算，时间复杂度为O(V+E)
多源最短路径：对每个节点执行BFS，获取其到所有其他节点的最短路径

解法代码（BFS实现）

代码实现

cpp

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

const int MAXN = 1005;

vector<int> adj[MAXN];
int n, m;
int max_dist = 0; // 记录最长最短路径

void bfs(int start) {
    vector<int> dist(n, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
                if (dist[v] > max_dist) {
                    max_dist = dist[v]; // 更新最长距离
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图，双向加边
    }

    // 对每个节点执行BFS
    for (int i = 0; i < n; ++i) {
        bfs(i);
    }

    cout << "最长最短路径长度：" << max_dist << endl;
    if (max_dist > 6) {
        cout << "不符合六度空间" << endl;
    } else {
        cout << "符合" << endl;
    }
    return 0;
}

算法解析：

图的存储：使用邻接表存储无向图，每个节点的好友关系双向添加。
BFS计算最短路径：对每个节点作为起点进行BFS，记录到其他节点的距离dist[v]。BFS的层级对应最短路径长度，因此无需显式维护距离数组，只需在遍历过程中更新最长距离max_dist。
结果判断：遍历所有点对后，若max_dist超过6，则输出"不符合"，否则输出"符合"。

三、综合练习题

1. 最短路径算法比较

题目：比较Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法的适用场景和时间复杂度。

答案与解析

算法	时间复杂度	空间复杂度	适用场景	能否处理负权边	能否检测负权环
Dijkstra	O((V+E)logV)	O(V)	单源最短路径，无负权边	否	否
Bellman-Ford	O(VE)	O(V)	单源最短路径，可有负权边	是	是
Floyd-Warshall	O(V³)	O(V²)	多源最短路径	是	是

详细分析：

Dijkstra算法：
- 优点：对于无负权边的图效率最高
- 缺点：不能处理负权边
- 适用：稠密图或需要求单源最短路径且保证无负权边
Bellman-Ford算法：
- 优点：能处理负权边，能检测负权环
- 缺点：时间复杂度较高
- 适用：存在负权边的单源最短路径问题
Floyd-Warshall算法：
- 优点：能求解所有点对间的最短路径
- 缺点：时间复杂度高，不适合大规模图
- 适用：小规模图的多源最短路径问题

2. 图的应用场景分析

题目：列举图在实际生活中的应用场景，并说明采用的图算法。

答案与解析

1. 社交网络分析

应用：好友推荐、影响力分析、社区发现
算法：BFS/DFS遍历、最短路径、连通分量、PageRank

2. 交通导航系统

应用：路径规划、实时路况分析
算法：Dijkstra最短路径、A*搜索算法

3. 互联网路由

应用：数据包路由、网络拓扑分析
算法：最短路径算法、生成树算法

4. 任务调度

应用：项目管理、依赖关系处理
算法：拓扑排序、关键路径法(CPM)

5. 推荐系统

应用：商品推荐、内容推荐
算法：协同过滤、随机游走、图神经网络

6. 生物信息学

应用：蛋白质相互作用网络、基因调控网络
算法：聚类算法、模式挖掘

7. 金融风控

应用：反欺诈、洗钱检测、关联关系挖掘
算法：社区发现、异常检测、图嵌入

四、思考题

1. 图算法优化策略

题目：在处理大规模图数据时，有哪些常见的优化策略？

思考与解答

1. 存储优化

压缩存储：使用压缩稀疏行(CSR)格式存储稀疏图
分布式存储：将大图分割存储在多台机器上
缓存优化：利用局部性原理优化内存访问

2. 算法优化

并行化：利用多核CPU或GPU进行并行计算
剪枝策略：在搜索过程中提前终止不必要的分支
近似算法：用近似算法替代精确算法，提高效率

3. 数据结构优化

选择合适的存储方式：根据图的特点选择邻接表、邻接矩阵或其他结构
索引优化：建立适当的索引加速查询
预处理：对图进行预处理，如计算度数、构建辅助结构

4. 工程实践

分层处理：将复杂问题分解为多个子问题
增量更新：支持图的动态更新而不需要重新计算
容错机制：处理数据不一致和系统故障

2. 图算法在AI中的应用

题目：图算法在人工智能领域有哪些重要应用？

思考与解答

1. 图神经网络(GNN)

应用：节点分类、图分类、链接预测
典型算法：GCN、GraphSAGE、GAT
场景：社交网络分析、分子性质预测、知识图谱

2. 知识图谱

应用：实体关系抽取、知识推理、问答系统
算法：随机游走、嵌入学习、路径推理
场景：搜索引擎、智能助手、推荐系统

3. 强化学习

应用：状态空间搜索、策略优化
算法：蒙特卡洛树搜索、价值网络
场景：游戏AI、机器人控制、自动驾驶

4. 计算机视觉

应用：场景图生成、目标关系建模
算法：图匹配、图卷积
场景：图像理解、视频分析、3D重建

5. 自然语言处理

应用：依存句法分析、文本分类、机器翻译
算法：图注意力机制、序列到图的转换
场景：语义理解、信息抽取、对话系统

本章总结

通过第四章的学习，我们深入掌握了图的基本概念、存储方式、遍历算法以及实际应用。主要收获包括：

理论基础：理解了有向图与无向图、连通性与强连通性等基本概念
存储技术：掌握了邻接矩阵、邻接表、链式前向星等存储方式的优缺点
算法实现：熟练掌握了DFS、BFS、最短路径等核心算法
实际应用：了解了图算法在社交网络、交通导航、金融风控等领域的应用

图作为一种重要的数据结构，在计算机科学和实际应用中都具有广泛的价值。通过不断练习和思考，相信大家能够更好地运用图算法解决实际问题。

4.3节后习题 - 图的高级应用 ​

一、外汇交易平台套利检测问题 ​

题目描述 ​

题目分析 ​

解法代码（SPFA算法） ​

二、六度空间理论验证问题 ​

题目描述 ​

题目分析 ​

解法代码（BFS实现） ​

三、综合练习题 ​

1. 最短路径算法比较 ​

2. 图的应用场景分析 ​

四、思考题 ​

1. 图算法优化策略 ​

2. 图算法在AI中的应用 ​

本章总结 ​

4.3节后习题 - 图的高级应用

一、外汇交易平台套利检测问题

题目描述

题目分析

解法代码（SPFA算法）

二、六度空间理论验证问题

题目描述

题目分析

解法代码（BFS实现）

三、综合练习题

1. 最短路径算法比较

2. 图的应用场景分析

四、思考题

1. 图算法优化策略

2. 图算法在AI中的应用

本章总结