蓝桥杯备赛第三篇（图论）

1.邻接表

static class Edge {        int next;        int value;        public Edge(int next, int value) {            this.next = next;            this.value = value;        }    }    static HashMap graph = new HashMap();    public static void addEgde(int from, int to, int value) {        if (!graph.containsKey(from)) {            graph.put(from, new LinkedList());        }        if (!graph.containsKey(to)) {            graph.put(to, new LinkedList());        }        graph.get(from).add(new Edge(to, value));        graph.get(to).add(new Edge(from, value));    }

2.dijkstra

���单源最短路，不能求带有负权边

import java.util.*;public class Main{    static class Edge {        int next;        int value;        public Edge(int next, int value) {            this.next = next;            this.value = value;        }    }    static HashMap graph = new HashMap();    //用于记录起始点到每个点的最短距离    static int[] distance;    //用于记录每个点是否被标记过,如果被标记过说明这个点已经是最短路径了    static boolean[] visited;    static int N;    static int M;    public static void addEgde(int from, int to, int value) {        if (!graph.containsKey(from)) {            graph.put(from, new LinkedList());        }        if (!graph.containsKey(to)) {            graph.put(to, new LinkedList());        }        graph.get(from).add(new Edge(to, value));        graph.get(to).add(new Edge(from, value));    }    public static void dijkstra(int start) {        Arrays.fill(distance, Integer.MAX_VALUE);        Arrays.fill(visited, false);        distance[start] = 0;        int N = graph.size();        for (int i = 0; i  distance[j]) {                    min = distance[j];                    min_index = j;                }            }            if (min_index == -1) {                return;            }            //2.标记min_index=true            visited[min_index] = true;            //3.更新从min_index出发的边            LinkedList edges = graph.get(min_index);            for (int j = 0; j  
 3.dijkstra优化版本
 
import java.util.*;public class Main {    static class Edge {        int next;        int value;        public Edge(int next, int value) {            this.next = next;            this.value = value;        }    }    static class Distance implements Comparable {        int node;        int dis;        public Distance(int node, int dis) {            this.node = node;            this.dis = dis;        }        @Override        public int compareTo(Object o) {            Distance object = (Distance) o;            return Integer.compare(this.dis, object.dis);        }    }    static HashMap graph = new HashMap();    static int N;    static int M;    static int[] distance;    static boolean[] visited;    static PriorityQueue queue = new PriorityQueue();    public static void addEdge(int from, int to, int value) {        if (!graph.containsKey(from)) {            graph.put(from, new LinkedList());        }        if (!graph.containsKey(to)) {            graph.put(to, new LinkedList());        }        graph.get(from).add(new Edge(to, value));        graph.get(to).add(new Edge(from, value));    }    public static void dijkstra(int start) {        Arrays.fill(distance, Integer.MAX_VALUE);        distance[start] = 0;        //0.初始优先队列        queue.add(new Distance(start, 0));        while (!queue.isEmpty()) {            //1.从优先队列中弹出优先级最高的,找到最小的distance,然后标记            Distance dis = queue.poll();            if (visited[dis.node]) continue;            int min_index = dis.node;            int min_dis = dis.dis;            visited[min_index] = true;            //2.更新从min发出的所有边            LinkedList edges = graph.get(min_index);            for (Edge edge : edges) {                int next = edge.next;                int value = edge.value;                if (!visited[next] && distance[next] > min_dis + value) {                    distance[next] = min_dis + value;                    //3.压入优先队列                    //虽然优先队列中会出现一个点的多个distance,但是后面的用不到                    queue.add(new Distance(next, distance[next]));                }            }        }        for (int i = 1; i  
4.Floyd
   
作用：可以用于求带负权边的多源最短路径，并且只能用于邻接矩阵。
Floyd是采用动态规划的思想实现的。
（）
设dp[k][i][j]表示只用前 k 个点时,i 到 j 之间的最短路径是dp[k][i][j]
初始化：dp[0][i][j]表示点与点之间的距离
状态转移：dp[k][i][j] = min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])，注意k是最外层循环
然后进行空间压缩:dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])
  
 
 
import java.util.*;public class Main{    static int N;    static int M;    static int[][] distance;    public static void floyd() {        for (int k = 1; k