Chained forward star is a common way to store graph (it is the optimized version of forward star saving graph method). It supports adding edge and querying, but it does not support deleting edge (if you want to delete the specified edge, it is suggested to use adjacency matrix).

• Storage mode

First, define the array head [i] to store the subscript of the first edge starting from node i, and define that the structure edge [i] contains three elements nxt, to, val. respectively store the subscript (nxt) of the next edge starting from node i, the end point (to) of the edge, and the edge weight (VAL).

1 struct EDGE {
2     int nxt, to, val;    /* Subscript of next edge, end point of this edge, edge weight */ 
3 };
4 EDGE edge[maxn];
5 
6 int head[maxn];   /* head[ i ]Store the subscript of the first edge starting from node i */

• Add node

The definition variable cnt represents the number of the current edge (the initial value is 0), as shown in the code.

 1 int cnt = 0;
 2 
 3 void add ( int st, int ed, int v ) {
 4     edge[ ++cnt ].nxt = head[st];
 5     edge[cnt].to = ed;
 6     edge[cnt].val = v;
 7     head[st] = cnt;
 8 
 9 /*    
10     edge[ ++cnt ].nxt = head[ed];    * If it's a undirected graph, add this statement 
11     edge[cnt].to = st; 
12     edge[cnt].val = v;
13     head[ed] = cnt;
14 
15 */
16 
17 }

• Traversal of nodes

From the data structure, we can see the code.

1 /* i Is the node number as the origin */
2 for ( int j = head[i]; j != 0 ; j = edge[j].nxt )  /* <-- The key to traversal of chain forward stars */
3         printf ( "-->%d || val = %d \n", edge[j].to, edge[j].val );
4     }

• Summary code

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 
 6 const int maxn = 2018702;
 7 
 8 struct EDGE {
 9     int nxt, to, val;    /* Subscript of next edge, end point of this edge, edge weight */ 
10 };
11 EDGE edge[maxn];
12 
13 int head[maxn], cnt = 0; /* head[ i ]Store the subscript of the first edge starting from node i */
14 
15 void add ( int st, int ed, int v ) {
16     edge[ ++cnt ].nxt = head[st];
17     edge[cnt].to = ed;
18     edge[cnt].val = v;
19     head[st] = cnt;
20 
21 /*    
22     edge[ ++cnt ].nxt = head[ed];    * If it's a undirected graph, add this statement 
23     edge[cnt].to = st; 
24     edge[cnt].val = v;
25     head[ed] = cnt;
26 
27 */
28 
29 }
30 
31 int main () {
32     memset ( head, 0, sizeof head );
33     int n, m;
34     scanf ( "%d%d", &m, &n ); /* m nodes and n edges in total */
35     for ( int i = 1; i <= n; i ++ ){
36         int a, b, c;
37         scanf ( "%d%d%d", &a, &b, &c );
38         add ( a, b, c );
39     }
40     for ( int i = 1; i <= m; i ++ ){
41         printf ( "Start with node%d Origin\n", i );
42         for ( int j = head[i]; j != 0 ; j = edge[j].nxt ) /* <-- The key to traversal of chain forward stars */
43         printf ( "-->%d || val = %d \n", edge[j].to, edge[j].val );
44     }
45     return 0;
46 }