经典图算法面试题

001什么是最小生成树算法(Minimum Cost Spanning Tree简称 MST)？

所谓生成树，就是n个点之间连成n-1条边的图形。最小生成树，就是权值（两点间直线的值）之和的最小值。由此可以总结构造最小生成树的要求有：（1）必须只使用该图中的边来构造最小生成树；（2）必须使用且仅使用（n-1）条边来连接图中的n个顶点；（3）不能使用产生回路的边；（4）要求树的（n-1）条边的权值之和是最小的。

002什么是kruskal算法？

Kruskal（克鲁斯卡尔算法）算法是一种用来查找最小生成树的算法。Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。换而言之，Kruskal算法就是基于并查集的贪心算法。

003kruskal算法具体实现？

public static class MySets {
    public HashMap<Node, List<Node>> setMap;
    public MySets(List<Node> nodes) {
        for (Node cur : nodes) {
            List<Node> set = new ArrayList<Node>();
            set.add(cur);
            setMap.put(cur, set);
        }
    }
    public boolean isSameSet(Node from, Node to) {
        List<Node> fromSet = setMap.get(from);
        List<Node> toSet = setMap.get(to);

        return fromSet == toSet;
    }
    public void union(Node from, Node to) {
        List<Node> fromSet = setMap.get(from);
        List<Node> toSet = setMap.get(to);

        for (Node toNode : toSet) {
            fromSet.add(toNode);
            setMap.put(toNode, fromSet);
        }
    }
}

004什么是prim算法？

prim算法 (普里姆算法)我们先初始定义一个顶点u，然后在相邻的所有边中找到最小权值的边 e1，将顶点u链接到初始点c之外的顶点v,之后将顶点v放到c中，并且一直重复知道完成。

005prim算法的具体实现？

思路
1. 准备一个边的小根堆队列priorityQueue、顶点的集合set和要挑选的边的集合result
2. 遍历图的顶点nodes，将随机的一个顶点node放到集合set里面，将顶点node所相连所相连的边入队到小根堆队列priorityQueue。
3. 弹出队列里面最小权重的边，判断这个边的to节点的是不是在set集合里面，如果不在，则将to节点放到set里面，并把这条边存到result里面。再将to顶点所相连所相连的边入队到priorityQueue。周而复始依次迭代。
4. 3步骤之后break，跳出循环。

public static Set<Edge> primMST(Graph graph) {
    // 解锁的边进入小根堆
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
    HashSet<Node> set = new HashSet<>();
    Set<Edge> result = new HashSet<>(); // 依次挑选的的边在result里
    for (Node node : graph.nodes.values()) { // 随便挑了一个点
        // node 是开始点
        if (!set.contains(node)) {
            set.add(node);
            for (Edge edge : node.edges) { // 由一个点，解锁所有相连的边
                 priorityQueue.add(edge);
            }
            while (!priorityQueue.isEmpty()) {
                Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边
                Node toNode = edge.to; // 可能的一个新的点
                if (!set.contains(toNode)) { // 不含有的时候，就是新的点
                    set.add(toNode);
                    result.add(edge);
                    for (Edge nextEdge : toNode.edges) {
                        priorityQueue.add(nextEdge);
                    }
                 }
            }
        }
        break;
    }
    return result;
}