算法|15.图相关算法

矫情吗；* 2024-03-16 10:42 5阅读 0赞

## 算法|15.图相关算法 ##

### 基本定义 ###

package graph;
    
    import java.util.ArrayList;
    
    public class Node {
        
        public int value;
        public int in;
        public int out;
        public ArrayList<Node> nexts;
        public ArrayList<Edge> edges;
    
        public Node(int value){
        
            this.value=value;
            in=0;
            out=0;
            nexts=new ArrayList<>();
            edges=new ArrayList<>();
        }
    }

package graph;
    
    public 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;
        }
    }

package graph;
    
    import java.util.HashMap;
    import java.util.HashSet;
    
    public class Graph {
        
        public HashMap<Integer,Node> nodes;
        public HashSet<Edge> edges;
        public Graph(){
        
            nodes=new HashMap<>();
            edges=new HashSet<>();
        }
    }

### BFS ###

package graph;
    
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class BFS {
        
        public static void bfs(Node start){
        
            if(start==null){
        
                return ;
            }
            Queue<Node> queue=new LinkedList<>();
            HashSet<Node> set=new HashSet<>();
            queue.add(start);
            set.add(start);
            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 ###

package graph;
    
    import java.util.HashSet;
    import java.util.Stack;
    
    public class 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.contains(next)){
        
                        stack.push(cur);
                        stack.push(next);
                        set.add(next);
                        System.out.println(next.value);
                        break;
                    }
                }
            }
        }
    }

### 霍夫曼树 ###

package graph;
    
    import java.util.PriorityQueue;
    
    public class HuffmanTree {
        public static void constructHuffmanTree(int[] arr){
            //默认升序，小根堆即可
            PriorityQueue<Integer> pq=new PriorityQueue<>();
            for (int i = 0; i < arr.length; i++) {
                pq.add(arr[i]);
            }
            while(pq.size()>1){
                int cur=pq.poll()+pq.poll();
                pq.add(cur);
            }
            //截至目前构造完毕
        }
    }

### 迪杰特斯拉 ###

package graph;
    
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Map;
    
    public class Dijkstra {
        
        public static HashMap<Node, Integer> dijkstra1(Node from) {
        
            HashMap<Node, Integer> distanceMap = new HashMap<>();
            distanceMap.put(from, 0);
            // 打过对号的点
            HashSet<Node> selectedNodes = new HashSet<>();
            Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
            while (minNode != null) {
        
                //  原始点  ->  minNode(跳转点)   最小距离distance
                int distance = distanceMap.get(minNode);
                for (Edge edge : minNode.edges) {
        
                    Node toNode = edge.to;
                    if (!distanceMap.containsKey(toNode)) {
        
                        distanceMap.put(toNode, distance + edge.weight);
                    } else {
         // toNode
                        distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
                    }
                }
                selectedNodes.add(minNode);
                minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
            }
            return distanceMap;
        }
    
        public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
        
            Node minNode = null;
            int minDistance = Integer.MAX_VALUE;
            for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
        
                Node node = entry.getKey();
                int distance = entry.getValue();
                if (!touchedNodes.contains(node) && distance < minDistance) {
        
                    minNode = node;
                    minDistance = distance;
                }
            }
            return minNode;
        }
    
        public static class NodeRecord {
        
            public Node node;
            public int distance;
    
            public NodeRecord(Node node, int distance) {
        
                this.node = node;
                this.distance = distance;
            }
        }
    
        public static class NodeHeap {
        
            private Node[] nodes; // 实际的堆结构
            // key 某一个node， value 上面堆中的位置
            private HashMap<Node, Integer> heapIndexMap;
            // key 某一个节点， value 从源节点出发到该节点的目前最小距离
            private HashMap<Node, Integer> distanceMap;
            private int size; // 堆上有多少个点
    
            public NodeHeap(int size) {
        
                nodes = new Node[size];
                heapIndexMap = new HashMap<>();
                distanceMap = new HashMap<>();
                size = 0;
            }
    
            public boolean isEmpty() {
        
                return size == 0;
            }
    
            // 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
            // 判断要不要更新，如果需要的话，就更新
            public void addOrUpdateOrIgnore(Node node, int distance) {
        
                if (inHeap(node)) {
        
                    distanceMap.put(node, Math.min(distanceMap.get(node), distance));
                    insertHeapify(heapIndexMap.get(node));
                }
                if (!isEntered(node)) {
        
                    nodes[size] = node;
                    heapIndexMap.put(node, size);
                    distanceMap.put(node, distance);
                    insertHeapify(size++);
                }
            }
    
            public NodeRecord pop() {
        
                NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
                swap(0, size - 1);
                heapIndexMap.put(nodes[size - 1], -1);
                distanceMap.remove(nodes[size - 1]);
                // free C++同学还要把原本堆顶节点析构，对java同学不必
                nodes[size - 1] = null;
                heapify(0, --size);
                return nodeRecord;
            }
    
            private void insertHeapify(int index) {
        
                while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
        
                    swap(index, (index - 1) / 2);
                    index = (index - 1) / 2;
                }
            }
    
            private void heapify(int index, int size) {
        
                int left = index * 2 + 1;
                while (left < size) {
        
                    int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
                            ? left + 1
                            : left;
                    smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
                    if (smallest == index) {
        
                        break;
                    }
                    swap(smallest, index);
                    index = smallest;
                    left = index * 2 + 1;
                }
            }
    
            private boolean isEntered(Node node) {
        
                return heapIndexMap.containsKey(node);
            }
    
            private boolean inHeap(Node node) {
        
                return isEntered(node) && heapIndexMap.get(node) != -1;
            }
    
            private void swap(int index1, int index2) {
        
                heapIndexMap.put(nodes[index1], index2);
                heapIndexMap.put(nodes[index2], index1);
                Node tmp = nodes[index1];
                nodes[index1] = nodes[index2];
                nodes[index2] = tmp;
            }
        }
    
        // 改进后的dijkstra算法
        // 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
        public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
        
            NodeHeap nodeHeap = new NodeHeap(size);
            nodeHeap.addOrUpdateOrIgnore(head, 0);
            HashMap<Node, Integer> result = new HashMap<>();
            while (!nodeHeap.isEmpty()) {
        
                NodeRecord record = nodeHeap.pop();
                Node cur = record.node;
                int distance = record.distance;
                for (Edge edge : cur.edges) {
        
                    nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
                }
                result.put(cur, distance);
            }
            return result;
        }
    
    }

### 克鲁斯克尔 ###

package graph;
    
    import java.util.*;
    
    public class Kruskal {
        
        // Union-Find Set
        public static class UnionFind {
        
            // key 某一个节点， value key节点往上的节点
            private HashMap<Node, Node> fatherMap;
            // key 某一个集合的代表节点, value key所在集合的节点个数
            private HashMap<Node, Integer> sizeMap;
    
            public UnionFind() {
        
                fatherMap = new HashMap<Node, Node>();
                sizeMap = new HashMap<Node, Integer>();
            }
    
            public void makeSets(Collection<Node> nodes) {
        
                fatherMap.clear();
                sizeMap.clear();
                for (Node node : nodes) {
        
                    fatherMap.put(node, node);
                    sizeMap.put(node, 1);
                }
            }
    
            private Node findFather(Node n) {
        
                Stack<Node> path = new Stack<>();
                while(n != fatherMap.get(n)) {
        
                    path.add(n);
                    n = fatherMap.get(n);
                }
                while(!path.isEmpty()) {
        
                    fatherMap.put(path.pop(), n);
                }
                return n;
            }
    
            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 aDai = findFather(a);
                Node bDai = findFather(b);
                if (aDai != bDai) {
        
                    int aSetSize = sizeMap.get(aDai);
                    int bSetSize = sizeMap.get(bDai);
                    if (aSetSize <= bSetSize) {
        
                        fatherMap.put(aDai, bDai);
                        sizeMap.put(bDai, aSetSize + bSetSize);
                        sizeMap.remove(aDai);
                    } else {
        
                        fatherMap.put(bDai, aDai);
                        sizeMap.put(aDai, aSetSize + bSetSize);
                        sizeMap.remove(bDai);
                    }
                }
            }
        }
    
    
        public static class EdgeComparator implements Comparator<Edge> {
        
    
            @Override
            public int compare(Edge o1, Edge o2) {
        
                return o1.weight - o2.weight;
            }
    
        }
    
        public static Set<Edge> kruskalMST(Graph graph) {
        
            UnionFind unionFind = new UnionFind();
            unionFind.makeSets(graph.nodes.values());
            // 从小的边到大的边，依次弹出，小根堆！
            PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
            for (Edge edge : graph.edges) {
         // M 条边
                priorityQueue.add(edge);  // O(logM)
            }
            Set<Edge> result = new HashSet<>();
            while (!priorityQueue.isEmpty()) {
         // M 条边
                Edge edge = priorityQueue.poll(); // O(logM)
                if (!unionFind.isSameSet(edge.from, edge.to)) {
         // O(1)
                    result.add(edge);
                    unionFind.union(edge.from, edge.to);
                }
            }
            return result;
        }
    }

### 普瑞姆 ###

package graph;
    
    import java.util.Comparator;
    import java.util.HashSet;
    import java.util.PriorityQueue;
    import java.util.Set;
    
    public class Prim {
        
        public static class EdgeComparator implements Comparator<Edge> {
        
    
            @Override
            public int compare(Edge o1, Edge o2) {
        
                return o1.weight - o2.weight;
            }
    
        }
    
        public static Set<Edge> primMST(Graph graph) {
        
            // 解锁的边进入小根堆
            PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
    
            // 哪些点被解锁出来了
            HashSet<Node> nodeSet = new HashSet<>();
    
    
    
            Set<Edge> result = new HashSet<>(); // 依次挑选的的边在result里
    
            for (Node node : graph.nodes.values()) {
         // 随便挑了一个点
                // node 是开始点
                if (!nodeSet.contains(node)) {
        
                    nodeSet.add(node);
                    for (Edge edge : node.edges) {
         // 由一个点，解锁所有相连的边
                        priorityQueue.add(edge);
                    }
                    while (!priorityQueue.isEmpty()) {
        
                        Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边
                        Node toNode = edge.to; // 可能的一个新的点
                        if (!nodeSet.contains(toNode)) {
         // 不含有的时候，就是新的点
                            nodeSet.add(toNode);
                            result.add(edge);
                            for (Edge nextEdge : toNode.edges) {
        
                                priorityQueue.add(nextEdge);
                            }
                        }
                    }
                }
                // break;
            }
            return result;
        }
    
        // 请保证graph是连通图
        // graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路
        // 返回值是最小连通图的路径之和
        public static int prim(int[][] graph) {
        
            int size = graph.length;
            int[] distances = new int[size];
            boolean[] visit = new boolean[size];
            visit[0] = true;
            for (int i = 0; i < size; i++) {
        
                distances[i] = graph[0][i];
            }
            int sum = 0;
            for (int i = 1; i < size; i++) {
        
                int minPath = Integer.MAX_VALUE;
                int minIndex = -1;
                for (int j = 0; j < size; j++) {
        
                    if (!visit[j] && distances[j] < minPath) {
        
                        minPath = distances[j];
                        minIndex = j;
                    }
                }
                if (minIndex == -1) {
        
                    return sum;
                }
                visit[minIndex] = true;
                sum += minPath;
                for (int j = 0; j < size; j++) {
        
                    if (!visit[j] && distances[j] > graph[minIndex][j]) {
        
                        distances[j] = graph[minIndex][j];
                    }
                }
            }
            return sum;
        }
    
        public static void main(String[] args) {
        
            System.out.println("hello world!");
        }
    
    }

### 拓扑排序 ###

package graph;
    
    import java.util.*;
    
    public class TopologySort {
        
        public static List<Node> sortedTopology(Graph graph){
        
            //剩余入度
            HashMap<Node,Integer> inMap=new HashMap<>();
            //入度为0进入的队列
            Queue<Node> zeroQueue=new LinkedList<>();
            for (Node node:graph.nodes.values()) {
        
                inMap.put(node,node.in);
                if(node.in==0){
        
                    zeroQueue.add(node);
                }
            }
            List<Node> result=new ArrayList<>();
            while(!zeroQueue.isEmpty()){
        
                Node cur=zeroQueue.poll();
                result.add(cur);
                for (Node next:cur.nexts) {
        
                    inMap.put(next,inMap.get(next)-1);
                    if(inMap.get(next)==0){
        
                        zeroQueue.add(next);
                    }
                }
            }
            return result;
        }
    }