newv的判断是否多余

Question

拓展切分时， 对newv进行了判断， 找到不属于蓝色切分的端点， 然后将其visited设为true. 这个newv = visited[minEdge.getV()] ? minEdge.getW() : minEdge.getV(); 是否多余呢， 因为好像每次往优先队列里面丢入新的横切边的时候， 新的横切边的初始化方式都是v为true的结点, w为false的结点的呀。

Answer 1

liuyubobobo 2020-10-26 12:52:41

把你认为的，去掉冗余的，完整的 Prim 算法的代码贴一下？

• 提问者 IT_god #1

  public Prim(WeightedGraph G){
  
          this.G = G;
          mst = new ArrayList<>();
  
          CC cc = new CC(G);
          if(cc.count() > 1) return;
  
          boolean visited[] = new boolean[G.V()];
          visited[0] = true;
          Queue pq = new PriorityQueue<WeightedEdge>();
          for(int w: G.adj(0))
              pq.add(new WeightedEdge(0, w, G.getWeight(0, w)));
  
          while(!pq.isEmpty()){
  
              WeightedEdge minEdge = (WeightedEdge) pq.remove();
              if(visited[minEdge.getV()] && visited[minEdge.getW()])
                  continue;
  
              mst.add(minEdge);
  
              int newv = minEdge.getW();
              visited[newv] = true;
              for(int w: G.adj(newv))
                  if(!visited[w])
                      pq.add(new WeightedEdge(newv, w, G.getWeight(newv, w)));
          }
      }

• liuyubobobo 回复 提问者 IT_god #2

  理解了。可以，没问题的：）

• 提问者 IT_god 回复 liuyubobobo #3

  谢谢老师

点开查看后面1条评论