链式前向星是一种常见的储存图的方式（是前向星存图法的优化版本），支持增边和查询，但不支持删边（如果想要删除指定的边建议用邻接矩阵）。
- 储存方式
首先定义数组 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 }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/608225.html