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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!