图的常见算法

图的表示方式展开目录

图是由一系列点和边的集合构成的，一般有邻接矩阵和邻接表两种表示方式，c/c++ 可以看我的这篇文章：搜索 (1)

这篇文章主要讲 java 语言中图的相关算法。首先看一下图结构的代码：

class Node {//点集
    public int value;
    public int in;//入度
    public int out;//出度
    public ArrayList<Node> nexts;//邻居结点(以我为from的情况下)
    public ArrayList<Edge> edges;//从我出发发散出的边集合
    
    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

class Edge {//边集
    public int weight;//权重
    public Node from;//起始结点
    public Node to;//终止结点
    
    public Edge(int weight,Node from,Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

class Graph {//图
    public HashMap<Integer,Node> nodes;
    public HashSet<Edge> edges;
    
    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

构建一个图：

public class GraphGenerator {
    public static Graph createGraph(Integer[][] matrix) {
        /* matrix = {
         *  {weight,from,to}
         *  {weight,from,to}
         *  ...
         *  ...
         *  }
         */
        Graph graph = new Graph();
        for(int i = 0;i < matrix.length;i++) {
            Integer weight = matrix[i][0];
            Integer from = matrix[i][1];
            Integer to = matrix[i][2];
            if(!graph.nodes.containsKey(from))//图中不含有该点，就创建改点
                graph.nodes.put(from,new Node(from));
            if(!graph.nodes.containsKey(to))
                graph.nodes.put(to,new Node(to));
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge newEdge = new Edge(weight,fromNode,toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }
}

一般来说，图的题目都会给这样的输入，一个 n 行 3 列的二维矩阵，每行都代表一个输入，第一列代表边的权重，第二列代表起始点，第三列代表终止点，比方说 [2,1,2] 就表示从 1 结点出发到 2 结点连一条边，该边权重为 2

BFS—— 广度优先搜索展开目录

广搜一般由队列完成，广搜的顺序与子节点到初始节点的距离有关，离初始节点越近的子节点会更早被访问

public static void bfs(Node node) {
    if(node == null)
        return;
    Queue<Node> queue = new LinkedList<>();
    HashSet<Node> set = new HashSet<>();
    queue.add(node);
    set.add(node);
    while(!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.println(cur.value);
        for(Node next:cur.nexts) {
            if(!set.contains(next)) {
                set.add(next);
                queue.add(next);
            }
        }
    }
}

DFS—— 深度优先搜索展开目录

深搜一般由栈完成，从一个结点出发，一直沿着这个结点的子结点遍历，直到没有点可以走了就开始出栈，出栈操作也就相当于 “回溯”

public static void dfs(Node node) {
    if(node == null)
        return;
    Stack<Node> stack = new Stack<>();
    HashSet<Node> set = new HashSet<>();
    stack.add(node);
    set.add(node);
    System.out.println(node.value);
    while(!stack.isEmpty()) {
        Node cur = stack.pop();
        for(Node next:cur.nexts) {
            if(!set.isEmpty()) {
                stack.push(cur);
                stack.push(next);
                set.add(next);
                System.out.println(next.value);
                break;
            }
        }
    }
}

图的拓扑排序展开目录

图的拓扑排序以下图来举例，假设你要学课程 A，但是课程 A 有先导课，必须上完先导课才能上 A，因此你必须先上 BCD，但是由于 BD 也有先导课 K，所以必须先上 K。那么正确的上课顺序就该是 KC、BD、A，至于究竟是先上 K 还是先上 C，这个顺序无所谓
说一下拓扑排序的算法流程：找到入度为 0 的结点，打印，然后删掉该结点，直到图中结点为空

//dirceted graph and no loop
public static List<Node> sortedTopology(Graph graph) {
    HashMap<Node,Integer> inMap = new HashMap<>();
    Queue<Node> zeroInQueue = new LinkedList<>();
    for(Node node : graph.nodes.values()) {//遍历所有的点
        inMap.put(node,node.in);//把每个点以及入度登记在inMap里
        if(node.in == 0)
            zeroInQueue.add(node);//入度为0的点进队
    }
    List<Node> res = new ArrayList<>();
    while(!zeroInQueue.isEmpty()) {
        Node cur = zeroInQueue.poll();//从入度为0的点的队列中拿出一个
        res.add(cur);
        for(Node next : cur.nexts) {//遍历这个结点的所有子结点
            inMap.put(next,inMap.get(next) - 1);//子结点的入度减1，相当于删除from点
            if(inMap.get(next) == 0)
                zeroInQueue.add(next);
        }
    }
    return res;
}

图的最小生成树展开目录

图的最小生成树算法用于无向图，只选择图中的某些边，达到整体边的权重加起来是最小的，并且各个点之间是连通的，连通的意思是假设 [1,2] 之间有条边，[2,3] 之间有条边，那么 [1,3] 之间就是连通的，图的最小生成树算法有两个，分别是 K 算法和 P 算法，他俩产生的结果都是一样的，只不过决策的过程不一样。

K 算法展开目录

以上面的图为例，K 算法的思想是以边进行考虑，优先选择小权重的边。首先，选择 [1,2] 之间权重为 1 的边，然后选择 [2,3] 之间权重为 1 的边，然后考虑 [1,3] 之间权重为 2 的边，但是如果选了，[1,3] 之间就会构成回路，因此不选，然后再看 [1,4] 之间权重为 2 的边，选上，最后结束，[1,2,3,4] 都是连通的

利用并查集，初始时每个结点自己是一个集合，每次选完边后，更新集合，判断宣布选择某条边，就看该点所在的集合是否已经包含在当前的集合内，如果包含，就不选，如果不包含就选

public static class UnionFind {//并查集
    private HashMap<Node,Node> fatherMap;
    private HashMap<Node,Integer> rankMap;
        
    public UnionFind() {
        fatherMap = new HashMap<Node,Node>();
        rankMap = new HashMap<Node,Integer>();
    }
        
    private Node findFather(Node n) {
        Node father = fatherMap.get(n);
        if(father != n) 
            father = findFather(father);
        fatherMap.put(n,father);
        return father;
    }
    
    public void makeSets(Collection<Node> nodes) {
        fatherMap.clear();
        rankMap.clear();
        for(Node node : nodes) {
            fatherMap.put(node,node);
            rankMap.put(node,1);
        }
    }
    
    public boolean isSameSet(Node a,Node b) {
        return findFather(a) == findFather(b);
    }
    
    public void union(Node a,Node b) {
        if(a == null || b == null) 
            return;
        Node aFather = findFather(a);
        Node bFather = findFather(b);
        if(aFather != bFather) {
            int aFrank = rankMap.get(aFather);
            int bFrank = rankMap.get(bFather);
            if(aFrank <= bFrank) {
                fatherMap.put(aFather,bFather);
                rankMap.put(bFather,aFrank + bFrank);
            } else {
                fatherMap.put(bFather,aFather);
                rankMap.put(aFather,aFrank + bFrank);
            }
        }
    }
}
    
public static class EdgeComparator implements Comparator<Edge> {
    public int compare(Edge o1,Edge o2) {
        return o1.weight - o2.weight;
    }
}
    
public static Set<Edge> kruskalMST(Graph graph) {//K算法
    UnionFind unionFind = new UnionFind();
    unionFind.makeSets(graph.nodes.values());
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
    for(Edge edge : graph.edges) 
        priorityQueue.add(edge);
    Set<Edge> res = new HashSet<>();
    while(!priorityQueue.isEmpty()) {
        Edge edge = priorityQueue.poll();
        if(!unionFind.isSameSet(edge.from,edge.to)) {
            res.add(edge);
            unionFind.union(edge.from,edge.to);
        }
    }
    return res;
}

P 算法展开目录

P 算法是以点作为考虑，首先随便选一个点 x，和这个点相连的所有的边解锁，找到其中权重最小的边，到达另一个结点 y，和这个 y 结点相连的所有边解锁，再在其中找到全职最小的边（包括上面和 x 相连的所有边）重复下去就能得到答案

public static class EdgeComparator implements Comparator<Edge> {
    public int compare(Edge e1,Edge e2) {
        return e1.weight - e2.weight;
    }
}
    
public static Set<Edge> PrimMST(Graph graph) {
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
    HashSet<Node> set = new HashSet<>();
    Set<Edge> res = new HashSet<>();
    for(Node node : graph.nodes.values()) {
        if(!set.contains(node)) {
            set.add(node);
            for(Edge edge : node.edges) //node的所有的边加入到队列中
                priorityQueue.add(edge);
            while(!priorityQueue.isEmpty()) { 
                Edge edge = priorityQueue.poll();//从队列中弹出一个最小的边
                Node toNode = edge.to;
                if(!set.contains(toNode)) {//toNode如果不在，就加进来
                    set.add(toNode);
                    res.add(edge);
                    for(Edge nextEdge : toNode.edges) //将toNode的所有边加入队列
                        priorityQueue.add(nextEdge);
                }
            }
        }
    }
    return res;
}