各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

图的常见算法

August 14, 2018 • Read: 462 • 算法

图的表示方式

图是由一系列点和边的集合构成的,一般有邻接矩阵和邻接表两种表示方式,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;
}
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment