一点睛

链式前向星采用了一种静态链表存储方式，将边集数组和邻接表相结合，可以快速访问一个节点的所有邻接点。

链式前向星有如下两种存储结构。

1 边集数组

edge[],edge[i] 表示第 i 条边。

2 头节点数组

head[],head[i] 存储以 i 为起点的第1条边的下标（edge[] 中的下标）。

二图解

1 画出下面无向图的链式前向星结构。

2 图解

三链式前向星的特性

1 和邻接表一样，采用头插法进行链接，所以边的输入顺序不同，创建的链式前向星也不同。

2 对于无向图，每输入一条边，都需要添加两条边，互为反向边。例如，输入第1条边1 2 5 ，实际添加了两条边。这两条边互为反向边，可以通过与 1 的异或运算得到其反向边，0^1=1,1^1=0。也就是说，如果一条边的下标为i，则其反向边为i^1。这个特性在网络流中应用起来非常方便。

3 链式前向星具有边集数组和邻接表的功能，属于静态表，不需要频繁地创建节点，应用起来十分灵活。

四代码

package graph;import java.util.Scanner;public class ListGraph {static final int maxn = 100000 + 5;static int n;static int m;static int x;static int y;static int w;static int cnt;static Edge e[] = new Edge[maxn];static int head[] = new int[maxn];static {for (int i = 0; i < e.length; i++) {e[i] = new Edge();}for (int i = 0; i < head.length; i++) {head[i] = -1;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();cnt = 0;for (int i = 1; i <= m; i++) {x = scanner.nextInt();y = scanner.nextInt();w = scanner.nextInt();add(x, y, w); // 添加边add(y, x, w); // 添加反向边}printg();}static void printg() { // 输出链式前向星System.out.println("----------链式前向星如下：----------");for (int v = 1; v <= n; v++) {System.out.print(v + "：  ");for (int i = head[v]; i != -1; i = e[i].next) {int v1 = e[i].to, w1 = e[i].w;System.out.print("[" + v1 + " " + w1 + "]\t");}System.out.println();}}static void add(int u, int v, int w) { // 添加一条边u--ve[cnt].to = v;e[cnt].w = w;e[cnt].next = head[u];head[u] = cnt++;}
}class Edge {int to;int w;int next;
}