图的表示方式

 图是由一系列点和边的集合构成的,一般有邻接矩阵和邻接表两种表示方式,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;}