一、相关概念
- 连通图
两个顶点v、w连通是指：v和w之间存在路径（直接或间接）。
连通图：是指无向图，图中任意两节点都连通，则称为连通图。
- 连通分量
无向图中的极大连通子图（这些节点都是连通的，并且不能再多了，再多就有不连通的了）称为连通分量
① 任何连通图的连通分量只有一个，即是其自身
② 非连通的无向图有多个连通分量。
- 强连通图
两个顶点v、w强连通是指：从v到w、从w到v都有路径。
强连通图：是指有向图，图中任意两节点都强连通，则称为强连通图。
- 强连通分量
有向图中的极大强连通子图，称为强连通分量
① 强连通图只有一个强连通分量，即是其自身。
② 非强连通的有向图有多个强连分量。
- 连通网
连通图中的边有具有一定的意义，具有权值，则称这样的连通图为连通网。
- 生成树
生成树中包含图中的n个节点，n-1条边（再多一条边就会成环）。关键点：1）任意两点间都连通；2）是一棵树
- 最小生成树
在连通网的所有生成树中，边代价和最小的生成树，称为最小生成树
二、题目
题目
1.png
2.png
思路
无向图的最小生成树的特点：最小生成树中有n个节点，n-1条边，且这n个节点一定是连通的，各边上代价和最小。所以，这道题目实质上就是要求无向图的最小生成树。本文采用Kruskal算法生成最小生成树，这是一种基于并查集的贪心算法。
代码
package 面试.贝壳网;
import java.util.Arrays;
import java.util.Scanner;
/**
*
* <p>Description:
* 5
* 4 1 8 2 </p>
* @author 杨丽金
* @date 2018-8-19
* @version 1.0
*/
public class 最小生成树 {
// 图节点
class Node{
// 节点编号（从0开始）
int num;
// 节点信息：海拔
int A;
public Node(int num,int A){
this.num=num;
this.A=A;
}
@Override
public String toString() {
return "Node [num=" + num + ", A=" + A + "]";
}
}
// 图的边
class Road implements Comparable{
// 边编号（从0开始）
int num;
// 边左节点编号
int a;
// 边右节点编号
int b;
// 边权值
int cost;
// 定义默认排序规则
@Override
public int compareTo(Object o) {
if(o instanceof Road){
Road anotherRoad=(Road)o;
if(this.cost>anotherRoad.cost){
return 1;
}else if(this.cost<anotherRoad.cost){
return -1;
}else{
return 0;
}
}
return 0;
}
@Override
public String toString() {
return "Road [num=" + num + ", a=" + a + ", b=" + b + ", cost="
+ cost + "]";
}
public Road(int num, int a, int b, int cost) {
super();
this.num = num;
this.a = a;
this.b = b;
this.cost = cost;
}
}
// 图
class MGraph{
// 节点数
int n;
// 边数
int e;
// 节点
Node[] nodes;
// 边
Road[] roads;
// 边及权值
int[][] edges;
public MGraph(int n){
this.n=n;
// 节点编号从0开始
nodes=new Node[n];
edges=new int[n][n];
e=(n*n-n)/2;
roads=new Road[e];
}
@Override
public String toString() {
return "MGraph [n=" + n + ", nodes=" + Arrays.toString(nodes)
+ ", roads=" + Arrays.toString(roads)
+ ",roads.length="+roads.length;
}
}
public static void main(String[] args) {
new 最小生成树().exe();
}
private void exe(){
Scanner scan=new Scanner(System.in);
// N个节点
int N=scan.nextInt();
MGraph g=new MGraph(N);
for(int i=0;i<N;i++){
g.nodes[i]=new Node(i,scan.nextInt());
}
// 初始化边的大小
/*for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i==j){
// (0,0)
g.edges[i][j]=0;
}else{
// 取决于海拔大的村庄
g.edges[i][j]=Math.max(g.nodes[i].A, g.nodes[j].A);
}
}
}*/
int k=0;
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
// 遍历一半的节点
// g.roads[k]=new Road(k,i,j,g.edges[i][j]);
g.roads[k]=new Road(k,i,j,Math.max(g.nodes[i].A, g.nodes[j].A));
k++;
}
}
// 输出
System.out.println(g);
// 图的边大小
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
System.out.print(g.edges[i][j]+"\t");
}
System.out.println();
}
int result=kruskal(g);
System.out.println(result);
}
/**
* 基于并查集的贪心算法
* 利用最小生成树Kruskal算法得到最小生成树，并得到最小代价和
* @param g
* @return
*/
private int kruskal(MGraph g){
// 最小生成树的边代价综合
int sum=0;
// 将边按照权重从小到大的顺序排列
Road[] roads=g.roads;
Arrays.sort(roads);
// 并查集
int[] v=new int[g.n];
// 初始化并查集
for(int i=0;i<g.n;i++){
// 每个节点分别处在独立的集合中
v[i]=i;
}
// 贪心算法：使每次选择看起来都是当前最佳选择，期望通过局部最优选择得到全局最优选择
for(int i=0;i<g.e;i++){
// 当前这条边的两个端点是否在同一集合
int a=getRoot(v,g.roads[i].a);
int b=getRoot(v,g.roads[i].b);
if(a!=b){
// 不在同一集合，可以放入最小生成树
v[a]=b;
System.out.println("road:"+g.roads[i]);
sum+=g.roads[i].cost;
}else{
continue;
}
}
return sum;
}
/**
* 从并查集v中得到节点x的根节点
* 并查集：就是树的双亲存储结构，
* 里面存储了一个或多个树（当某节点的父节点是其本身时，它就是它所在树的根节点）
* @param v
* @param x
* @return
*/
private int getRoot(int[] v, int x) {
while(x!=v[x]){
x=v[x];
}
return x;
}
}
网友评论