链式前向星

public class 链式前向星 {
	public static void main(String[] args) {
		add(1, 3, 5);
		add(1, 2, 4);
		add(1, 5, 8);
		visit(1);
	}

	static int N = 1005;
	static int cnt = 0;// 边的编号
	static int[] first = new int[N];
	static Edge[] edges = new Edge[N];

	/**
	 * 遍历以 u 为起点的所有边
	 * 
	 * @param u 起点
	 */
	static void visit(int u) {
		for (int i = first[u]; i != 0; i = edges[i].next) {
			System.out.println(u + "->" + edges[i].to + "的权值为" + edges[i].w);
		}
	}

	/**
	 * 添加一条边（单向添加）
	 * 
	 * @param u 边的起点
	 * @param v 边的终点
	 * @param w 边的权值
	 * 
	 * 注意：这里的 edges 数组仅仅分配了数组空间，
	 * 空间中的每一个对象元素并没有进行初始化，
	 * 要使用 new 关键字进行处理才能对对象进行使用
	 */
	static void add(int u, int v, int w) {
		edges[++cnt] = new Edge(v, w, first[u]);// cnt = 0 这个编号舍弃不用
		first[u] = cnt;// 更新
	}
}

/**
 * 边类 
 * 一共有三个属性
 */
class Edge {
	int to;// 终点
	int w;// 边的权值
	int next;// 下一条边

	public Edge(int to, int w, int next) {
		super();
		this.to = to;
		this.w = w;
		this.next = next;
	}
}