图专项 ——图的存储

图的存储主要有邻接矩阵，邻接表，存边等几种方法。

邻接矩阵

临界矩阵就是按照点的个数$n$，建立一个$n\times n$的矩阵，矩阵的a[i][j]存$i$点到$j$点的权值。

private static int[][] matrix; private static int size; public static void get_data(){ Scanner in = new Scanner(System.in); size = in.nextInt(); //make the matrix matrix = new int[size+1][size+1]; for(int i=1;i<=size;i++){ for(int j=1;j<=size;j++){ int s1 = in.nextInt(); int s2 = in.nextInt(); int val = in.nextInt(); matrix[s1][s2] = val; matrix[s2][s1] = val; //undirected graph } } in.close(); }

邻接表

思路与邻接矩阵相同，在邻接矩阵中一个点到所有点的距离都将被表示（即使两个点中并没有连接的边），而邻接表就将那些没有边的两个点的存储信息删除。这样不仅可以节省存储空间，而且在搜索一个点的相邻点的时候效率也会提升。 （2019.3月的csp第五题如果用邻接表暴力的话还能得30分，，结果我用的邻接矩阵爆零了，，都是泪啊）

其中的LinkedList 可以进行高效的删除。

import java.util.LinkedList; import java.util.Scanner; class Node{ public int num; //the number of the node public int val; //the value between two node //constructor Node(int num,int val){ this.num = num; this.val = val; } } public class Main{ private static LinkedList<Node>[] list = new LinkedList[100]; public static void Init() { for (int i = 0; i < 100; i++) { list[i] = new LinkedList(); } } public static void main(String arg[]){ Init(); Scanner in = new Scanner(System.in); int size = in.nextInt(); for (int i = 0; i < size; i++) { int start = in.nextInt(); int end = in.nextInt(); int val = in.nextInt(); list[start].add(new Node(end, val)); list[end].add(new Node(start, val)); } for (int i = 0; i < 100; i++) { for(Node node:list[i]){ System.out.printf("%d->%d - %d\n", i, node.num, node.val); } } } }

前向星

理论参考博客：https://blog.csdn.net/acdreamers/article/details/16902023

Java 实现代码

import java.util.LinkedList; import java.util.Scanner; /* edge[i].to表示第i条边的终点 edge[i].next表示与第i条边同起点的下一条边的存储位置 edge[i].w为边权值 head[i],它是用来表示以i为起点的第一条边存储的位置 */ class Edge{ public int next; public int to; public int w; Edge(){} Edge(int next, int to, int w){ this.next = next; this.to = to; this.w = w; } } public class Main{ private static Edge[] matrix = new Edge[100]; private static int[] head = new int[100]; private static int cur = 0; public static void Init(){ for(int i=0; i<100; i++){ matrix[i] = new Edge(); head[i] = -1; } } public static void add(int start, int end, int val){ matrix[cur].to = end; matrix[cur].w = val; matrix[cur].next = head[start]; head[start] = cur++; } public static void main(String arg[]){ Init(); Scanner in = new Scanner(System.in); int size = in.nextInt(); for(int i=0; i<size; i++){ int start = in.nextInt(); int end = in.nextInt(); int val = in.nextInt(); add(start, end, val); } for (int i = 0; i < size; i++) { int cur = head[i]; while(cur!=-1){ System.out.printf("%d->%d - %d\n", i, matrix[cur].to, matrix[cur].w); cur = matrix[cur].next; } } } }