📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: chengrr
跳转到指定楼层
上一主题 下一主题
收起左侧

新鲜店面骨狗

🔗
luka77 2017-12-14 13:54:51 | 只看该作者
全局:
感谢楼主分享!我感觉可以转化为无向图来做,就变成了single source shortest distance 问题了
回复

使用道具 举报

🔗
 楼主| chengrr 2017-12-19 10:28:32 | 只看该作者
全局:
luka77 发表于 2017-12-14 13:54
感谢楼主分享!我感觉可以转化为无向图来做,就变成了single source shortest distance 问题了

我怎么没想到!看来功底不够
回复

使用道具 举报

🔗
xiayank 2017-12-21 00:19:37 | 只看该作者
全局:
楼主请问不能用BFS直接找最短距离吗?以其中一个要找的Node为root开始
回复

使用道具 举报

🔗
littlegrass 2017-12-23 11:38:54 | 只看该作者
全局:
请问楼主,家谱里的node 是给的还是自己写?

补充内容 (2017-12-23 11:39):
node 类
回复

使用道具 举报

🔗
miamiae 2017-12-24 05:08:32 | 只看该作者
全局:
那夫妻之间的距离是为0吗?
回复

使用道具 举报

🔗
randrand1 2017-12-24 06:58:59 | 只看该作者
全局:
miamiae 发表于 2017-12-24 05:08
那夫妻之间的距离是为0吗?

有道理。。。感觉用无向图求距离的算法最为简洁!
回复

使用道具 举报

🔗
Elina_huang 2017-12-31 00:13:57 | 只看该作者
全局:
请问楼主输入信息是什么形式给的呢?还是说自己随意?不能用BFS直接找最短距离吗?
回复

使用道具 举报

🔗
amazinglu 2018-3-4 07:19:00 | 只看该作者
全局:
对的,就是无向图然后BFS搜
回复

使用道具 举报

🔗
lf963 2018-4-8 02:25:42 | 只看该作者
全局:
打算當成無向圖用BFS搜索的話,請問 class 要怎麼設計呢
回复

使用道具 举报

🔗
lf963 2018-4-8 06:52:11 | 只看该作者
全局:
用BFS找圖的最短路徑
我假設夫妻之間的距離為0
並把夫妻當成一個 node 來看
也就是說原本 Abe 和 Mona 在圖中應該是兩個不同的 node,但我把他們用同個 node 來代表,此 node 命名為 abeMona



  1. import java.util.*;
  2. public class Simpson {
  3.     public static void main(String[] args){
  4.         Map<PersonNode,Set<PersonNode>> familyTree = new HashMap<>();

  5.         PersonNode abe = new PersonNode("Abe");
  6.         familyTree.put(abe,new HashSet<>());

  7.         PersonNode mona = new PersonNode("Mona");
  8.         familyTree.put(mona,new HashSet<>());

  9.         PersonNode clancy = new PersonNode("Clancy");
  10.         familyTree.put(clancy,new HashSet<>());

  11.         PersonNode jacqueline = new PersonNode("Jacqueline");
  12.         familyTree.put(jacqueline,new HashSet<>());

  13.         PersonNode herb = new PersonNode("Herb");
  14.         familyTree.put(herb,new HashSet<>());

  15.         PersonNode homer = new PersonNode("Homer");
  16.         familyTree.put(homer,new HashSet<>());

  17.         PersonNode marge = new PersonNode("Marge");
  18.         familyTree.put(marge,new HashSet<>());

  19.         PersonNode patty = new PersonNode("Patty");
  20.         familyTree.put(patty,new HashSet<>());

  21.         PersonNode selma = new PersonNode("Selma");
  22.         familyTree.put(selma,new HashSet<>());

  23.         PersonNode bart = new PersonNode("Bart");
  24.         familyTree.put(bart,new HashSet<>());

  25.         PersonNode lisa = new PersonNode("Lisa");
  26.         familyTree.put(lisa,new HashSet<>());

  27.         PersonNode maggie = new PersonNode("Maggie");
  28.         familyTree.put(maggie,new HashSet<>());

  29.         PersonNode ling = new PersonNode("Ling");
  30.         familyTree.put(ling,new HashSet<>());



  31.         /*We view couple as one single node*/
  32.         PersonNode abeMona = new PersonNode("AbeMona");
  33.         familyTree.put(abeMona,new HashSet<>());

  34.         PersonNode clancyJacqueline = new PersonNode("ClancyJacqueline");
  35.         familyTree.put(clancyJacqueline,new HashSet<>());

  36.         PersonNode homerMarge = new PersonNode("HoerMarge");
  37.         familyTree.put(homerMarge,new HashSet<>());


  38.         /*construct edges*/
  39.         familyTree.get(abeMona).add(herb);
  40.         familyTree.get(abeMona).add(homerMarge);

  41.         familyTree.get(clancyJacqueline).add(homerMarge);
  42.         familyTree.get(clancyJacqueline).add(patty);
  43.         familyTree.get(clancyJacqueline).add(selma);

  44.         familyTree.get(herb).add(abeMona);

  45.         familyTree.get(homerMarge).add(abeMona);
  46.         familyTree.get(homerMarge).add(clancyJacqueline);
  47.         familyTree.get(homerMarge).add(bart);
  48.         familyTree.get(homerMarge).add(lisa);
  49.         familyTree.get(homerMarge).add(maggie);

  50.         familyTree.get(patty).add(clancyJacqueline);

  51.         familyTree.get(selma).add(clancyJacqueline);
  52.         familyTree.get(selma).add(ling);

  53.         familyTree.get(bart).add(homerMarge);

  54.         familyTree.get(lisa).add(homerMarge);

  55.         familyTree.get(maggie).add(homerMarge);

  56.         familyTree.get(ling).add(selma);



  57.         /*If someone is married, put that person and his/her spouse into this map*/
  58.         HashMap<PersonNode,PersonNode> couple = new HashMap<>();

  59.         couple.put(abe,abeMona);
  60.         couple.put(mona,abeMona);

  61.         couple.put(clancy,clancyJacqueline);
  62.         couple.put(jacqueline,clancyJacqueline);

  63.         couple.put(homer,homerMarge);
  64.         couple.put(marge,homerMarge);


  65.         Simpson s = new Simpson();
  66.         int distance = s.findShortestDistance(abe,mona, familyTree,couple);
  67.         System.out.println(distance);
  68.     }

  69.     int findShortestDistance(PersonNode A, PersonNode B, Map<PersonNode,Set<PersonNode>> familyTree, HashMap<PersonNode,PersonNode> couple){
  70.         //if person A and person B are couple, return 0;
  71.         if(couple.containsKey(A) && couple.containsKey(B) && couple.get(A).equals(couple.get(B)))
  72.             return 0;
  73.         //if person A is married but B is not his/her spouse, we use A's spouse to search instead of A
  74.         if(couple.containsKey(A))
  75.             A = couple.get(A);

  76.         //if person B is married but A is not his/her spouse, we use B's spouse to search instead of B
  77.         if(couple.containsKey(B))
  78.             B = couple.get(B);
  79.         Queue<PersonNode> myQ = new LinkedList<>();
  80.         Set<PersonNode> visited = new HashSet<>();
  81.         int distance = 0;
  82.         myQ.add(A);
  83.         visited.add(A);

  84.         while(!myQ.isEmpty()){
  85.             int qSize = myQ.size();
  86.             for(int i=0; i<qSize; i++){
  87.                 PersonNode curPerson = myQ.poll();
  88.                 if(curPerson == B)
  89.                     return distance;

  90.                 for(PersonNode p : familyTree.get(curPerson)){
  91.                     if(!visited.contains(p)){
  92.                         myQ.add(p);
  93.                         visited.add(curPerson);
  94.                     }
  95.                 }
  96.             }
  97.             distance++;
  98.         }
  99.         //we cannot find a path from A to B
  100.         return -1;
  101.     }
  102. }

  103. class PersonNode{
  104.     String name;
  105.     PersonNode(String name){
  106.         this.name = name;
  107.     }

  108.     public boolean equals(Object o){
  109.         PersonNode p = (PersonNode) o;
  110.         return this.name.equals(p.name);
  111.     }

  112.     public int hashCode(){
  113.         return name.hashCode();
  114.     }
  115. }


复制代码

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表