有关Java图论的，不是很明白，求解答

只需要帮忙理解一下题目，告诉题目要干啥，再提供一个大致思路就行了

img

简单来说，就是为了解决不同币种之间的汇率问题，如果每个币种之间都存在汇率关系，这个问题就很简单，只需要创建两个币种的map即可，但是问题就在于存在两个币种之间不存在汇率关系，但是可以通过币种的转换来实现二者之间的汇率map，由于这个转换关系可以通过多种情况，这就是所谓的图，有多种途径达到汇率的转换。 基本思路是先实现它的基础版本，也就是假设所有币种都存在汇率关系进行编程，然后再其基础上添加汇率转换功能。

汇率兑换图，有向边上的权重是log(1/汇率)，需要在图中找到最短的路径获得最高的汇率。题目要求实现四个功能，并自行构造测例

  • 最佳转换汇率：输入n*n的汇率矩阵，并输出给定的任意两个节点间的最佳汇率转换路径
    • 这个问题就是寻找两点之间最短路径，用Dijistra算法即可
  • 套利寻找：输入n*n的汇率矩阵，找到回路可以获得利润
    • 需要算每两点之间的最大距离和最小距离，然后构造回路，回路的距离之和可以用前面算的最大距离和最小距离算出对应的回路和，找到所有距离之和小于0的回路
  • 兑换桥：输入n*n的汇率矩阵，构造无向图，包含可以直接兑换的边；之后找到所有的可以通过多步兑换连接的边，称之为兑换桥。举了一个如何判断在u,v中存在这种边的方法：使用DFS，每个点有d(v)代表第几次遍历到，m(v)代表第几次探索到（探索到不代表会遍历它），如果m(v)>d(u)，则说明存在这样的边
    • 题中给的方法我并没有看懂，叙述方法中的语法极烂，表意不明。直接DFS后在里面的边都是联通的。
  • Demo: 录制对应的测例视频

基础示例代码如下：


package HelpOther;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 基础汇率换算应用
 * 我们假设有四个币种，人民币:CNY 美元：USA 日元：YEN 韩元：KRW
 * 其中 :
 * CNY:USA=7:1
 * CNY:YEN=1:100
 * CNY:KRW=1:1000
 * USA:YEN=1:500
 * USA:KRW=1:200
 * YEN:KRW=1:100
 * 上面四个币种的的换算关系现在都知道了，我们首先根据前面的关系进行一个汇率换算的基础应用实现
 */
public class ExchangeRate {
    public Map<String,Double> exchange;

    /**
     * 这里是初始化币种汇率的方法，一般来说是使用配置的方式进行读取载入的
     * 这里只是为了演示
     */
    public ExchangeRate(){
        exchange=new HashMap<>();
        exchange.put("CNY:USA",7.000);
        exchange.put("CNY:YEN",0.010);
        exchange.put("CNY:KRW",0.001);
        exchange.put("USA:YEN",0.002);
        exchange.put("USA:KRW",0.005);
        exchange.put("YEN:KRW",0.010);
    }

    /**
     * 汇率转换组件，根据入参ccy1和ccy2得到两个币种的汇率比ccy1:ccy2
     * @param ccy1 第一个币种
     * @param ccy2 第二个币种
     * @return ccy1:ccy2
     */
    public double Exchange(String ccy1,String ccy2){
        double result=-1;
        String exchangeStr1=ccy1+":"+ccy2;
        String exchangeStr2=ccy2+":"+ccy1;
        if(exchange.get(exchangeStr1)==null){
            if(exchange.get(exchangeStr2)!=null){
                result=1/exchange.get(exchangeStr2);
            }else {
                return  -1;
            }
        }else{
            result=exchange.get(exchangeStr1);
        }
        return result;
    }
    public static void main(String[] args) {
        ExchangeRate exchangeRate=new ExchangeRate();
        String ccy1=null;
        String ccy2=null;
        Scanner scanner=new Scanner(System.in);
        System.out.println("欢迎进入汇率转换系统，首先请输入你的本币种：");
        ccy1=scanner.nextLine();
        System.out.println("请输入你的目标币种:");
        ccy2=scanner.nextLine();
        System.out.println(ccy1+":"+ccy2+"的汇率转换比为:");
        System.out.println(exchangeRate.Exchange(ccy1,ccy2));
    }
}

img