圖的常見算法

圖的表示方式

?圖是由一系列點和邊的集合構成的,一般有鄰接矩陣和鄰接表兩種表示方式,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 looppublic 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;}