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 stub
this.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 stub
this.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;
}
}