图的最小生成树

关于图的几个概念定义：

连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。
强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。
连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
1.Prim算法
假设最小生成树的顶点集合Vr,边的集合为Er.
1.初始化：从图G的顶点集合V中任意选择一个顶点加入到Vr.Er为空。
2.遍历Vr中的所有顶点，找到和他们相关联且权值最小的边（如果这条边的两个顶点均在Vr中，则跳过此边），将最小的边加入到Er中，相应的顶点加入到Vr中。
3.第2步一共做n-1次。

public Graph createMinTreeWithPrim(Graph g){
        
        Set<Node> nodes=g.nodes;
        Set<Node> minNodes=new HashSet<>();
        Set<Edge> minEdges=new HashSet<>();
        for(Node node:nodes){
            minNodes.add(node);
            //System.out.println("selected"+node.value);
            break;
        }
        
        for(int i=0;i<nodes.size()-1;i++){
            
            Edge minEdge=null;
            int minWeight=Integer.MAX_VALUE;
            for(Node n:minNodes){
                List<Edge> edges=n.getEdges();

                for(Edge e:edges){
                    if(minNodes.contains(e.start)&&minNodes.contains(e.end)){
                        continue;
                    }
                    if(e.weight<minWeight){
                        minWeight=e.weight;
                        minEdge=e;
                    }
                    
                    
                }
            }

            minEdges.add(minEdge);
            if(minNodes.contains(minEdge.start)){
                minNodes.add(minEdge.end);
            }
            else{
                minNodes.add(minEdge.start);
            }
            
        
        }
        ///System.out.println("minNodes"+minNodes.size());
        Graph graph=new Graph(minNodes,minEdges);
        return graph;
        
        
    }

2.Kruskal算法
并查集：
1）find(x):找到包含x元素的子集合
2）union(x,y):分别找到包含x，包含y的两个不想交的子集合的并集。

public class SetUtil<T> {

  Set<Set<T>>  set;
  
  public SetUtil(Set<Set<T>> s){
      this.set=s;
      
  }
  public Set find(T x){
      for(Set s:set){
          if(s.contains(x)){
              return s;
          }
      }
      return null;
  }
  
  
  public void union(T x,T y){
      Set sx=find(x);
      Set sy=find(y);
      if(sx!=null && sy!=null){
          sx.addAll(sy);
          set.remove(sy);
      }
      
  }
}

Kruskal算法思想
1.初始化，一个集合中S包含V个子集合。每个子集合中有一个元素，即图的一个顶点。
2.对图G的所有边进行排序，每次选出权值最小的边，在S查找这条边的开始节点和结束节点所属的子集，如果是同一个，则跳过。否则合并这两个子集。
3.第2步共做n-1次。

    /**
     * 
     * @param g
     * @return <p>
     *         Description:图的边权重排序，每次选权重最小且不会构成环路的边加进来。一共需要n-1次
     *         </p>
     */
    public Graph createMinTreeWithKruskal(Graph g) {
        Set<Edge> edges = g.edges;
        Set<Edge> minEdges = new HashSet<>();
        Set<Node> nodes = g.nodes;

        Set<Set<Node>> nodeSet = new HashSet<>();
        

        for(Node n:nodes){
            Set newSet=new HashSet<>();
            newSet.add(n);
            nodeSet.add(newSet);
            
        }
        SetUtil setUtil = new SetUtil(nodeSet);
        for (int i = 0; i < g.nodes.size() - 1; i++) {
            int minWeight = Integer.MAX_VALUE;
            Edge minEdge = null;

            for (Edge edge : edges) {
                if (edge.weight <= minWeight) {
                    
                    Set start = setUtil.find(edge.start);
                    Set end = setUtil.find(edge.end);
                    if (start.equals(end)) {
                        //System.out.println("skip"+edge.start.value+""+edge.end.value);
                        continue;
                    }
                    else{
                        minWeight = edge.weight;
                        minEdge = edge;
                    }

                }
            }
            
            setUtil.union(minEdge.start, minEdge.end);
            minEdges.add(minEdge);
                
            edges.remove(minEdge);

        }

        Graph minGraph = new Graph(nodes, minEdges);
        return minGraph;

    }

IMG_20180716_155130.jpg