【备战蓝桥杯】2024蓝桥杯赛前突击省一：图论模版篇

2024蓝桥杯赛前模版突击：图论篇

图论在蓝桥杯中一般考的不难，如果有图论的题，就基本是模板题，知道板子就有分了。

邻接表

本文使用方法1的方式实现邻接表

邻接表1

static int[] dist = new int[N],st = new int[N];
static int[] h = new int[N],e = new int[M],ne = new int[M],w = new int[M];
static int idx;static void init(){Arrays.fill(h,-1);
}
static void add(int a,int b,int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}

邻接表2

用来快速得到顶点的所有邻边条数

leetcode中比较常见

ArrayList<Integer>[] g = new ArrayList[N];//初始化
for(int i=0;i<n;i++)g[i] = new ArrayList<Integer>();//顶点a,b中间添加一条边
g[a].add(b);

最短路Dijkstra

单源最短路 O(mlogn)

package _00模板;
import java.util.*;public class Dijkstra {static int INF = 0x3f3f3f3f;static int N = 101000,M = 2*N;static int[] dist = new int[N],st = new int[N];static int[] h = new int[N],e = new int[M],ne = new int[M],w = new int[M];static int idx;static int n,m;static long ans;static void add(int a,int b,int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;}static int dijkstra(int start) {Arrays.fill(dist,INF);PriorityQueue<PII> q = new PriorityQueue<>((a,b)->a.dist-b.dist);q.add(new PII(start,0));st[start] = 0;while(q.size()>0) {PII top = q.poll();if (st[top.v]==1) continue;st[top.v] = 1;for(int i=h[top.v];i!=-1;i=ne[i]) {int j = e[i],val = w[i];if(dist[top.v]+val<dist[j]) {dist[j] = dist[top.v]+val;q.add(new PII(j,dist[j]));}}}return dist[n]!=INF?dist[n]:-1;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);Arrays.fill(h,-1);n = sc.nextInt();m = sc.nextInt();for(int i=1;i<=n;i++) {}}}
class PII{int dist;int v;public PII(int v,int dist) {// TODO Auto-generated constructor stubthis.v = v;this.dist = dist;}
}

最短路spfa

负权图的最短路O（m*n）

package _00模板;
import java.util.*;
public class Spfa {static int INF = 0x3f3f3f3f;static int N = 101000,M = 2*N;static int[] st = new int[N],dist = new int[N];static int n,m;static long ans;static int[] h = new int[N],e = new int[M],w = new int[M],ne = new int[M];static int idx;static void add(int a,int b,int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;}static int spfa(int start) {Arrays.fill(dist,INF);Queue<Integer> q = new LinkedList<Integer>();q.add(start);st[start] = 1;dist[start] = 0;while(q.size()>0) {int top = q.poll();st[top] = 0;for(int i=h[top];i!=-1;i=ne[i]) {int j = e[i];if(dist[top]+w[i]< dist[j]) {dist[j] = dist[top]+w[i];if(st[j]==0) {st[j] = 1;q.add(j);}	}}}return dist[n]!=INF?dist[N]:-1;}}

Floyd

多源最短路O（n^3）

package _00模板;
import java.util.*;public class Floyd {static int INF = 0x3f3f3f3f;static int N = 101000,M = 2*N;static int[][] g = new int[N][N];static int n,m;static long ans;static void floyd() {for(int k=1;k<=n;k++) {for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {g[i][j] = Math.min(g[i][j],g[i][k]+g[k][j]);}}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);for(int i=1;i<=n;i++) {Arrays.fill(g[i],INF);g[i][i] = 0;}n = sc.nextInt();m = sc.nextInt();for(int i=1;i<=m;i++) {int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();g[a][b] = c;g[b][a] = c;}floyd();}
}

最小生成树kruskal

kruskal 算法O (mlogm)，Prim不需要掌握，用kruskal 就行

package _00模板;
import java.util.*;public class Kruskal {static int INF = 0x3f3f3f3f;static int N = 101000,M = 2*N;static Edge[] edges = new Edge[N];static int idx;static int n,m;static long ans;static int[] fa = new int[N];static void init() {for(int i=1;i<=n;i++) {fa[i] = i;}}static int find(int x) {if(fa[x]==x) return x;return fa[x] = find(fa[x]);}static void union(int a,int b) {fa[find(a)] = find(b);}static int kruskal() {Arrays.sort(edges,0,idx,(a,b)->(a.w-b.w));int cnt = 0,res = 0;for(int i=0;i<m;i++) {int a = edges[i].a;int b = edges[i].b;int w = edges[i].w;if(find(a)!=find(b)) {union(a,b);cnt += 1;res += w;}}return cnt==n-1?res:-1;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for(int i=1;i<=m;i++) {int a = sc.nextInt();int b = sc.nextInt();int w = sc.nextInt();edges[idx++] = new Edge(a,b,w);}}
}
class Edge{int a,b,w;public Edge(int a,int b,int w) {// TODO Auto-generated constructor stubthis.a = a;this.b = b;this.w = w;}
}

拓扑排序

int[] d = new int[N];//存放入度int[] print = new int[N];//记录答案int cnt;static boolean topSort() {Queue<Integer> q = new LinkedList<Integer>();for(int i=1;i<=n;i++) {if(d[i]==0)q.add(i);}while(q.size()>0) {Integer top = q.poll();print[cnt++] = top;for(int i=h[top];i!=-1;i=ne[i]) {int j = e[i];d[j]--;if(d[j]==0) {q.add(j);}}}return n==cnt;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for(int i=1;i<=m;i++) {int a = sc.nextInt();int b = sc.nextInt();int w = sc.nextInt();add(a,b,w);d[b] += 1;}}