链式前向星是一种常见的储存图的方式(是前向星存图法的优化版本),支持增边和查询,但不支持删边(如果想要删除指定的边建议用邻接矩阵)。
储存方式
首先定义数组 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 }
总结以上是内存溢出为你收集整理的C++链式前向储存方式、添加节点、节点的遍历实例讲解全部内容,希望文章能够帮你解决C++链式前向储存方式、添加节点、节点的遍历实例讲解所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)