【算法】006_图

标签：Node node 结点 add 算法 006 new public

图的表示

图的表示方法有很多种，如果遇到不同的表示方法，可以转换成自己最常用的那一种

public class Graph {
    public HashMap<Integer, Node> nodes;//点集
    public HashSet<Edge> edges;//边集

    public Graph() {
    }

    public Graph(HashMap<Integer, Node> nodes, HashSet<Edge> edges) {
        this.nodes = nodes;
        this.edges = edges;
    }

}

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;
    }
}

public class Node {
    public int value;//点的值
    public int in;//点的入度
    public int out;//点的出度
    public ArrayList<Node> nextList;//点指向哪些点
    public ArrayList<Edge> edgeList;//点的出边

    public Node(int value){
        this.value = value;
        in = 0;
        out = 0;
        nextList = new ArrayList<>();
        edgeList = new ArrayList<>();
    }
}

public class GraphGenerator {
    public Graph createGraph(Integer[][] matrix){
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            Integer from = matrix[i][0];//出点
            Integer to = matrix[i][1];//入点
            Integer weight = 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.nextList.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edgeList.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }
}

宽度优先遍历BFS

利用队列实现
从源节点开始依次按照宽度进队列，然后弹出
每弹出一个结点，就把该结点所有没有进过队列的邻接点放入队列
直到队列为空

public class Code01_BFS {
    public 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 class Code02_DFS {
    public 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) {
                //只要是没有访问过的结点就访问，一直走到底
                //栈中保存的就是当前的DFS的路径
                if (!set.contains(next)){
                    stack.push(cur);
                    stack.push(next);
                    set.add(next);
                    System.out.println(next.value);
                    break;//访问下一个邻接点
                }
            }
        }
    }
}

拓扑排序算法

适用范围：要求有向图，且有入度为0的结点，且没有环

从第一个结点node出发，访问node
去掉图上的node，同时删除与node的邻接点之间的边，这些邻接点的入度就会减一
然后访问下一个入度为0的结点

public class Code03_TopologySort {
    public List<Node> topologySort(Graph graph){
        //key：某一个node；value：剩余的入度
        HashMap<Node, Integer> inMap = new HashMap<>();
        //保存入度为0的结点
        Queue<Node> zeroInQueue = new LinkedList<>();
        //将所有结点放入哈希表中
        for (Node node : graph.nodes.values()) {
            inMap.put(node, node.in);
            if (node.in == 0){
                zeroInQueue.add(node);
            }
        }
        //拓扑排序的结果依次加入result
        List<Node> result = new ArrayList<>();
        while (!zeroInQueue.isEmpty()){
            Node cur = zeroInQueue.poll();
            result.add(cur);
            //去掉这个入度为0的结点后，它的邻接点的入度也要减一
            for (Node next : cur.nexts) {
                inMap.put(next, inMap.get(next) - 1);//更新
                if (inMap.get(next) == 0){
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
}

kruskal算法

适用范围：要求无向图

作用：生成最小生成树

每次都选择最小的边
选择过程中不能形成环
直到形成了最小生成树

初始时，每个结点单独一个集合：{A},{B},{C},
找到最小的边为2，2连接了A和C，A和C不在同一个集合，于是把他们加入一个集合：{A,C},{B},
考察权值为4的边，发现D和C不在一个集合，合并：{A,C,D},
考察权值为7的边，发现A和B不在一个集合，合并：
考察权值为100的边，形成了环，过

如何判断是否有环：
- 边的两个结点在一个集合，加上这条边之后就会形成环
考察权值为1000的边，形成了环，过
最后选择了权值为2、4、7的三条边

public class Code04_Kruskal {

    public class MySet{
        
        //key：结点；value：结点对应的集合
        public HashMap<Node, List<Node>> setMap;

        public MySet(List<Node> nodes){
            //每个结点对应的集合
            //最开始的时候一个结点一个集合
            for (Node cur : nodes){
                List<Node> set = new ArrayList<>();
                set.add(cur);
                setMap.put(cur, set);
            }
        }

        //判断两个结点是否属于一个集合
        public boolean isSameSet(Node from, Node to){
            List<Node> fromSet = setMap.get(from);
            List<Node> toSet = setMap.get(to);
            return fromSet == toSet;//一个集合
        }

        //一条边的两个结点，如果不在一个集合就合并
        public void union(Node from, Node to){
            List<Node> fromSet = setMap.get(from);//from所在的结点
            List<Node> toSet = setMap.get(to);//to所在的结点
            for (Node toNode : toSet) {
                fromSet.add(toNode);
                setMap.put(toNode, fromSet);
            }
        }
    }

    public class EdgeComparator implements Comparator<Edge> {

        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }

    }

    public Set<Edge> kruskalMST(Graph graph){
        //初始化，每个结点对应一个集合
        MySet mySet = new MySet(graph.nodes.values().stream().toList());
        //边按照从小到大排序
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
        for (Edge edge : graph.edges) {
            priorityQueue.add(edge);
        }
        Set<Edge> result = new HashSet<>();
        while (!priorityQueue.isEmpty()){
            Edge edge = priorityQueue.poll();//获取最短边
            //判断edge的两个结点是否属于一个集合
            //如果属于一个集合，加上这条边，这个图就会有环
            //如果不属于一个集合，就合并
            if (!mySet.isSameSet(edge.from, edge.to)){
                result.add(edge);
                mySet.union(edge.from, edge.to);//合并
            }
        }
        return result;
    }
}

prim算法

适用范围：要求无向图

作用：生成最小生成树

集合用于保存访问过的结点
每次都选择的是集合中的结点的所有邻接边中，最短的那条边，所以可以使用小根堆
选中的边就会有一个新的结点，这个结点就加入集合中

任意选择一个出发点，假设从A出发
A的邻接边中AC权值最小：
{A,C}两个结点的所有邻接边中CF权值最小：
{A，C，F}的邻接边中FD权值最小：
{A，C，F，D}的邻接边中CB最短：
{A，C，F，D，B}的邻接边中BE权值最小：

public class Code05_Prim {
    public class EdgeComparator implements Comparator<Edge> {

        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }

    }

    public Set<Edge> primMST(Graph graph){
        //每加入一个新的点到集合中，就会解锁新的邻接边
        //解锁的边进入小根堆
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());

        HashSet<Node> set = new HashSet<>();

        Set<Edge> result = new HashSet<>();

        // Node node = graph.nodes.values().stream().toList().get(0);//选择一个结点作为开始
        
        for (Node node : graph.nodes.values()) {//可能有多个不连通的图，需要每一个图生成一个最小生成树，这时就需要循环
            //选中的结点不在集合中
            //如果选中的结点在集合中，会形成环
            if (!set.contains(node)){//多个不连通的图的时候需要加上这行
                set.add(node);
                //遍历node的所有邻接边，将边加入到小根堆中
                for (Edge edge : node.edges) {
                    priorityQueue.add(edge);
                }
                while (!priorityQueue.isEmpty()){
                    Edge edge = priorityQueue.poll();//小根堆中的最短边
                    Node toNode = edge.to;//解锁的新节点  edge中fromNode已经在集合中了
                    //判断是否在集合中，如果在的话这个点就不能加入，也就是edge这条边不能要，否则会形成环
                    if (!set.contains(toNode)){
                        set.add(toNode);
                        result.add(edge);
                        for (Edge nextEdge : toNode.edges) {
                            priorityQueue.add(nextEdge);
                        }
                    }
                }
            }
        }
        
        return result;
    }
}

Dijkstra算法

适用范围：没有权值为负数的边

作用：从某一个点出发，到其他点的最短距离。其他点要经过已经已知的点。

从一个结点A开始，依次加入结点，更新A到其他结点的最短距离。

初始

A有AB、AC、AD三条边
- 由于这三条边使得A到B、C、D的距离变得更短了

A到A的最短距离已经求到了，剩余结点中A到B的距离最近，于是选择B。B有BA、BC、BE三条边

有了新的边，判断A到其他点的距离是否更短了
- 从A到B再到C，AC之间的距离变短
  
  也就是AB的最短距离已经知道，如果B可以到达其他结点，那么距离就会更短
- 从A到B再到E，AE之间的距离变短

剩余结点A到C的距离最近，选择C。

判断A经过B、C到其他结点是否距离更短

也就是AC最短距离是5，那么AE=AC+CE=19

如果C可以到达其他结点，那么A到其他结点的距离就可能会更新

public class Code06_Dijkstra {

    public HashMap<Node, Integer> dijkstra1(Node head){
        //从head出发到所有点的最小距离
        //key：从head出发到达key
        //value：从head出发到达key的最小距离
        //如果在表中，没有T的记录，含义是从head出发到T点的距离是正无穷
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(head, 0);
        //已经求过距离的结点，存在selectedNodes中，以后再也不碰
        HashSet<Node> selectedNodes = new HashSet<>();
        //从distanceMap中选择最短的路径，并且是没有被使用过的，没有被当作中间结点，更新head到其他结点的距离
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null){
            int distance = distanceMap.get(minNode);//head到minNode的最短距离
            //已经知道了head到minNode的最短距离，那么其它结点从head经过minNode到达之后距离是否更短
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                if (!distanceMap.containsKey(toNode)){//说明head到toNode是正无穷
                    distanceMap.put(toNode, distance + edge.weight);
                }
                //原来的距离 与 加入新节点之后的距离进行比较
                distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
            }
            selectedNodes.add(minNode);//minNode被使用过了
        }
        return distanceMap;
    }

    public 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){
                minDistance = distance;
                minNode = node;
            }
        }
        return minNode;
    }
}

标签：Node,node,结点,add,算法,006,new,public
From： https://www.cnblogs.com/jyyyy/p/18016450