【C++学习笔记】 链式前向星

2018-09-01 05:38:20来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

  • 储存方式

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

1 struct EDGE {
2     int nxt, to, 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 <cstdio>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 
 6 const int maxn = 2018702;
 7 
 8 struct EDGE {
 9     int nxt, to, val;    /* 下一条边的下标, 这条边的终点, 边权 */ 
10 };
11 EDGE edge[maxn];
12 
13 int head[maxn], cnt = 0; /* head[ i ]储存从节点 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];    * 如果是无向图就加上这个语句 
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 个节点, 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, b, 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].to, edge[j].val );
44     }
45     return 0;
46 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:CSP201604-2:俄罗斯方块

下一篇:【C++学习笔记】强大的算法——spfa