4.15.1、无向图的相关术语

• 相邻顶点：当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点；
• 度： 某个顶点的度就是依附于该顶点的边的个数；
• 子图：是一幅图的所有边的子集组成的图；
• 路径：是由边顺序连接的一系列的顶点组成；
• 环：是一条至少含有一条边且起点和终点相同的路径；
• 连通图：图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称为连通图；
• 连通子图：一个非连通图有若干连通的部分组成，每一个连通的部分都可以称为该图的连通子图；
  

4.15.2、无向图图的存储结构

要表示一幅图，只需要表示清楚以下两个部分的内容：

• 图中的所有顶点
• 所有连接顶点的边
  常见的图的存储结构有两种：邻接矩阵和邻接表

4.15.2.1、邻接矩阵

• 使用一个N*N的二维数组int[N][N]adj，把索引的值看做是顶点；
• 如果顶点a与顶点b相连，我们只需要将adj[a][b]和adj[b][a]的值设置为1，否则设置为0即可；
  

但是邻接矩阵的存储方式的空间复杂度为N^2，如果我们处理的问题的数据规模比较大，那么内存空间就需要消耗很多，可能造成不够用的情况

4.15.2.2、邻接表

• 使用一个大小为N的数组Queue[N]adj，把索引看做是顶点
• 每个索引处adj[v]存储了一个队列，该队列中存储的是所有与该顶点相邻的其他顶点
  

但是邻接表的空间不是一个线性级别的，所以后面我们一直采用邻接表这种存储方式来表示图。

4.15.3、无向图图的API设计和实现

API设计

类名	Graph
构造方法	Graph(int N)：创建一个包含N个顶点但不包含边的图
成员变量	private final int V：记录顶点的数量 private int E：记录边的数量 private Queue\[] adj：邻接表
成员方法	public int V()：获取图中的顶点数量 public int E()：获取图中边的数量 public void addEdge(int v,int w)：向图中添加一条边 public Queue\ adj(int v)：获取和顶点v相连的所有顶点

实现类

package cn.test.algorithm.datastruct;

public class Graph {
    //顶点的数量
    private final int V;

    //边的条数
    private int E;

    //邻接表
    private Queue<Integer>[] adj;

    public Graph(int N) {
        this.V = N;
        this.E = 0;
        this.adj = new Queue[N];

        for (int i = 0; i < adj.length; i++) {
            adj[i] = new Queue<Integer>();
        }

    }

    //获取顶点的数量
    public int V() {
        return V;
    }

    //获取边的数量
    public int E() {
        return E;
    }

    //向图中添加一条边v-w
    public void addEdge(int v, int w) {
        //无向图中边是没有方向的，所以如果添加边，那么v中有指向w的边，w中有指向v的边
        adj[v].enqueue(w);//v顶点有指向w的边

        adj[w].enqueue(v);//w顶点有指向v的边

        E++;//边的数量加1
    }

    //获取和顶点v相邻的所有顶点
    public Queue<Integer> adj(int v) {
        return adj[v];
    }
}

4.15.4、图的搜索

在很多情况下，我们需要遍历图，得到图的一些性质，例如，找到图中与指定的顶点相连的所有结点，或者判定某个顶点与指定顶点是否相通，是非常常见的需求。

有关图的搜索，最经典的算法有深度优先搜索和广度优先搜索。

4.15.4.1、深度优先搜索

所谓的深度优先搜索，指的是在搜索是，如果遇到一个结点即有子结点又有兄弟结点，那么先找子结点，然后再找兄弟结点。（先深入到字结点搜索，然后再找兄弟结点）

很明显，在由于边没有方向，所以如果4和5顶点相连，那么4会出现在5的相邻表中，5也会出现在4的相邻链表中，为了不对顶点进行重复搜索，应该要有相应的标记来表示当前顶点有没有搜索过，可以使用一个布尔类型的数组boolean[V] marked，所以表示顶点，值代表当前顶点是否已经被搜索过，如果已经被搜索过，标记为true，如果没有搜索过，标记为false。

API设计

类名	DepthFirstSearch
构造方法	DepthFirstSearch(Graph G,int s)：构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相通的顶点
成员变量	private boolean[] marked：索引表示顶点，值表示当前顶点是已经被搜索过 private int count：记录右多少个顶点与s顶点相通
成员方法	private void dfs(Graph G,int v)：使用深度优先搜索找出G图中与v顶点相通的所有顶点 public boolean marked(int w)：判断w顶点与s顶点是否相通 public int count()：获取与顶点s相通的所有顶点总数

实现类

package cn.test.algorithm.datastruct;

public class DepthFirstSearch {
    //索引表示顶点，值表示当前顶点是否已经查找过
    private boolean[] marked;
    //记录有多少个顶点与s顶点相通
    private int count;

    public DepthFirstSearch(Graph G, int s) {
        //初始化marked数组
        marked = new boolean[G.V()];
        //初始化跟顶点s相通的顶点数量
        count = 0;

        dfs(G, s);
    }

    //使用深度优先搜索找出G图中与v顶点的所有相通顶点
    private void dfs(Graph G, int v) {
        //把v顶点标识为已经搜索
        marked[v] = true;

        for (Integer w : G.adj(v)) {
            //判断当前顶点是被搜索过，如果没有搜索过就需要递归调用
            if (!marked[w]) {
                dfs(G, w);
            }
        }

        //相通顶点数量+1
        count++;
    }

    //判断w顶点与s顶点是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    //获取与顶点s相通的所有顶点总数
    public int count() {
        return count;
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.DepthFirstSearch;
import cn.test.algorithm.datastruct.Graph;

public class DepthFirstSearchTest {
    public static void main(String[] args) {
        //准备图
        Graph graph = new Graph(13);
        graph.addEdge(0, 5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(0, 6);
        graph.addEdge(5, 3);
        graph.addEdge(5, 4);
        graph.addEdge(3, 4);
        graph.addEdge(4, 6);

        graph.addEdge(7, 8);

        graph.addEdge(9, 10);
        graph.addEdge(9, 11);
        graph.addEdge(9, 12);
        graph.addEdge(11, 12);

        //准备深度优先对象
        DepthFirstSearch depthFirstSearch = new DepthFirstSearch(graph, 0);

        System.out.println("顶点数量："+depthFirstSearch.count());

        System.out.println("测试顶点0和顶点5是否相通"+depthFirstSearch.marked(5));
        System.out.println("测试顶点0和顶点7是否相通"+depthFirstSearch.marked(7));
    }
}

测试结果

顶点数量：7
测试顶点0和顶点5是否相通true
测试顶点0和顶点7是否相通false

4.15.4.2、广度优先搜索

所谓的广度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点又有兄弟结点，那么先搜索兄弟结点，然后再找子结点。（先把广度兄弟结点搜索完了后再搜索子结点）

类名	BreadthFirstSearch
构造方法	BreadthFirstSearch(Graph G,int s)：构造广度优先搜索对象，使用广度优先搜索找出G图中s顶点的所有相通的顶点
成员变量	private boolean[] marked：索引表示顶点，值表示当前顶点是已经被搜索过 private int count：记录右多少个顶点与s顶点相通 private Queue\ waitSearch：用来存储待搜索邻接表的顶点
成员方法	private void dfs(Graph G,int v)：使用广度优先搜索找出G图中与v顶点相通的所有顶点 public boolean marked(int w)：判断w顶点与s顶点是否相通 public int count()：获取与顶点s相通的所有顶点总数

实现类

package cn.test.algorithm.datastruct;

public class BreadthFirstSearch {
    //索引表示顶点，值表示当前顶点是否已经查找过
    private boolean[] marked;
    //记录有多少个顶点与s顶点相通
    private int count;
    //用来存储待搜索邻接表的顶点
    private Queue<Integer> waitSearch;

    public BreadthFirstSearch(Graph G, int s) {
        //初始化marked数组
        marked = new boolean[G.V()];
        //初始化跟顶点s相通的顶点数量
        count = 0;
        //初始化队列
        waitSearch = new Queue<Integer>();

        dfs(G, s);
    }

    //使用深度优先搜索找出G图中与v顶点的所有相通顶点
    private void dfs(Graph G, int v) {
        //把v顶点标识为已经搜索
        marked[v] = true;
        //顶点v进入队列
        waitSearch.enqueue(v);
        //相通顶点数量+1
        count++;

        //通过循环，如果队列不为空，则从队列中弹出
        while (!waitSearch.isEmpty()) {
            Integer wait = waitSearch.dequeue();

            //遍历wait的邻接表
            for (Integer w : G.adj(wait)) {
                if (!marked[w]) {
                    marked[w] = true;
                    waitSearch.enqueue(w);
                    count++;
                }
            }
        }
    }

    //判断w顶点与s顶点是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    //获取与顶点s相通的所有顶点总数
    public int count() {
        return count;
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.BreadthFirstSearch;
import cn.test.algorithm.datastruct.Graph;

public class BreadthFirstSearchTest {
    public static void main(String[] args) {
        //准备图
        Graph graph = new Graph(13);
        graph.addEdge(0, 5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(0, 6);
        graph.addEdge(5, 3);
        graph.addEdge(5, 4);
        graph.addEdge(3, 4);
        graph.addEdge(4, 6);

        graph.addEdge(7, 8);

        graph.addEdge(9, 10);
        graph.addEdge(9, 11);
        graph.addEdge(9, 12);
        graph.addEdge(11, 12);

        //准备深度优先对象
        BreadthFirstSearch breadthFirstSearch = new BreadthFirstSearch(graph, 0);

        System.out.println("顶点数量："+breadthFirstSearch.count());

        System.out.println("测试顶点0和顶点5是否相通"+breadthFirstSearch.marked(5));
        System.out.println("测试顶点0和顶点7是否相通"+breadthFirstSearch.marked(7));
    }
}

测试结果

顶点数量：7
测试顶点0和顶点5是否相通true
测试顶点0和顶点7是否相通false

4.15.5、路径查找

如果我们要从一个顶点到另一个顶点看是否存在一条路径？如果存在，请找出这条路径。

例如上图查找顶点0到顶点4的路径用红色标识出来，我们可以把该路径表示为0-2-3-4。这里是无向图，所以我们只需要找出一条路径即可。

API设计

类名	DepthFirstPaths
构造函数	DepthFirstPaths(Graph G,int s)：构造深度优先搜索对象，使用深度优先搜索找出图G中起到为s的所有路径
成员变量	private boolean[] marked：索引表示顶点，值表示当前顶点是否已经被搜索 private int s：起点 private int[] edgeTo：索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
成员方法	private void dfs(Graph G,int v)：使用深度优先搜索找到G图中v顶点的所有相邻顶点 public boolean hasPathTo(int v)：判断v顶点与s顶点是否存在路径 public Stack\ pathTo(int v)：找出从起点s到顶点v的路径(就是该路径经过的顶点)

实现类

package cn.test.algorithm.datastruct;

public class DepthFirstPaths {

    private boolean[] marked;

    private int s;

    private int[] edgeTo;

    public DepthFirstPaths(Graph G, int s) {
        //初始marked数组
        marked = new boolean[G.V()];
        //初始化起点
        this.s = s;
        //初始edgeTo数据
        edgeTo = new int[G.V()];

        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        //遍历v的邻接表，拿到每一个子结点，继续递归搜索
        for (Integer w : G.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;//达到顶点w的路径上的最后一个顶点是v
                dfs(G, w);
            }
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Stack<Integer> pathTo(int v) {
        if (!hasPathTo(v)){
            return null;
        }
        //存储路径对象
        Stack<Integer> path = new Stack<>();
        while (v != s){
            path.push(v);
            v = edgeTo[v];
        }
        path.push(v);
        return path;
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.DepthFirstPaths;
import cn.test.algorithm.datastruct.Graph;
import cn.test.algorithm.datastruct.Stack;

public class DepthFirstPathsTest {
    public static void main(String[] args) {
        //准备图
        Graph graph = new Graph(6);

        graph.addEdge(0,1);
        graph.addEdge(0,2);
        graph.addEdge(0,5);

        graph.addEdge(2,3);
        graph.addEdge(2,4);

        graph.addEdge(3,4);
        graph.addEdge(3,5);

        DepthFirstPaths depthFirstPaths = new DepthFirstPaths(graph, 0);
        Stack<Integer> path = depthFirstPaths.pathTo(4);
        for (Integer w : path) {
            System.out.print(w+"-");
        }
    }
}

测试结果

0-2-3-4-

4.15.6、加权无向图

加权无向图是一种以每条边关联一个权重值或成本的图模型，这种图能够自然地表示许多应用。如顶点与顶点之间可以表示一个时间、路程、金额等，我们从中可以找到从一个顶点到另一个顶点的成本最少的一条路径。

4.15.6.1、加权无向图的边API设计和实现

加权无向图中的边我们就不能简单用v-w两个顶点来表示了，而是必须要给边关联一个权重值，因此我们需要使用对象来描述一条边。

API设计

类名	Edge implements Comparable\
构造方法	Edge(int v,int w,double weight)：通过顶点v和w以及权重weight值构造一个边对象
成员变量	private final int v：顶点1 private final int w：顶点2 private final double weight：当前边的权重
成员方法	public double weight()：权重值获取 public int either()：获取边上的一个点 public int other(int vertex)：获取边上除了顶点vertex外的另一个顶点 public int compareTo(Edge that)：比较当前边和参数that边的权重，如果当前边的权重大，返回1，如果一样大返回0，如果小就返回-1

实现类

package cn.test.algorithm.datastruct;

public class Edge implements Comparable<Edge> {
    private final int v;//顶点1
    private final int w;//顶点2
    private final double weight;//权重

    public Edge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    //获取边的权重值
    public double weight() {
        return weight;
    }

    //获取边上的一个点
    public int either() {
        return v;
    }

    //获取边上处理顶点vertex外的另一个顶点
    public int other(int vertex) {
        return v == vertex ? w : v;
    }

    @Override
    public int compareTo(Edge that) {
        //使用一个变量记录比较结果
        int cmp;
        if (weight > that.weight) {
            cmp = 1;
        } else if (weight < that.weight) {
            cmp = -1;
        } else {
            cmp = 0;
        }
        return cmp;
    }
}

4.15.6.2、加权无向图的API设计和实现

API设计

类名	EdgeWeightedGraph
构造方法	EdgeWeightedGraph(int V)：创建一个包含V个顶点的空加权无向图
成员变量	private final int V：记录顶点数量 private int E：记录边数量 private Queue\[]：邻接表
成员方法	public int V()：获取图中的顶点数量 public int E()：获取图中边的数量 public void addEdge(Edge e)：向图中添加一条边e public Queue\ adj(int v)：获取和顶点v相连的所有边 public Queue\ edges()：获取加权无向图的所有边

实现类

package cn.test.algorithm.datastruct;

public class EdgeWeightedGraph {
    //顶点数量
    private final int V;

    //记录边的数量
    private int E;

    //邻接表
    private Queue<Edge>[] adj;

    public EdgeWeightedGraph(int V) {
        //初始化顶点数量
        this.V = V;
        //初始化边的数量
        this.E = 0;
        //初始邻接表
        this.adj = new Queue[V];
        for (int i = 0; i < adj.length; i++) {
            this.adj[i] = new Queue<Edge>();
        }
    }

    //获取顶点的数量
    public int V() {
        return this.V;
    }

    //获取边的数量
    public int E() {
        return this.E;
    }

    //向加权无向图中添加一条边
    public void addEdge(Edge e) {
        int v = e.either();
        int w = e.other(v);

        adj[v].enqueue(e);
        adj[w].enqueue(e);

        E++;
    }

    //获取和顶点v关联的所有边
    public Queue<Edge> adj(int v) {
        return adj[v];
    }


    //获取加权无向图所有的边
    public Queue<Edge> edges() {
        //创建一个队列对象，存储所有的边
        Queue<Edge> allEdges = new Queue<>();

        //需要遍历图中每一个顶点，找到该顶点的邻接表，邻接表存储了该顶点的管理的每一条边
        for (int v = 0; v < adj.length; v++) {
            for (Edge e : adj(v)) {
                //因为是无向图，所以同一条边同时会出现在两个顶点的邻接表中，我们只需要激励一次
                //所以我们只需要对比两个顶点的大小，如果小于就存这条边，否则就不存储
                if (e.other(v) < v) {
                    allEdges.enqueue(e);
                }
            }
        }
        return allEdges;
    }
}

4.15.7、最小生成树

4.15.7.1、最小生成树的定义和约定

定义：图的生成树是它的一棵含有其所有顶点的无环连通子图，一幅加权无向图的最小生成树它的一棵权重值最小的生成树。

约定：

• 只考虑连通图。如果图不是连通图，那么分别计算每个连通子图的最小生成树，合并到一起称为最小生成森林。
• 所有边的权重各不相同。如果不同的边的权重可以相同，那么一幅图的最小生成树就可能不唯一了，虽然我们的算法可以处理这样的情况，但是为了好理解，还是约定所有边的权重不一样。

4.15.7.2、最小生成树的原理

树的性质：

1、用一条边连接数中的任意两个顶点都会产生一个新的环

2、从树中删除任意一条边，将会得到两棵独立的树

切分定理：

要从一幅连通图中找出该图中的最小生成树，需要通过切分定理完成。

切分：将图的所有顶点按照某些规则分为两个非空且没有交集的集合。

横切边：连接两个属于不同集合的顶点的边称之为横切边。

例如将图中的顶点分为两个集合，灰色顶点属于一个集合，白色顶点属于另一个集合，那么效果如下：

切分定理：在一幅加权图中，给定的任意的切分，它的横切边的权重最小者必然属于图中的最小生成树。

注意：一次切分产生的多个横切边中，权重最小的边不一定是所有横切边中唯一属于图的最小生成树的边。

4.15.7.3、贪心算法

贪心算法是计算图中最小生成树的基础算法，它的基本原理就是切分定理。使用切分定理找到最小生成树的一条边，不断的重复知道找到最小生成树的所有边。如果图有V个顶点，那么需要找到V-1条边，就可以表示该图的最小生成树。

计算图的最小生成树的算法有很多中，但是这些算法都可以看做是贪心算法的一种特殊情况，这些算法的不同之处在于保存切分和判断权重最小的横切边方式。

4.15.7.4、Prim算法

Prim算法就是它的每一步都会为一棵生成中的树添加一条边。一开始这棵树只有一个顶点，然后回向它添加v-1条边，每次总是将下一条连接数中的顶点与不在树中的顶点且权重最小的边加入到树中。

Prim算法的切分规则：

把最小生成树中的顶点看着是一个集合，把不在最小生成树中的顶点看做是另外一个集合。

Prim算法API设计

类名	PrimMST
构造方法	PrimMST(EdgeWeightedGraph G)：根据一幅加权无向图，创建最小生成树计算对象
成员变量	private Edge[] edgeTo：索引表示顶点，值表示当前顶点与最小生成树之间的最短边 private double[] distTo[]：索引表示顶点，值表示当前顶点和最小生成树之间的最短边的权重 private boolean[] marked：索引表示顶点，如果当前顶点已经在树中，则值为true，否则为false private IndexMinPriorityQueue\ pq：存放树中的顶点与非树中的顶点之间的有效横切边
成员方法	private void visit(EdgeWeightedGraph G,int v)：将顶点v添加到最小生成树中，并更新数据 public Queue\ edges()：获取最小生成树的所有边

实现类

package cn.test.algorithm.datastruct;

public class PrimMST {
    //索引表示顶点，值表示当前顶点与最小生成树之间的最短边
    private Edge[] edgeTo;

    //索引表示顶点，值表示当前顶点和最小生成树之间的最短边的权重
    private double[] distTo;

    //索引表示顶点，如果当前顶点已经在树中，则值为true，否则为false
    private boolean[] marked;

    //存放树中的顶点与非树中的顶点之间的有效横切边
    private IndexMinPriorityQueue<Double> pq;


    public PrimMST(EdgeWeightedGraph G) {
        //初始化edgeTo
        this.edgeTo = new Edge[G.V()];

        //初始化distTo
        this.distTo = new double[G.V()];
        for (int i = 0; i < this.distTo.length; i++) {
            this.distTo[i] = Double.POSITIVE_INFINITY;//最大值
        }

        //初始化marked
        this.marked = new boolean[G.V()];

        //初始pq
        this.pq = new IndexMinPriorityQueue<Double>(G.V());

        //默认让顶点0进入到树中，树中只有一个顶点0，因此0顶点默认没有和其他顶点相连，所以distTo对应位置应该是0
        distTo[0] = 0.0;
        pq.insert(0, 0.0);

        //遍历索引最小优先队列
        while (!pq.isEmpty()) {
            visit(G, pq.delMin());
        }
    }

    //把顶点v添加到最小生成树中，并更新数据
    private void visit(EdgeWeightedGraph G, int v) {
        //把顶点v添加到最小生成树中
        marked[v] = true;
        //更新数据
        for (Edge e : G.adj(v)) {
            //获取e边的另外一个顶点
            int w = e.other(v);
            //判断另外一个顶点是否已经在树中，在就不做处理，不在就更新数据
            if (marked[w]) {
                continue;
            }
            //判断边e的权重是否小于从w顶点到树中已经存在的最小边的权重
            if (e.weight() < distTo[w]) {
                //更新数据
                edgeTo[w] = e;

                distTo[w] = e.weight();

                if (pq.contains(w)) {
                    pq.changeItem(w, e.weight());
                } else {
                    pq.insert(w, e.weight());
                }
            }
        }
    }

    //获取最小生成树的所以边
    public Queue<Edge> edges() {
        Queue<Edge> allEdges = new Queue<>();
        for (int i = 0; i < edgeTo.length; i++) {
            if (edgeTo[i] != null) {
                allEdges.enqueue(edgeTo[i]);
            }
        }
        return allEdges;
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.Edge;
import cn.test.algorithm.datastruct.EdgeWeightedGraph;
import cn.test.algorithm.datastruct.PrimMST;
import cn.test.algorithm.datastruct.Queue;

public class PrimMSTTest {
    public static void main(String[] args) {
        //准备一幅加权无向图
        EdgeWeightedGraph G = new EdgeWeightedGraph(16);

        G.addEdge(new Edge(4, 5, 0.35));
        G.addEdge(new Edge(4, 7, 0.37));
        G.addEdge(new Edge(5, 7, 0.28));
        G.addEdge(new Edge(0, 7, 0.16));
        G.addEdge(new Edge(1, 5, 0.32));
        G.addEdge(new Edge(0, 4, 0.38));
        G.addEdge(new Edge(2, 3, 0.17));
        G.addEdge(new Edge(1, 7, 0.19));
        G.addEdge(new Edge(0, 2, 0.26));
        G.addEdge(new Edge(1, 2, 0.36));
        G.addEdge(new Edge(1, 3, 0.29));
        G.addEdge(new Edge(2, 7, 0.34));
        G.addEdge(new Edge(6, 2, 0.40));
        G.addEdge(new Edge(3, 6, 0.52));
        G.addEdge(new Edge(6, 0, 0.58));
        G.addEdge(new Edge(6, 4, 0.93));

        //创建PrimMST对象计算最小生成树
        PrimMST prim = new PrimMST(G);

        //获取最小生成树的所有边
        Queue<Edge> edges = prim.edges();
        //遍历打印所以边
        for (Edge e : edges) {
            int v = e.either();
            int w = e.other(v);

            double weight = e.weight();

            System.out.println(v + " " + w + " " + weight);
        }

    }
}

测试结果

1 7 0.19
0 2 0.26
2 3 0.17
4 5 0.35
5 7 0.28
6 2 0.4
0 7 0.16

4.15.7.5、kruskal算法

kruskal算法是计算一幅加权无向图的最小生成树的另外一种算法，它的思想是按照边的权重从小到大处理他们，将边加入最小生成树中，加入的边不会与已经加入的最小生成树的边构成环，直到树中包含V-1条边为止。

kruskal算法和prim算法的区别：

Prim算法是一条边一条边的构造最小生成，每一步都为一棵树添加一条边。kruskal算法构造最小生成树也是一条边一条边的构造，但它的切分规则是不一样的。它每一次寻找的边会连接一片森林中的两棵树。如果一幅加权无向图由V个顶点组成，初始化情况下每个顶点都构成一棵独立的树，则V个顶点对应V棵树，则V个顶点对应V棵树，组成一片森林，kruskal算法每一次处理都会将两棵树进行合并为一棵树，知道整个森林中只剩下一棵树为止。

kruskal算法API设计

类名	KruskalMST
构造方法	KruskalMST(EdgeWeightedGraph G)：根据一幅加权无向图，创建最小生成树计算对象
成员变量	private Queue\ mst：保存最小生成树的素所有边 private UF_Tree_Weighted uf：索引表示顶点，使用uf.connect(v,w)：判断顶点v和w是否在同一颗树中，使用功能uf.union(v,w)可以把顶点v和w所在的树合并 private MinPriorityQueue\ pq：存储图中的所有边，使用功能最小优先队列，对边按照权重进行排序
成员方法	public Queue\ edges()：获取最小生成树的所有边

实现类

package cn.test.algorithm.datastruct;

public class KruskalMST {
    //保存最小生成树的所有边
    private Queue<Edge> mst;

    //索引表示顶点，使用uf.connect(v,w)：判断顶点v和w是否在同一颗树中，使用功能uf.union(v,w)可以把顶点v和w所在的树合并
    private UF_Tree_Weighted uf;

    //存储图中的所有边，使用功能最小优先队列，对边按照权重进行排序
    private MinPriorityQueue<Edge> pq;


    public KruskalMST(EdgeWeightedGraph G) {
        //初始化mst
        this.mst = new Queue<Edge>();
        //初始化uf
        this.uf = new UF_Tree_Weighted(G.V());
        //初始化pq
        this.pq = new MinPriorityQueue<Edge>(G.E() + 1);
        //把图中所有的边存储到pq中
        for (Edge e : G.edges()) {
            pq.insert(e);
        }

        //遍历pq队列，拿到最小权重的边，进行处理
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            //找到权重最小的边
            Edge e = pq.delMin();
            //找到改边的两个顶点
            int v = e.either();
            int w = e.other(v);
            //如果不在同一棵树就合并，在就不合并
            if (uf.connected(v, w)) {
                continue;
            }

            //合并两棵树
            uf.union(v, w);

            //添加到队列
            mst.enqueue(e);
        }
    }

    //获取最小生成树的所有边
    public Queue<Edge> edges() {
        return mst;
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.*;

public class KruskalMSTTest {
    public static void main(String[] args) {
        //准备一幅加权无向图
        EdgeWeightedGraph G = new EdgeWeightedGraph(16);

        G.addEdge(new Edge(4, 5, 0.35));
        G.addEdge(new Edge(4, 7, 0.37));
        G.addEdge(new Edge(5, 7, 0.28));
        G.addEdge(new Edge(0, 7, 0.16));
        G.addEdge(new Edge(1, 5, 0.32));
        G.addEdge(new Edge(0, 4, 0.38));
        G.addEdge(new Edge(2, 3, 0.17));
        G.addEdge(new Edge(1, 7, 0.19));
        G.addEdge(new Edge(0, 2, 0.26));
        G.addEdge(new Edge(1, 2, 0.36));
        G.addEdge(new Edge(1, 3, 0.29));
        G.addEdge(new Edge(2, 7, 0.34));
        G.addEdge(new Edge(6, 2, 0.40));
        G.addEdge(new Edge(3, 6, 0.52));
        G.addEdge(new Edge(6, 0, 0.58));
        G.addEdge(new Edge(6, 4, 0.93));

        //创建PrimMST对象计算最小生成树
        KruskalMST prim = new KruskalMST(G);

        //获取最小生成树的所有边
        Queue<Edge> edges = prim.edges();
        //遍历打印所以边
        for (Edge e : edges) {
            int v = e.either();
            int w = e.other(v);

            double weight = e.weight();

            System.out.println(v + " " + w + " " + weight);
        }
    }
}

测试结果

0 7 0.16
2 3 0.17
1 7 0.19
0 2 0.26
5 7 0.28
4 5 0.35
6 2 0.4