C# · 12月 20, 2021

C++链式前向储存方式、添加节点、节点的遍历实例讲解

链式前向星是一种常见的储存图的方式(是前向星存图法的优化版本),支持增边和查询,但不支持删边(如果想要删除指定的边建议用邻接矩阵)。

储存方式

首先定义数组 head[ i ] 来储存从节点 i 出发的第一条边的下标,定义结构体 edge[ i ] 中包含三个元素 nxt,to,val,分别储存从节点 i 出发的下一条边的下标(nxt),该边的终点(to), 该边的边权(val)。

1 struct EDGE {

2 int nxt,val; /* 下一条边的下标, 这条边的终点, 边权 */

3 };

4 EDGE edge[maxn];

5

6 int head[maxn]; /* head[ i ]储存从节点 i 出发的第一条边的下标 */

添加节点

定义变量 cnt 表示当前边的编号(初始值为0),具体如代码所示。

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]; * 如果是无向图就加上这个语句

11 edge[cnt].to = st;

12 edge[cnt].val = v;

13 head[ed] = cnt;

14

15 */

16

17 }

节点的遍历

从数据结构就可以看出来,上代码。

1 /* i 是作为原点的节点编号 */

2 for ( int j = head[i]; j != 0 ; j = edge[j].nxt ) /* <– 链式前向星遍历的关键 */

3 printf ( “–>%d || val = %d n”,edge[j].to,edge[j].val );

4 }

汇总代码

1 #include

2 #include

3

4 using namespace std;

5

6 const int maxn = 2018702;

7

8 struct EDGE {

9 int nxt,val; /* 下一条边的下标, 这条边的终点, 边权 */

10 };

11 EDGE edge[maxn];

12

13 int head[maxn],cnt = 0; /* head[ i ]储存从节点 i 出发的第一条边的下标 */

14

15 void add ( int st,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]; * 如果是无向图就加上这个语句

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,sizeof head );

33 int n,m;

34 scanf ( “%d%d”,&m,&n ); /* 共有 m 个节点, n 条边 */

35 for ( int i = 1; i <= n; i ++ ){

36 int a,b,c;

37 scanf ( “%d%d%d”,&a,&b,&c );

38 add ( a,c );

39 }

40 for ( int i = 1; i <= m; i ++ ){

41 printf ( “开始以节点%d为原点n”,i );

42 for ( int j = head[i]; j != 0 ; j = edge[j].nxt ) /* <– 链式前向星遍历的关键 */

43 printf ( “–>%d || val = %d n”,edge[j].val );

44 }

45 return 0;

46 }