链式前向星

性质

一种邻接表的写法

关键点：

• 数据结构

  // 边
  class Edge {
      int next; // 指向相同起始点的下一条边
      int to; // 邻接点
      int w; // 权重
  }
  Edge[] edge = new Edge[9];
  // edge[cnt]表示编号为cnt的边
  
  // 用数组表示
  int[] next = new int[MAX];
  int[] to = new int[MAX];
  int[] w = new int[MAX];
  // 即next[j]表示与编号为j的边的起始点相同的下一条边
  //   to[j]表示编号为j的边的邻接点
  //   w[j]表示编号为j的边的权重
  
  //存放每个起始点的边头指针
  int[] head = new int[MAX]; 
  // 即head[i]表示以i为起点的第一条边的序号
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20

• 加边操作

  addEdge(int from , int to, int w){
      // cnt为边的序号
      edge[cnt].to = to;
      edge[cnt].w = w;
      // 头插法
      edge[cnt].next = head[from];
      head[from] = cnt
  }
  1
  2
  3
  4
  5
  6
  7
  8

• 遍历某一起始点的所有边

  int t = head[i]; // 假设不存在为-1
  while(t != -1){
  	....
      t = edge[t].next
  }
  1
  2
  3
  4
  5

附：用链式前向星求拓扑序列

import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int MAXN = 200002;
    public static int MAXM = 200002;
    public static int[] head = new int[MAXN];
    public static int[] indegree = new int[MAXN];// 入度表
    public static int[] q = new int[MAXN];
    public static int h = 0; // 队列头
    public static int r = 0; // 队列尾

    // edge
    public static int[] next = new int[MAXM];
    public static int[] to = new int[MAXM];
    public static int cnt = 0; // 边的编号

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder re = new StringBuilder();
        String str;
        // 满足即存在环
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        int count = 0 ; // 记录出队的节点数
        Arrays.fill(head, 0, n + 1, -1);
        if (m > n * (n - 1) / 2 ) {
            System.out.println("-1");
            return;
        }

        // 存图
        while ((str = br.readLine()) != null) {
            String[] temp = str.split(" ");
            int from = Integer.parseInt(temp[0]);
            int to = Integer.parseInt(temp[1]);
            addEdge(from, to);
            indegree[to]++;
        }
		
		// 初始化入度表
        for (int i = 1 ; i < n + 1; i++) {
            if(indegree[i] == 0){
                q[r++] = i; 
            }
        }
        while(h < r){
            int no = q[h++];
            count++;
            re.append(no + " ");
            updateIndegree(no);
        }
        if(count == n){
            System.out.println(re);
        }
        else{
             System.out.println("-1");
        }
        br.close();
    }

    public static void addEdge(int from, int t) {
        to[cnt] = t;
        next[cnt] = head[from];
        head[from] = cnt++;  
    }

    public static void updateIndegree(int node){
        int i = head[node];
        while(i != -1){
            indegree[to[i]]--;
            if( indegree[to[i]] == 0){
                q[r++] = (to[i]);
            }
            i = next[i];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80