使用LinkedList手撕图的邻接表
主要是学习图的邻接表的核心结构等等，话不多说直接上代码：
import java.util.LinkedList;public class GrapAdj {private int n ; // 表示图中顶点的数量。private LinkedList<Integer>[] adj;public GrapAdj(int n){this.n = n;adj = new LinkedList[n + 1];}private void init(){for (int i = 1;i <= n; i++){adj[i] = new LinkedList<>();}}public void add(int v1,int v2){adj[v1].add(v2);}public void print(){for (int v= 1; v <= n;v++){System.out.println(v+"->");for (int x: adj[v]){System.out.println(x+"->");}System.out.println(0);}}public static void main(String[] args) {GrapAdj graph = new GrapAdj(5);graph.init();graph.add(1, 2);graph.add(1, 3);graph.add(2, 4);graph.add(3, 4);graph.add(4, 5);graph.print();}
}
下面是基于数据结构方面的分析
在数据结构方面，使用邻接表来表示图是一种常用的图表示方法，特别适用于稀疏图（即边数远小于节点数平方的图）。以下是对邻接表数据结构的详细分析：
数据结构组成
1. 顶点数组：
private int n ：表示图中顶点的数量。这个变量用于记录图的大小，方便在初始化和遍历时使用。
private LinkedList<Integer>[ ] adj：这是一个数组，每个元素是一个 `LinkedList<Integer>。数组的索引对应图中的顶点编号，数组的元素是存储与该顶点相邻的顶点列表的链表。
索引：数组的索引从1到 `n`，对应图中的顶点编号。使用 `n + 1` 的数组大小是为了方便使用从1开始的顶点编号。
链表：每个链表存储与对应顶点直接相连的所有顶点的编号。链表的动态特性使得添加和删除边的操作非常高效。
2，初始化过程
初始化数组：
adj = new LinkedList[n + 1];：创建一个大小为 `n + 1` 的数组，每个元素初始化为 `null`。
init()` 方法遍历数组，为每个索引位置创建一个新的 LinkedList<Integer>。这一步确保每个顶点都有一个空的邻接列表，准备用于添加邻接顶点。
（1） 添加边的过程
add(int v1, int v2) 方法：
将顶点 `v2` 添加到顶点 `v1` 的邻接列表中，即 `adj[v1].add(v2);。
这里假设图是有向图。如果图是无向图，还需要添加 `adj[v2].add(v1);`，以表示双向连接。
（2）打印图的过程
print() 方法：
遍历每个顶点 `v`，打印其编号和箭头 `v+"->"`。
遍历顶点 `v` 的邻接列表，打印每个邻接顶点的编号和箭头 `x+"->"`。
每个顶点的邻接列表打印完毕后，打印一个0作为结束符，表示该顶点的邻接列表结束。
（3） 邻接表数据结构的优势
空间效率：邻接表只需要存储实际存在的边，对于稀疏图来说，相比于邻接矩阵，邻接表可以节省大量的空间。
动态操作：由于使用了链表，添加和删除边的操作非常高效，不需要像邻接矩阵那样重新分配整个矩阵。
灵活性：可以方便地处理图的动态变化，如增加或删除顶点和边，动态操作效率很高。
数据结构的局限性
查找边的操作：在邻接表中查找是否存在一条边需要遍历链表，时间复杂度为 O(deg(v))，其中 deg(v) 是顶点 v 的度。对于稠密图，这可能不如邻接矩阵高效。
不支持权重：基本的邻接表不支持边的权重信息。如果需要处理加权图，需要对数据结构进行扩展，例如使用 `LinkedList<Pair<Integer, Integer>>` 来存储邻接顶点及其权重。
通过使用邻接表数据结构，能够有效地表示了图的结构，并且拥有了基本的图操作功能。邻接表是图论中常用的数据结构之一，特别适用于处理稀疏图和动态图。
下面是对于代码的详细分析
1，类定义和成员变量
private int n;：- 这个变量表示图中顶点的数量。它用于初始化和管理图的大小。
private LinkedList<Integer>[] adj;：- 这是一个数组，每个元素是一个
LinkedList<Integer>。数组的索引对应图中的顶点编号，数组的元素是存储与该顶点相邻的顶点列表的链表。 - 使用
LinkedList是因为链表可以方便地进行插入和删除操作，适合动态地添加和删除边。
- 这是一个数组，每个元素是一个
2，构造函数
public GrapAdj(int n)：- 构造函数接受一个参数
n，表示图中顶点的数量。 - 初始化
this.n为n。 - 初始化
adj数组的大小为n + 1。这里使用n + 1是为了方便使用从1开始的顶点编号（例如，顶点编号从1到n）。
- 构造函数接受一个参数
4，初始化方法
private void init()：- 这个方法用于初始化邻接表。
- 使用一个
for循环遍历从1到n的每个顶点。 - 对于每个顶点
i，初始化adj[i]为一个新的LinkedList<Integer>。这样，每个顶点的邻接列表都是一个空的链表，准备用于添加邻接顶点。
5，添加边的方法
public void add(int v1, int v2)：- 这个方法用于向图中添加一条从顶点
v1到顶点v2的边。 - 使用
adj[v1].add(v2)将顶点v2添加到顶点v1的邻接列表中。 - 这里假设图是有向图，如果图是无向图，还需要添加
adj[v2].add(v1)。
- 这个方法用于向图中添加一条从顶点
6，打印图的方法
public void print()：- 这个方法用于打印图的邻接表。
- 使用一个
for循环遍历从1到n的每个顶点v。 - 打印顶点
v的编号和箭头v+"->"。 - 使用一个增强型
for循环遍历顶点v的邻接列表中的每个顶点x，并打印x+"->"。 - 每个顶点的邻接列表打印完毕后，打印一个0作为结束符，表示该顶点的邻接列表结束。
7，主方法（用于测试）
public static void main(String[] args)：- 创建一个
GrapAdj对象graph，顶点数量为5。 - 调用
init()方法初始化邻接表。 - 使用
add()方法添加几条边，构建一个简单的图。 - 调用
print()方法打印图的邻接表，展示图的结构。
- 创建一个
8，难点分析
- 数组初始化：
adj = new LinkedList[n + 1];这行代码初始化了一个数组，但数组的每个元素都是null。因此，需要在init()方法中为每个元素创建一个LinkedList。
- 邻接表的动态管理：
- 使用
LinkedList作为邻接列表的好处是可以动态地添加和删除边，但需要确保在添加边之前邻接列表已经被正确初始化。
- 使用